欧拉函数的计算式

---

欧拉函数

对于正整数 $n$ ，欧拉函数 $\phi (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{array}{l}1,p(k)\\ 0,\neg p(k)\end{array}$ 。

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

\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 时，显然 $\phi (0)=0$ ，因为 n = 0 时，欧拉函数的计算范围内只有 0，但是 (0, 0) = 0。

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

情况2

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

情况3

如果 p 为素数，n 是 p 的正整数次方，那么 $\phi (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}$ 个数，所以 $\phi (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$ ，欧拉函数满足 $\phi (mn)=\phi (m)\cdot \phi (n)$ ，证明如下：

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

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

$\begin{array}{cccccc}1& 2& \cdots & r& \cdots & m\\ m+1& m+2& \cdots & m+r& \cdots & 2m\\ 2m+1& 2m+2& \cdots & 2m+r& \cdots & 3m\\ ⋮& ⋮& & ⋮& & ⋮\\ (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_{\phi (m)}$ 。根据裴蜀定理，对于 $c_k$ 存在整数 x, y 满足 $x{c}_k+ym=1$ ，那么对于 $am+c_k$ ，有 $x(am+c_k)+(y-ax)m=1$ ，而 x 与 y-ax 都是整数，这说明 $c_k$ 所在的这一列都与 m 互素。

同时，在每一列我们都能找到 n 的一个欧拉剩余系。所以，在数阵中可以找到 $\phi (m)$ 列，其中每一列都有 $\phi (n)$ 个元素同时和 m 与 n 互素，这一共是 $\phi (m)\cdot \phi (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 个数。所以我们刚才找到的 $\phi (m)\cdot \phi (n)$ 个元素就是前 mn 个正整数中与 mn 互素的全部整数。所以 $\phi (mn)=\phi (m)\cdot \phi (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不难证明，这里不再赘述。