欧拉函数的计算式-欧拉函数怎么算

 

欧拉函数

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

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

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

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

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

φ(n)=n(1−1p1)(1−1p2)(1−1p3)⋯(1−1pk)\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}) }\\

其中 p1,p2,p3,⋯,pkp_1,p_2,p_3,\cdots,p_k 是 nn 的所有不重复的素因子。

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

情况1

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

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

情况2

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

情况3

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

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

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

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

欧拉函数的积性

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

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

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

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

12⋯r⋯mm+1m+2⋯m+r⋯2m2m+12m+2⋯2m+r⋯3m⋮⋮⋮⋮(n−1)m+1(n−1)m+2⋯(n−1)m+r⋯nm\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 的一个欧拉剩余系，记作 c1,c2,c3,⋯,cφ(m)c_1,c_2,c_3,\cdots,c_{\varphi(m)} 。根据裴蜀定理，对于 ckc_k 存在整数 x, y 满足 xck+ym=1xc_k+ym=1 ，那么对于 am+ckam+c_k ，有 x(am+ck)+(y−ax)m=1x(am+c_k)+(y-ax)m=1 ，而 x 与 y-ax 都是整数，这说明 ckc_k 所在的这一列都与 m 互素。

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

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

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

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

情况4

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

φ(n)=φ(p1α1p2α2p3α3⋯pkαk)=φ(p1α1)φ(p2α2)φ(p3α3)⋯φ(pkαk)=p1α1(1−1p1)p2α2(1−1p2)p3α3(1−1p3)⋯pkαk(1−1pk)=n(1−1p1)(1−1p2)(1−1p3)⋯(1−1pk)\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}\\

证毕。

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

φ(n)=p1α1−1(p1−1)p2α2−1(p2−1)p3α3−1(p3−1)⋯pkαk−1(pk−1)\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不难证明，这里不再赘述。

封面PID：67574807。（实在找不到适合的封面了，就放张北斋，祝大家新年快乐吧~）