第 5 章：欧拉函数的计数与两个恒等式

本章对象： $\varphi(n)$ 数 $1,\ldots,n$ 中与 $n$ 互素的整数； $p\mid n$ 的乘积仅遍历不同素因子。

5.1 欧拉函数：数互素整数，也数可逆剩余类

原问题：我是指那个公因子的

对，你指的是前面那个和“公因子/互素”有关的 欧拉函数（Euler totient function），不是欧拉公式。

它记作

$\boxed{\varphi(n)}$

定义是：

$\boxed{ \varphi(n)=\#\{1\le k\le n:\gcd(k,n)=1\} }$

也就是：从 $1$ 到 $n$ 里，有多少个数和 $n$ 没有大于 1 的公因子。

例如 $n=6$ ：

$1,2,3,4,5,6$

其中与 6 互素的是

$1,5.$

所以

$\varphi(6)=2.$

为什么会有这样一个函数？本质上是数论里经常需要问：

模 $n$ 意义下，哪些数有乘法逆元？

答案恰好就是那些满足

$\gcd(k,n)=1$

的数，所以 $\varphi(n)$ 其实是在数：

$(\mathbb{Z}/n\mathbb{Z})^\times$

里有多少个元素。

而在你现在学的单位根里，它又自然出现，因为：

$\zeta_n^k$

是本原 $n$ 次单位根，当且仅当

$\gcd(k,n)=1.$

所以本原 $n$ 次单位根的个数就是

$\varphi(n).$

更进一步，欧拉函数有一个很重要的计算公式：

$\boxed{ \varphi(n) = n\prod_{p\mid n}\left(1-\frac1p\right) }$

其中 $p$ 遍历 $n$ 的不同素因子。

比如

$12=2^2\cdot3.$

所以

$\varphi(12) = 12\left(1-\frac12\right)\left(1-\frac13\right) =4.$

因为 $1,\dots,12$ 中与 12 互素的是：

$1,5,7,11.$

这个公式其实就是“把所有与 $n$ 有公共素因子的数删掉”。

例如 $n=12$ 。先有 12 个数。

删掉 2 的倍数，占一半：

$12\left(1-\frac12\right)=6.$

再删掉剩下那些 3 的倍数，相当于再乘：

$1-\frac13.$

于是：

$12\cdot\frac12\cdot\frac23=4.$

所以

$\boxed{ \varphi(n) = n\prod_{p\mid n} \left(1-\frac1p\right) }$

本质上来自“排除所有与 $n$ 共享素因子的数”。

你现在先记住最核心的两层就够了：

$\boxed{ \varphi(n)=\text{与 }n\text{ 互素的余数类数量} }$

而在分圆域里：

$\boxed{ \varphi(n)=\text{本原 }n\text{ 次单位根的数量} }$

所以最终才得到

$\deg\Phi_n=\varphi(n).$

下一步我可以专门一步一步证明为什么

$\varphi(n)=n\prod_{p\mid n}(1-\frac1p)$

而不是只给这个公式。

5.2 用容斥原理证明欧拉函数的乘积公式

我们就把这个公式从最直观的“删掉有公共素因子的数”一步一步推出来：

$\boxed{ \varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right) }$

其中 $p\mid n$ 表示 $p$ 遍历 $n$ 的所有不同素因子。

先看一个具体例子， $n=12$ 。

$12=2^2\cdot3.$

要找和 12 互素的数，就是在

$1,2,\dots,12$

中，排除所有和 12 有公共素因子的数。

因为 12 的素因子只有 2 和 3，所以只需要排除：

$2\text{ 的倍数}$

以及

$3\text{ 的倍数}.$

一开始有 12 个数。

2 的倍数有：

$2,4,6,8,10,12$

共

$\frac{12}{2}=6$

个。

所以删掉它们以后剩：

$12-\frac{12}{2} = 12\left(1-\frac12\right) = 6.$

但现在还要删掉 3 的倍数。

不能直接再减 $12/3$ ，因为 6 和 12 已经因为是 2 的倍数被删过一次了。

这就是为什么需要“容斥原理”。

3 的倍数有

$\frac{12}{3}=4$

个：

$3,6,9,12.$

而同时是 2 和 3 的倍数，也就是 6 的倍数，有：

$\frac{12}{6}=2$

个。

所以最终：

$\varphi(12) = 12-\frac{12}{2}-\frac{12}{3}+\frac{12}{6}.$

算一下：

$=12-6-4+2 =4.$

整理：

$\varphi(12) = 12\left( 1-\frac12-\frac13+\frac16 \right).$

注意括号里正好能因式分解：

$1-\frac12-\frac13+\frac16 = \left(1-\frac12\right) \left(1-\frac13\right).$

所以：

$\boxed{ \varphi(12) = 12\left(1-\frac12\right) \left(1-\frac13\right) }$

现在推广到一般情况。

假设：

$n=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$

是 $n$ 的素因数分解。

一个数 $k$ 和 $n$ 互素，当且仅当：

$k$

不被任何一个

$p_1,p_2,\dots,p_r$

整除。

所以我们从 $1,\dots,n$ 这 $n$ 个数里，删掉所有 $p_i$ 的倍数。

被 $p_i$ 整除的数有：

$\frac{n}{p_i}$

个。

被 $p_i,p_j$ 同时整除的数有：

$\frac{n}{p_ip_j}$

个。

被三个不同素数同时整除的数有：

$\frac{n}{p_ip_jp_k}$

个。

于是容斥原理给：

$\varphi(n) = n -\sum_i\frac{n}{p_i} +\sum_{i<j}\frac{n}{p_ip_j} -\sum_{i<j<k}\frac{n}{p_ip_jp_k} +\cdots$

把 $n$ 提出来：

$\varphi(n) = n\left[ 1 -\sum_i\frac1{p_i} +\sum_{i<j}\frac1{p_ip_j} -\cdots \right].$

而括号里恰好就是乘积展开：

$\prod_{i=1}^r \left(1-\frac1{p_i}\right).$

所以：

$\boxed{ \varphi(n) = n\prod_{p\mid n} \left(1-\frac1p\right) }$

这就是公式的来源。

这里还有一个你很值得注意的点：

$\boxed{ \text{指数 }a_i\text{ 为什么没有直接出现在乘积里？} }$

因为判断

$\gcd(k,n)=1$

时，只关心 $k$ 是否被某个素因子 $p_i$ 整除。

比如：

$n=2^5\cdot3^7.$

一个 $k$ 只要能被 2 整除，就已经和 $n$ 不互素了；不需要继续区分它是否能被 $2^2,2^3$ 整除。

所以乘积只遍历“不同素因子”。

例如：

$\varphi(8) = 8\left(1-\frac12\right)=4.$

虽然：

$8=2^3,$

但只出现一次素数 2。

同样：

$\varphi(18) = 18\left(1-\frac12\right)\left(1-\frac13\right) =6.$

与 18 互素的数正好是：

$1,5,7,11,13,17.$

现在把它重新接回你正在学的分圆域：

$\boxed{ \deg\Phi_n = \varphi(n) = n\prod_{p\mid n} \left(1-\frac1p\right) }$

所以例如：

$[\mathbb{Q}(\zeta_{12}):\mathbb{Q}] = \deg\Phi_{12} = \varphi(12) = 4.$

也就是说，欧拉函数不仅是在数“互素整数”，同时直接告诉你第 $n$ 个分圆域相对于 $\mathbb{Q}$ 的扩张次数。

5.3 为什么最大公因数一定整除 n

原问题：为什么整除

因为这里的 $d$ 被定义成

$d=\gcd(k,n).$

而“最大公因数”首先得是一个公因数，所以它一定同时整除 $k$ 和 $n$ 。

也就是说：

$d\mid k$

并且

$\boxed{d\mid n}.$

例如如果

$\gcd(8,12)=4,$

那么 4 当然整除 8，也整除 12。

所以当我们把 $1,\dots,n$ 按照

$\gcd(k,n)=d$

分类时， $d$ 不可能随便取，而只能取 $n$ 的约数。

比如 $n=12$ ，那么可能的 $d$ 只能是

$1,2,3,4,6,12.$

不可能有

$\gcd(k,12)=5$

因为 5 根本不整除 12。

所以前面写

$\boxed{d\mid n}$

不是额外假设，而是从

$d=\gcd(k,n)$

自动得到的。

5.4 欧拉函数的约数和：单位根计数证明

原问题：为什么这个成立

这个恒等式

$\boxed{ n=\sum_{d\mid n}\varphi(d) }$

本质上是因为：把 $1,\dots,n$ 这 $n$ 个整数按它们和 $n$ 的最大公因数分类，每一类的数量恰好是某个 $\varphi(d)$ 。

先看最直观的单位根版本，因为和你现在学的内容最贴近。

$x^n-1$ 一共有 $n$ 个不同的复根。每一个根都有一个阶，而且这个阶一定整除 $n$ 。

所以这 $n$ 个根可以按“阶”分组：

$\text{阶为 }d,\qquad d\mid n.$

而阶恰好为 $d$ 的单位根有多少个？

就是：

$\varphi(d).$

因为本原 $d$ 次单位根一共有 $\varphi(d)$ 个。

于是所有根的总数就是：

$\sum_{d\mid n}\varphi(d).$

但另一方面， $x^n-1$ 本来就有 $n$ 个不同的根。

所以：

$\boxed{ n=\sum_{d\mid n}\varphi(d) }$

举个例子， $n=6$ 。

6 的约数是：

$1,2,3,6.$

各阶单位根的数量分别是：

$\varphi(1)=1,$

$\varphi(2)=1,$

$\varphi(3)=2,$

$\varphi(6)=2.$

加起来：

$1+1+2+2=6.$

这正好就是 $x^6-1$ 的 6 个根。

所以这个公式其实是在说：

$\boxed{ \text{所有 }n\text{ 次单位根} = \text{按阶分类后的所有本原 }d\text{ 次单位根} }$

其中 $d$ 遍历 $n$ 的所有约数。

如果你愿意，我下一步可以继续给你讲这个恒等式的纯整数证明，不借助单位根。

5.5 欧拉函数的约数和：纯整数分类证明

我们不用单位根，只用整数和最大公因数来证明

$\boxed{\sum_{d\mid n}\varphi(d)=n}.$

核心思路是：把

$1,2,\dots,n$

这 $n$ 个整数按它们和 $n$ 的最大公因数分类。

先看一个具体例子，取

$n=12.$

把 $1,\dots,12$ 按

$\gcd(k,12)$

来分组。

可能出现的最大公因数一定是 12 的约数：

$1,2,3,4,6,12.$

例如：

$\gcd(k,12)=1$

的有

$1,5,7,11,$

共

$4=\varphi(12)$

个。

再看

$\gcd(k,12)=2.$

这些 $k$ 可以写成

$k=2m.$

条件变成

$\gcd(2m,12)=2.$

把 2 提出来：

$\gcd(m,6)=1.$

所以 $m$ 必须在 $1,\dots,6$ 中与 6 互素。

这样的 $m$ 有

$\varphi(6)=2$

个。

所以满足

$\gcd(k,12)=2$

的 $k$ 也有

$\varphi(6)$

个。

一般来说，如果

$\gcd(k,n)=d,$

其中

$d\mid n,$

那么可以写

$k=dm.$

又因为

$n=d\cdot \frac nd,$

所以

$\gcd(k,n)=d$

等价于

$\gcd\left(dm,d\frac nd\right)=d.$

提出 $d$ ：

$d\gcd\left(m,\frac nd\right)=d.$

于是

$\boxed{ \gcd\left(m,\frac nd\right)=1 }$

所以这样的 $m$ 有

$\varphi\left(\frac nd\right)$

个。

因此，满足

$\gcd(k,n)=d$

的整数 $k$ 有

$\boxed{ \varphi\left(\frac nd\right) }$

个。

现在把所有可能的 $d\mid n$ 加起来，因为每个

$k=1,\dots,n$

都会且只会属于其中一类：

$n = \sum_{d\mid n} \varphi\left(\frac nd\right).$

最后注意，当 $d$ 遍历 $n$ 的所有约数时，

$\frac nd$

也恰好遍历 $n$ 的所有约数。

所以把变量换个名字，就得到

$\boxed{ n=\sum_{d\mid n}\varphi(d). }$

这就是纯整数证明。

你可以把它记成一句话：

$\boxed{ \text{把 }1,\dots,n\text{ 按 }\gcd(k,n)\text{ 分类} }$

每一类的大小就是某个欧拉函数值，所以总数相加必然等于 $n$ 。

而你前面学的单位根证明，其实和这个证明结构非常像：一个是按“最大公因数”分类，一个是按“阶”分类。