To boldly go where no one has gone before.

【学习笔记】欧拉函数

2019-10-03 12:23:59


定义

欧拉函数$\varphi(n)$:表示$[1,n)$内与$n$互质的数的个数。

性质

性质1

对于素数,很明显有$$\varphi(n)=n-1$$

性质2

$$\varphi(p^k)=p^k-p^{k-1}\;\;(p\text{为质数})$$ 证明: 由于$p$是质数,所以只要一个数的因数不含$p$,那么这个数就和$p$互质。在$[1,p^k)$内,这样的数也就是$p^1,p^2,\cdots,p^{k-1},$总共有$p^{k-1}$个。因此只要将这些数去除,剩下的数都和$p^k$互质。

性质3

若$n=p_1\cdot p_2\;\;(p_1,p_2\text{为质数})$,则有:$$\varphi(n)=\varphi(p_1)\cdot\varphi(p_2)$$ 证明: 由于$p_1,p_2$是质数,所以在$[1,n)$中,只有$p_1$和$p_2$的倍数与$n$非互质。而$p_1$的倍数共有$p_2-1$个,$p_2$的倍数共有$p_1-1$个,所以有:$$\varphi(n)=p_1\cdot p_2-1-(p_1-1)-(p_2-1)$$$$=p_1\cdot p_2-p_1-p_2+1=(p_1-1)\cdot(p_2-1)$$ 由性质1可得:$$\varphi(n)=\varphi(p_1)\cdot\varphi(p_2)$$

性质4

设$n=p_1^{k_1}\cdot p_2^{k_2}\cdot \cdots\cdot p_s^{k_s}$,则$$\varphi(n)=n\cdot\prod_{i=1}^s(1-\frac 1{p_i})$$ 证明: 首先将性质2改写成:$$\varphi(p^k)=p^k(1-\frac 1p)$$ 然后用性质3将$\varphi(n)$展开,可得:$$\varphi(n)=\prod_{i=1}^s \varphi(p_i^{k_i})=\prod_{i=1}^s p_i^{k_i}\cdot \prod_{i=1}^s (1-\frac 1{p_i})=n\cdot\prod_{i=1}^s (1-\frac 1{p_i})$$

性质5

若$n$为奇数,则有:$$\varphi(2n)=\varphi(n)$$ 证明: 运用性质3展开即可。

性质6

当$a,n\;(n>2)$互质,有:$$a^{\varphi(n)}\equiv1\,(\mod n)$$ 证明: 我不知道,背结论就好。

拓展

当$n=p$且$p$为质数,有:$$a^{\varphi(p)}=a^{p-1}\equiv1\,(\mod p)$$ 该式即费马小定理

求法

单个数的求法

枚举质因数即可,复杂度$O(\sqrt{n})$,代码略。

递推求法

运用性质4,以及欧拉筛的思路进行递推。

void euler() {
    for (int i = 2; i < MAXN; i++)
        if (!phi[i])
            for (int j = i; j < MAXN; j += i) {
                if(!phi[j])
                    phi[j] = j;
                phi[j] = phi[j] / i * (i - 1);  
            }
}