这篇文章上次修改于 613 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

欧拉函数

对于正整数 $n$ ，欧拉函数 $\varphi(n)$ 表示 $n$ 的缩同余类的个数，也就是 $1,2,3,\cdots,n-1$ 中与 $n$ 互素的数的个数。（这里不需要考虑 0 和 n ，因为当 n > 1 时，这两个数一定与 n 不互素。）

按照肯尼斯·艾佛森的记号，欧拉函数的定义式可以写为

$\bbox[#C0FFFF,5px,border:2px solid #90A0FF]{ \varphi(x)=\sum_k[(k,n)=1][k \in N][k<n] }\\$

这里的方括号记号表示：对于命题函数 $p(k)$ ， $[p(k)]=\begin{cases} 1\ ,p(k)\\ 0\ ,\neg p(k) \end{cases}$ 。

但是这种表示方式很难计算欧拉函数的值。事实上，欧拉函数有另一个便于计算的公式：

$\bbox[#C0FFFF,5px,border:2px solid #90A0FF]{ \varphi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})\cdots(1-\frac{1}{p_k}) }\\$

其中 $p_1,p_2,p_3,\cdots,p_k$ 是 $n$ 的所有不重复的素因子。

下面给出对这个计算式的证明。

情况1

当 n = 0 时，显然 $\varphi(0)=0$ ，因为 n = 0 时，欧拉函数的计算范围内只有 0，但是 (0, 0) = 0。

当 n = 1 时， $\varphi(1)=1$ ，因为 1 与自身互素。

情况2

当 n 为素数时， $\varphi(n)=n-1$ ，因为 $1,2,3,\cdots,n-1$ 都不被 n 整除，所以这些数都与 n 互素。

情况3

如果 p 为素数，n 是 p 的正整数次方，那么 $\varphi(p^k)=p^k(1-\frac{1}{p})$ ，证明如下：

考虑满足 $1 \le m \le p^k$ 的正整数 m，如果 $(m,p^k)=1$，必有 $m \nmid p$ ，否则 $m \mid p$ ，故 $m \mid p^k$ ，矛盾。

同样，如果 $m \nmid p$ ，那么 $(m,p)=1$ （因为 p 是素数），所以 $(m,p^k)=1$ 。

这就说明，与 $p^k$ 互素的数与不整除 p 的数一一对应。而 $1,2,3,\cdots,p^k$ 这 $p^k$ 个数中，p 的倍数只有 $p,2p,3p,\cdots,p^{k-1}\cdot p$ 这 $p^{k-1}$ 个数，所以 $\varphi(p^k)=p^k-p^{k-1}=p^k(1-\frac{1}{p})$ 。

欧拉函数的积性

“积性”指的是对于互素的 m, n，函数 $f(x)$ 满足 $f(mn)=f(m)\cdot f(n)$ 。欧拉函数是积性函数。（但是积性不对全体自然数成立。）

我们有这样的引理：对于 $(m,n)=1$ ，欧拉函数满足 $\varphi(mn)=\varphi(m)\cdot\varphi(n)$ ，证明如下：

（这是来自Faithfully(CSDN)的一个很有意思的证法）

构造 $m\times n$ 的一个数阵：

$\begin{array}{ccccc} 1 & 2 & \cdots & r & \cdots & m \\ m+1 & m+2 & \cdots & m+r & \cdots & 2m\\ 2m+1 & 2m+2 & \cdots & 2m+r & \cdots & 3m\\ \vdots & \vdots & & \vdots & & \vdots \\ (n-1)m+1 & (n-1)m+2 & \cdots & (n-1)m+r & \cdots & nm \end{array}\\$

可以看到，每一行都是 m 的一个完全剩余系，每一列都是 n 的一个完全剩余系。（这是因为如果某一列不是 n 的完全剩余系，那么一定存在两个元素模 n 同余，那么在同余式两边减去这一列的第一个数，再根据 (m, n)=1 消去同余式两边的 m，得到一个矛盾的结论。我说的比较抽象，这里动笔算一下，结果很容易得到。）

这样，在第一行能找出 m 的一个欧拉剩余系，记作 $c_1,c_2,c_3,\cdots,c_{\varphi(m)}$ 。根据裴蜀定理，对于 $c_k$ 存在整数 x, y 满足 $xc_k+ym=1$ ，那么对于 $am+c_k$ ，有 $x(am+c_k)+(y-ax)m=1$ ，而 x 与 y-ax 都是整数，这说明 $c_k$ 所在的这一列都与 m 互素。

同时，在每一列我们都能找到 n 的一个欧拉剩余系。所以，在数阵中可以找到 $\varphi(m)$ 列，其中每一列都有 $\varphi(n)$ 个元素同时和 m 与 n 互素，这一共是 $\varphi(m)\cdot\varphi(n)$ 个元素。接下来，我们证明“同时和 m 与 n 互素”等价于“和 mn 互素”。

如果 $(a,n)=(a,m)=1$ ，肯定有 $(a,mn)=1$ 。

如果 $(a,mn)=1$ ，那么存在整数 x, y 使 $xa+ymn=1$ 。由于 x 和 yn 也是整数，所以 $(a,m)=1$ ，同理 $(a,n)=1$ 。

现在观察这个数阵，可以发现里面包含了 $1,2,3,\cdots,mn$ 这 mn 个数。所以我们刚才找到的 $\varphi(m)\cdot\varphi(n)$ 个元素就是前 mn 个正整数中与 mn 互素的全部整数。所以 $\varphi(mn)=\varphi(m)\cdot\varphi(n)$ ，证毕。

情况4

对于任意正整数 n ，构造 n 的标准分解： $n=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\cdots p_k^{\alpha_k}$ ，其中 $p_1,p_2,p_3,\cdots,p_k$ 均为素数。根据欧拉函数的积性，同时注意到 $p_1^{\alpha_1},p_2^{\alpha_2},p_3^{\alpha_3},\cdots,p_k^{\alpha_k}$ 两两互素，所以有

$\begin{align} \varphi(n)&=\varphi(p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\cdots p_k^{\alpha_k})\\[1em] &=\varphi(p_1^{\alpha_1}) \varphi(p_2^{\alpha_2}) \varphi(p_3^{\alpha_3})\cdots \varphi(p_k^{\alpha_k})\\[1em] &=p_1^{\alpha_1}(1-\frac{1}{p_1})p_2^{\alpha_2}(1-\frac{1}{p_2})p_3^{\alpha_3}(1-\frac{1}{p_3})\cdots p_k^{\alpha_k}(1-\frac{1}{p_k})\\[0.5em] &=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})\cdots(1-\frac{1}{p_k}) \end{align}\\$

证毕。

欧拉函数还有另一种计算形式：

$\bbox[#C0FFFF,5px,border:2px solid #90A0FF]{ \varphi(n)=p_1^{\alpha_1-1}(p_1-1)p_2^{\alpha_2-1}(p_2-1)p_3^{\alpha_3-1}(p_3-1)\cdots p_k^{\alpha_k-1}(p_k-1) }\\$

根据上面的情况4不难证明，这里不再赘述。