欧拉函数证明

给定任意正整数 $_math_inline$n$math_inline_$ ，那么在小于等于 $_math_inline$n$math_inline_$ 的所有正整数之中，有多少个与 $_math_inline$n$math_inline_$ 构成互质关系？

计算这个值的方法就叫做欧拉函数 $_math_inline$\phi(n)$math_inline_$ 表示：在 $_math_inline$1$math_inline_$ 到 $_math_inline$n$math_inline_$ 之中，与n构成互质关系的数的数量。

分析

情况一

如果 $_math_inline$n=1$math_inline_$ ，则 $_math_inline$\phi(1)=1$math_inline_$ 。因为1与任何数（包括自身）都构成互质关系

情况二

如果 $_math_inline$n$math_inline_$ 是质数，则 $_math_inline$\phi(n)=n-1$math_inline_$ 。因为质数与小于它的每一个数，都构成互质关系。比如 $_math_inline$5$math_inline_$ 与 $_math_inline$1、2、3、4$math_inline_$ 都构成互质关系。

情况三

如果 $_math_inline$n$math_inline_$ 是质数的某一个次方，即 $_math_inline$n=p^k$math_inline_$ （ $_math_inline$p$math_inline_$ 为质数， $_math_inline$k$math_inline_$ 为大于等于 $_math_inline$1$math_inline_$ 的整数），则 $_math_inline$\phi(p^k)=p^k-p^{k-1}$math_inline_$

比如 $_math_inline$\phi(8)=\phi(2^3)=2^3-2^2=8-4=4$math_inline_$

这是因为只有当一个数不包含质数 $_math_inline$p$math_inline_$ ，才有可能与 $_math_inline$n$math_inline_$ 互质。而包含质数 $_math_inline$p$math_inline_$ 的数一共有 $_math_inline$p^{k-1}$math_inline_$ 个。

即 $_math_inline$1\times p、2\times p、3\times p、... 、p^{k-1}\times p$math_inline_$ ，把他们去除，剩下的就是与 $_math_inline$n$math_inline_$ 互质的数。

上面的式子还可以写成下面的形式：

可以看出，上面的第二种情况是 $_math_inline$k=1$math_inline_$ 时的特例

情况四

如果n可以分解成两个互质的整数之积： $_math_inline$n=p_1\times p_2$math_inline_$

则： $_math_inline$\phi(n)=\phi(p_1p_2)=\phi(p_1)\phi(p_2)$math_inline_$

即积的欧拉函数等于各个因子的欧拉函数之积。比如 $_math_inline$\phi(56)=\phi(8\times 7)=\phi(8)\phi(7)=4\times 6=24$math_inline_$

对于素数 $_math_inline$p$math_inline_$ ， $_math_inline$\phi(p)=p-1$math_inline_$ ，对于两个素数 $_math_inline$p,q$math_inline_$ ， $_math_inline$\phi(pq)=pq-1$math_inline_$

欧拉函数是积性函数，但不是完全积性函数

欧拉函数的积性

若 $_math_inline$m,n$math_inline_$ 互质，则 $_math_inline$\phi(mn)=\phi(m)\phi(n)$math_inline_$ 。

由“ $_math_inline$m,n$math_inline_$ 互质”可知 $_math_inline$m,n$math_inline_$ 无公因数，所以：

其中 $_math_inline$p_1、p_2、p_3...p_n$math_inline_$ 为 $_math_inline$m$math_inline_$ 的质因数， $_math_inline$p_1'、p_2'、p_3'...p_n'$math_inline_$ 为 $_math_inline$n$math_inline_$ 的质因数，而 $_math_inline$m,n$math_inline_$ 无公因数。

所以 $_math_inline$p_1、p_2、p_3...p_n、p_1'、p_2'、p_3'...p_n$math_inline_$ 互不相同，所以 $_math_inline$p_1、p_2、p_3...p_n、p_1'、p_2'、p_3'...p_n$math_inline_$ 均为 $_math_inline$mn$math_inline_$ 的质因数且为 $_math_inline$mn$math_inline_$ 的质因数的全集。

所以 $_math_inline$\phi(mn)=mn(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})...(1-\frac{1}{p_n})\cdot (1-\frac{1}{p_1'})(1-\frac{1}{p_2'})(1-\frac{1}{p_3'})...(1-\frac{1}{p_n'})$math_inline_$

所以 $_math_inline$\phi(mn)=\phi(m)\phi(n)$math_inline_$ 。

以上部分涉及到“中国剩余定理”

情况五

因为任意一个大于1的正整数，都可以写成一系列质数的积。（分解质因数）

根据结论四，得到

再根据结论三，得到

也就等于

结论

比如 $_math_inline$\phi(1323)=(3^3\times 7^2)=1323(1-\frac{1}{3})(1-\frac{1}{7})=756$math_inline_$

即 $_math_inline$\phi(mn)=\phi(n)\phi(m)$math_inline_$ 只在 $_math_inline$(m,n)=1$math_inline_$ 时成立。

对于一个正整数 $_math_inline$N$math_inline_$ 的素数幂分解 $_math_inline$N=p_1^{q_1}p_2^{q_2}...p_n^{q_n}$math_inline_$

除了 $_math_inline$N=2, \phi(N)$math_inline_$ 都是偶数

设 $_math_inline$N$math_inline_$ 为正整数， $_math_inline$\sum{\phi(d)}=N(d|N)$math_inline_$

欧拉函数

根据性质二，我们可以在 $_math_inline$O(\sqrt{n})$math_inline_$ 的时间复杂度内求出一个数的欧拉函数值。

 1//直接求解欧拉函数  
 2int euler(int n) { //返回euler(n)   
 3    int res = n, a = n;
 4    for (int i = 2; i * i <= a; i++) {
 5        if (a % i == 0) {
 6            res = res / i * (i - 1);//先进行除法是为了防止中间数据的溢出   
 7            while (a % i == 0) a /= i;
 8        }
 9    }
10    if (a > 1) res = res / a * (a - 1);
11    return res;
12}

欧拉函数线性筛

如果要求 $_math_inline$N$math_inline_$ 以内的所有数的欧拉函数 $_math_inline$O(n)$math_inline_$

 1const int MAXN = 1e6;
 2//欧拉线性筛：在线性时间内筛素数的同时求出所有数的欧拉函数
 3int tot;
 4int phi[MAXN]; //保存各个数字的欧拉函数
 5int prime[MAXN]; //按顺序保存素数
 6bool mark[MAXN]; //判断是否是素数
 7void get_phi(int N){
 8    phi[1] = 1;
 9    for(int i = 2; i <= MAXN; i++){ //相当于分解质因数的逆过程
10        if(!mark[i]){
11            prime[++tot] = i;
12            phi[i] = i-1;
13        }
14        for(int j = 1; j <= tot; j++){
15            if(i * prime[j] > N) break;
16            mark[i * prime[j]] = 1; //确定i*prime[j]不是素数
17            if(i % prime[j] == 0){ //判断prime[j] 是否为 i的约数
18                phi[i * prime[j]] = phi[i] * prime[j];
19                break;
20            }
21            else{ //prime[j] - 1 就是 phi[prime[j]],利用了欧拉函数的积性
22                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
23            }
24        }
25    }
26}