欧拉函数学习笔记

定义：对于正整数 $n$n，欧拉函数是小于等于 $n$n的数中与 $n$n互质的数的个数。

符号： $\phi \left(n\right)$φ(n)表示 $n$n的欧拉函数，默认 $\phi \left(1\right)=1$φ(1)=1。

一些定理：

1.对于一个素数 $p$p， $\phi \left(p\right)=p-1$φ(p)=p−1。

证明略。

2.对于两个互质的数 $a,b$a,b， $\phi (a\times b)=\phi \left(a\right)\times \phi \left(b\right)$φ(a×b)=φ(a)×φ(b)。 $($(感谢 $hyj$hyj 巨佬的指正 $)$)

证明：因为 $a$a与 $b$b互质，所以 $a$a与 $b$b没有共同的质因数。设 $a$a有 $k_a$ka​个质因数， $b$b有 $k_b$kb​个质因数，因此：
$\begin{array}{cc}{\displaystyle \phi \left(a\right)\ast \phi \left(b\right)}& {\displaystyle =a\ast \prod _{i=1}^{k_a}(1-\frac{1}{p\left[i\right]})\ast b\ast \prod _{i=1}^{k_b}(1-\frac{1}{p\left[i\right]})}\\ {\displaystyle }& {\displaystyle =a\ast b\ast \prod _{i=1}^{k_a+k_b}(1-\frac{1}{p\left[i\right]})}\\ {\displaystyle }& {\displaystyle =\phi (a\ast b)}\end{array}$φ(a)∗φ(b)​=a∗i=1∏ka​​(1−p[i]1​)∗b∗i=1∏kb​​(1−p[i]1​)=a∗b∗i=1∏ka​+kb​​(1−p[i]1​)=φ(a∗b)​
注：欧拉函数是积性函数，但不是完全积性函数。

$update$update：这个证法貌似是错的，因为要用到欧拉函数的公式，但是欧拉函数的公式又要由这个式子推出来。所以只能显然正确了。真的证明我还不会 $($(我菜爆了 $)$)，可以参考这里

3.对于一个素数 $p$p的幂次，如 $p^a$pa，有 $\phi \left(p^a\right)$φ(pa) $=$= $(p-1)$(p−1) $\times$× $p^{a-1}$pa−1。

证明：比 $p^a$pa小的正整数共 $p^a-1$pa−1个。其中所有 $p$p的倍数可以表示成 $p$p $\times$× $t$t $(t=1,\mathrm{2......}{p}^{a-1}-1)$(t=1,2......pa−1−1)，即共有 $p^{a-1}-1$pa−1−1个数能被 $p$p整除。因为 $p$p是质数，所以显然只有这些数不能被 $p$p整除，剩余的数都与 $p$p互质。因此， $\phi \left(p^a\right)$φ(pa) $=$= $p^a-1$pa−1 $-$− $(p^{a-1}-1)$(pa−1−1) $=$= $(p-1)$(p−1) $\times$× $p^{a-1}$pa−1。

4.如果 $i\%p=0$i%p=0，那么 $\phi (i\times p)=\phi \left(i\right)\times p$φ(i×p)=φ(i)×p。

证明：懒了不想写，好像没多大用。

求欧拉函数：

1.求单个欧拉函数： $\phi \left(x\right)$φ(x) $=x$=x $\times$× ${\prod }_{i=1}^k(1-\frac{1}{p\left[i\right]})$i=1∏k​(1−p[i]1​)

其中 $p\left[1\right],p\left[2\right]......p\left[k\right]$p[1],p[2]......p[k]为 $x$x的所有质因子

证明：首先，由整数的唯一分解定理可得， $x$x $=$= $p[1{]}^{a_1}$p[1]a1​ $\times$× $p[2{]}^{a_2}$p[2]a2​ $\times$× $......$...... $\times$× $p[k{]}^{a_k}$p[k]ak​。显然 $p[1{]}^{a_1}$p[1]a1​， $p[2{]}^{a_2}$p[2]a2​， $......$......， $p[k{]}^{a_k}$p[k]ak​之间两两互质。那么，根据定理 $2,3$2,3：
$\begin{array}{cc}{\displaystyle \phi \left(x\right)}& {\displaystyle =\phi \left(p\right[1{]}^{a_1})\ast \phi (p\left[2{]}^{a_2}\right)\ast ......\ast \phi \left(p\right[k{]}^{a_k})}\\ {\displaystyle }& {\displaystyle =\left(p\right[1{]}^{a_1}\ast (1-\frac{1}{p\left[1\right]}))\ast (p[2{]}^{a_2}\ast (1-\frac{1}{p\left[2\right]}\left)\right)\ast ......\ast \left(p\right[k{]}^{a_k}\ast (1-\frac{1}{p\left[k\right]}))}\\ {\displaystyle }& {\displaystyle =\left(p\right[1{]}^{a_1}\ast p[2{]}^{a_2}\ast ......\ast p[k{]}^{a_k})\ast (1-\frac{1}{p\left[1\right]})\ast (1-\frac{1}{p\left[2\right]})\ast ......\ast (1-\frac{1}{p\left[k\right]})}\\ {\displaystyle }& {\displaystyle =x\ast \prod _{i=1}^k(1-\frac{1}{p\left[i\right]})}\end{array}$φ(x)​=φ(p[1]a1​)∗φ(p[2]a2​)∗......∗φ(p[k]ak​)=(p[1]a1​∗(1−p[1]1​))∗(p[2]a2​∗(1−p[2]1​))∗......∗(p[k]ak​∗(1−p[k]1​))=(p[1]a1​∗p[2]a2​∗......∗p[k]ak​)∗(1−p[1]1​)∗(1−p[2]1​)∗......∗(1−p[k]1​)=x∗i=1∏k​(1−p[i]1​)​
代码：

inline int getphi(int x){
    int res=x;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            res=res/i*(i-1);//通分公式大括号内内容即可
            while(x%i==0) x/=i; 
        }
    }
    if(x>1) res=res/x*(x-1);
    return res;
}

2.线性筛欧拉函数：方法类似于筛素数，其实并不难，在筛素数的同时进行筛欧拉函数。

用到上面的1，2，4定理。

代码：

for(int i=2;i<=n;i++){
    if(!v[i]){
        phi[i]=i-1;
        pr[++top]=i;
    }
    for(int j=1;j<=top&&i*pr[j]<=n;j++){
        v[i*pr[j]]=1;
        if(i%pr[j]==0){
            phi[i*pr[j]]=phi[i]*pr[j];
            break;
        }
        else phi[i*pr[j]]=phi[i]*phi[pr[j]];
    }
}

欧拉定理：若 $gcd(a,m)=1$gcd(a,m)=1​，那么 $a^{\phi \left(m\right)}$aφ(m)​ $\equiv$≡​ $1\left(modm\right)$1(modm)​。

证明：找欧拉去