Euler 函数

1. 概述

于 初等数论 中, Euler 函数 计数模 的可逆 剩余类, 也就是 简化剩余系 的元素个数. 它既反映整数的素因数结构, 也给出 Euler 定理 中指数的自然上界.

2. 定义

定义 1 (Euler 函数)

对任意 , 定义：

称 算术函数 为 Euler 函数, 也称 Euler φ 函数.

3. 例子

例子 2 (Euler 函数的初步取值)

由 Euler 函数 的定义可得：

4. 相关性质

命题 3 (Euler 函数的基本公式)

Euler 函数 满足：

1. 若 是 素数, , 则：
2. 是 乘性函数; 即若 且 , 则：
3. 设 且 . 若其标准素因数分解为： 其中 , 为两两不同的素数, 则：

证明 4 (Euler 函数的基本公式)

1. 在 中, 不与 互素 的整数恰为 的倍数, 共有 个, 故 .
2. 若 或 , 等式由 直接成立. 以下设 . 由 中国剩余定理, 每个模 剩余类 唯一对应于一个模 剩余类与一个模 剩余类的有序对. 一个整数与 互素, 当且仅当它同时与 互素. 因此可逆剩余类的个数为 .
3. 由 算术基本定理, 不同的 两两互素. 反复应用 Euler 函数的基本公式 的第 2 条, 再使用第 1 条, 得：

定理 5 (Euler 定理)

设 , 且 . 则由 Euler 函数 给出的指数满足：

证明 6 (Euler 定理)

取模 的 简化剩余系 . 由 互素乘法置换简化剩余系, 模 同余 于 中元素的一个排列. 将这些同余式相乘, 得：

每个 均与 互素, 反复应用 互素性对乘积的保持 可知其乘积也与 互素. 由 同余式中的互素消去律 消去该乘积, 即得 .

推论 7 (Fermat 小定理)

设 是 素数, . 则：

特别地, 若 , 则 .

证明 8 (Fermat 小定理)

若 , 则 . 若 , 由 为 素数 可知 . 又由 Euler 函数 的定义与 Euler 函数的基本公式 的第 1 条有 , 故 Euler 定理 给出 ; 两侧乘以 即得 .

5. 相关概念

• 简化剩余系
• 模逆元
• 同余方程组
• 素数
• 算术函数
• 乘性函数

6. 术语翻译

中文	英文
Euler 函数	Euler’s totient function
Euler 定理	Euler’s theorem
Fermat 小定理	Fermat’s little theorem

初等数论