欧拉函数

欧拉函数 $\phi (n)$ 统计 $1\le k\le n$ 中与正整数 $n$ 互素的整数个数。例如 $n=12$ 时只有 $1,5,7,11$ 互素于 12，所以 $\phi (12)=4$。$n=1$ 时，约定 $\phi (1)=1$，对应唯一的整数 1。

从素因子排除不合格的数

若 $p$ 是素数，$1,\dots ,p-1$ 都与 $p$ 互素，因此 $\phi (p)=p-1$。对素数幂 $p^k$，在 $1,\dots ,p^k$ 中，恰有 $p^{k-1}$ 个数是 $p$ 的倍数，余下 $$\phi (p^k)=p^k-p^{k-1}=p^k(1-\frac{1}{p}).$$

一般地，把 $n$ 的不同素因子记为 $p_1,\dots ,p_r$。一个数与 $n$ 互素，当且仅当它不被任何 $p_i$ 整除。用容斥原理排除这些倍数，可得 $$\phi (n)=n\prod _{p\mid n}(1-\frac{1}{p}),$$ 乘积只取不同素因子。以 $12=2^2\cdot 3$ 代入，得 $12(1-1/2)(1-1/3)=4$，与逐个列数一致。重复把素因子 2 算两次会错误地排除同一批数。欧拉定理用 $\phi (n)$ 给出互素整数的幂在模 $n$ 下的周期性。

再取 $n=30=2\cdot 3\cdot 5$ 看容斥的每一层。先从 30 个整数中减去 2、3、5 的倍数，分别有 15、10、6 个；两两交叠的倍数 6、10、15 又须加回，分别有 5、3、2 个；三重交叠的 30 的倍数最后再减去 1 个。于是 $\phi (30)=30-(15+10+6)+(5+3+2)-1=8$。乘积公式给 $30(1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5})=8$，与逐层计数一致。

参考资料

• MIT，Mathematics for Computer Science，Euler's Theorem 章节。
• MIT 18.781，初等数论讲义。
• 继续阅读：算术基本定理、容斥原理、欧拉定理。