欧拉函数证明

给定任意正整数 $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$ 的时间复杂度内求出一个数的欧拉函数值。

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

欧拉函数线性筛

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

const int MAXN = 1e6;
//欧拉线性筛：在线性时间内筛素数的同时求出所有数的欧拉函数
int tot;
int phi[MAXN]; //保存各个数字的欧拉函数
int prime[MAXN]; //按顺序保存素数
bool mark[MAXN]; //判断是否是素数
void get_phi(int N){
    phi[1] = 1;
    for(int i = 2; i <= MAXN; i++){ //相当于分解质因数的逆过程
        if(!mark[i]){
            prime[++tot] = i;
            phi[i] = i-1;
        }
        for(int j = 1; j <= tot; j++){
            if(i * prime[j] > N) break;
            mark[i * prime[j]] = 1; //确定i*prime[j]不是素数
            if(i % prime[j] == 0){ //判断prime[j] 是否为 i的约数
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else{ //prime[j] - 1 就是 phi[prime[j]],利用了欧拉函数的积性
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            }
        }
    }
}