CSP-S数学知识总结 之 欧拉定理

---

定义

---

欧拉函数：对正整数\(n\)，欧拉函数是小于等于\(n\)的数中与\(n\)互质的数的数目，记为\(\varphi(n)\)。

欧拉定理：若\(a\)与\(m\)互质，则\(a^{\varphi(m)}\equiv 1 (mod \ m)\)

欧拉函数通项公式：

设 \(w\)为\(n\)的质因子个数，\(p_i\)为\(n\)的各个质因子
\[ \varphi(n)=n\prod_{i = 1}^{w}(1-\frac{1}{p_i}) \]
证明：
\[ 大体证明一下\\ 显然，对于每个质因子p_i,有\frac{n}{p_i}个数不与n互质\\ 然而，对于每对质因子p_i,p_j,都有\frac{n}{p_ip_j}个数被重复计算1次\\ 同时，对于每三个质因子p_i,p_j,p_k,都有\frac{n}{p_ip_jp_k}个数被重复计算2次\\ ……\\ 以此类推,不难发现，这其实是个容斥\\ \therefore \varphi(n)=n-\sum{\frac{n}{p_i}}+\sum{\frac{n}{p_ip_j}}-\sum{\frac{n}{p_ip_jp_k}}-\cdots+\sum{\frac{n}{p_ip_j\cdots p_w}}\\ \therefore \varphi(n)=n-n\sum{\frac{1}{p_i}}+n\sum{\frac{1}{p_ip_j}}-n\sum{\frac{1}{p_ip_jp_k}}-\cdots+n\sum{\frac{1}{p_ip_j\cdots p_w}}\\ \therefore \varphi(n)=n(1-\sum{\frac{1}{p_i}}+\sum{\frac{1}{p_ip_j}}-\sum{\frac{1}{p_ip_jp_k}}-\cdots+\sum{\frac{1}{p_ip_j\cdots p_w}})\\ ……\\ 最终因式分解得\\ \varphi(n)=n\prod_{i = 1}^{w}(1-\frac{1}{p_i})\\ \]
证毕。

额，证明的有点草率

引理

---

(1)如果\(n\)为素数，则\(\varphi(n) = n - 1\)

(2)如果\(n\)为某个素数\(p\)的\(a\)次幂\(p^a\)，则\(\varphi(p^a)=(p-1)*p^{a-1}\)

(3)如果\(n\)为某两个互质的数\(a\)，\(b\)的积，则\(\varphi(a*b)=\varphi(a)*\varphi(b)\)

证明：

​ (1)显然一个质数，所有小于它的数，都与它互质。

​ (2)
\[ \because比p_a小的正整数有p^{a-1}个，其中能被p整除的数可以表示为p*t(t\in N^*,t\lt q^{a-1}).\\ \therefore 共有p^{a-1}个数能被p整除，从而不与p^a互质\\ \because当t = p^a时,p*t=p^a\\ \therefore t只能取到p^{a-1}-1\\ \therefore \varphi(q^a)=p^a-1-(p^{a-1}-1)=p^a-p^{a-1}=(p-1)*p^{a-1}\\ \]
​ (3)
\[ 在比a*b小的整数中，由定义式得：\\ \varphi(a) = a\prod(1-\frac{1}{p_{a_i}})\\ \varphi(b) = b\prod(1-\frac{1}{p_{b_i}})\\ \because a的质因子或b的质因子一定是a*b的质因子\\ \therefore \varphi(a)*\varphi(b)=ab\prod(1-\frac{1}{p_{ab_i}})=\varphi(a*b)\\ \]
证毕。

推论

---

（敲小黑板划重点）

欧拉定理的推论：若\(a,p\in N^*\)互质，则\(\forall b \in N^*\)有\(a^b \equiv a^{b \ mod\ \varphi(p)}\ (mod\ p)\)

证明：
\[ 设b=q*\varphi(p)+r\ (r\in[1,\varphi(p)],即r = b\ mod\ \varphi(p)\\ 则有:a^b\equiv a^{q*\varphi(p)+r}\equiv (a^{\varphi(p)})^q*a^r\equiv 1^a*a^r\equiv a^r\equiv a^{b\ mod\ \varphi(p)}\\ \]
证毕。

那么，这个推论为什么重要呢，在面对乘方算式取模的时候，总不能把它分解成乘法算式然后一步一步的取模吧，这时就要用到欧拉定理的推论了，我们只需把底数对\(p\)取模，把指数对\(\varphi(p)\)取模即可。

求欧拉函数

---

那么既然欧拉函数这么好用，我们怎么求呢

1.首先，如果使用的欧拉函数个数较少，可以直接分解质因子，然后套通项公式求欧拉函数即可

(分解质因子的代码实现参考：数学知识总结 之 质数)

2.当需要大量使用欧拉函数的时候，就需要使用筛法来预处理欧拉函数(打表)

最常用的是欧拉筛线性筛出欧拉函数的表

int prime[MAXN],phi[MAXN];
int cnt;
void getphi(){
    prime[1] = 1;
    for(int i = 1; i <= MAXN; i++){
        if(!phi[i]){
            cnt++;
            phi[i] = i - 1;
            prime[cnt] = i;
        }
        for(int j= 1; j <= cnt; j++){
            if(i*prime[j]>MAXN){
                break;
            }
            if(!(i%prime[j])){
                phi[i*prime[j]] = phi[i]*prime[j];
                  }
            else{
                phi[i*prime[j]] = phi[i]*(prime[j]-1);
            }
        }
    }
}