第 3 章：欧拉函数与欧拉定理

3.1 欧拉函数数的是哪些整数

$\varphi(n)$ 表示 $1,2,\ldots,n$ 中与 $n$ 互质的整数个数。等价地，它是模 $n$ 可逆剩余类的个数。它数的不是素数，也不是 $n$ 的质因子。

若 $n=\prod_{i=1}^k p_i^{e_i}$ 是质因数分解，其中 $p_i$ 互不相同，那么

$\boxed{\varphi(n)=n\prod_{i=1}^k\left(1-\frac1{p_i}\right).}$

为什么只出现不同的质因子，而没有直接出现次数 $e_i$ ？一个整数与 $n$ 不互质，意味着它被某个 $p_i$ 整除。是否被 $p_i$ 整除已经决定了它要被排除，不需要再分别排除 $p_i^2,p_i^3$ 的倍数。幂次仍包含在前面的 $n$ 中。

3.2 乘积公式为什么就是容斥

先看 $n$ 恰有两个不同质因子 $p,q$ 的情况。在 $1$ 至 $n$ 中， $p$ 的倍数有 $n/p$ 个， $q$ 的倍数有 $n/q$ 个。如果直接都减掉，同时被 $p,q$ 整除的整数会被减两次，所以要补回 $n/(pq)$ 个：

$\varphi(n)=n-\frac np-\frac nq+\frac n{pq} =n\left(1-\frac1p\right)\left(1-\frac1q\right).$

有更多质因子时，原理相同：减去单个倍数集合，加回两两交集，再减去三重交集，依次交替。展开 $\prod_i(1-1/p_i)$ 时，选一个负项得到一次减法，选两个负项得到交集的加法，选三个负项得到三重交集的减法。乘积展开恰好记录了每种交集和符号。

对于每一个具体整数，这样加减后的总权重是什么？若它不被任何 $p_i$ 整除，权重为1；若它被其中 $j\ge1$ 个整除，权重为 $(1-1)^j=0$ 。因此最终恰好保留互质整数。完整容斥展开在第14章。

特别地， $\varphi(p)=p-1$ ， $\varphi(p^e)=p^e-p^{e-1}$ 。若 $m,n$ 互质，CRT把模 $mn$ 的可逆类与一对模 $m,n$ 的可逆类对应，因而 $\varphi(mn)=\varphi(m)\varphi(n)$ 。这个对应在第6章解释。

3.3 欧拉定理的证明为什么仍是重排

欧拉定理把质数模数推广到一般模数：若 $n\ge2$ 且 $\gcd(a,n)=1$ ，则

$\boxed{a^{\varphi(n)}\equiv1\pmod n.}$

设 $r_1,\ldots,r_{\varphi(n)}$ 代表全部与 $n$ 互质的剩余类。乘 $a$ 后仍互质：若某个质因子同时整除 $ar_i$ 和 $n$ ，它必整除 $a$ 或 $r_i$ ，而这两种情况都被互质条件排除。不同的 $r_i$ 也不会碰到一起： $ar_i\equiv ar_j$ 可以消去 $a$ 。