形式陈述

Euler 函数定义为

$$ \varphi(n)=|\{1\le a\le n:\gcd(a,n)=1\}|, $$$$\phi (n)=|\{1\le a\le n:gcd(a,n)=1\}|,$$

等价于单位群 $(\mathbb Z/n\mathbb Z)^\times$$(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ 的阶。若

$$ n=\prod_{i=1}^r p_i^{e_i}, $$$$n=\prod _{i=1}^r{p}_i^{e_i},$$

则

$$ \varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right) =\prod_i p_i^{e_i-1}(p_i-1). $$$$\phi (n)=n\prod _{p\mid n}(1-\frac{1}{p})=\prod _i{p}_i^{e_i-1}(p_i-1).$$

若 $\gcd(m,n)=1$$gcd(m,n)=1$，中国剩余定理给出乘法性

$$ \varphi(mn)=\varphi(m)\varphi(n). $$$$\phi (mn)=\phi (m)\phi (n).$$

另有约数和恒等式 $\sum_{d\mid n}\varphi(d)=n$$\sum _{d\mid n}\phi (d)=n$。

直觉

$\varphi(n)$$\phi (n)$ 统计模 $n$$n$ 下可逆的剩余类。每个不同素因子会排除其倍数，乘积公式正是对这些独立排除的计数。

例子与边界

$\varphi(p)=p-1$$\phi (p)=p-1$，$\varphi(p^k)=p^k-p^{k-1}$$\phi (p^k)=p^k-p^{k-1}$，而 $\varphi(12)=4$$\phi (12)=4$，对应单位类 $1,5,7,11$$1,5,7,11$。函数只在互素输入上乘法；例如 $\varphi(4)\varphi(2)=2$$\phi (4)\phi (2)=2$，但 $\varphi(8)=4$$\phi (8)=4$。定义区间可写 $1\le a\le n$$1\le a\le n$ 或 $0\le a<n$$0\le a<n$，给出同一类数；通常约定 $\varphi(1)=1$$\phi (1)=1$。由 $\varphi(n)$$\phi (n)$ 一般不能唯一恢复 $n$$n$，不同整数可有相同函数值。公式依赖素因数集合，不只是 $n$$n$ 的大小。

推论与应用

Euler 函数给出 Euler 定理指数、RSA 群阶、循环群生成元计数和 Farey 序列统计。

参考资料

• Kenneth Ireland and Michael Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Springer, 1990，Ch. 2, Euler phi function and multiplicativity。
• Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley, 1991，Ch. 2, Euler function and reduced residue systems。