欧拉函数公式证明
定义
欧拉函数φ(n)\varphi(n)φ(n)表示小于等于nnn且与nnn互质(gcd(x,n)=1)(gcd(x,n)=1)(gcd(x,n)=1)的数的个数
公式
φ(n)=n×(∏pi∣m,pi是质数pi−1pi)\varphi(n)=n\times (\prod\limits_{p_i|m,p_i是质数}\frac{p_i-1}{p_i})φ(n)=n×(pi∣m,pi是质数∏pipi−1)
推导
一些显而易见或者易证明的性质
- φ(p)=p−1,p是质数\varphi(p)=p-1,p是质数φ(p)=p−1,p是质数
- φ(pq)=φ(p)×φ(q)=(p−1)×(q−1),p,q均是质数\varphi(pq)=\varphi(p)\times \varphi(q)=(p-1)\times(q-1),p,q均是质数φ(pq)=φ(p)×φ(q)=(p−1)×(q−1),p,q均是质数
a. 直观理解，[1,pq][1,pq][1,pq]内与pqpqpq互质的数等于[1,p][1,p][1,p]内与ppp互质的数以及[1,q][1,q][1,q]内与qqq互质的数乘积
b. 从积性函数方向理解，欧拉函数是积性函数，所以有φ(pq)=φ(p)×φ(q)\varphi(pq)=\varphi(p)\times\varphi(q)φ(pq)=φ(p)×φ(q) - 对nnn分解质因子，n=p1k1p2k2…pmkm=∏i=1mpikin=p_1^{k_1}p_2^{k_2}\dots p_m^{k_m}=\prod\limits_{i=1}^{m}p_i^{k_i}n=p1k1p2k2…pmkm=i=1∏mpiki，其中 pip_ipi两两互质，所以pikip_i^{k_i}piki两两互质
a. 直观理解，[1,n][1,n][1,n]内与nnn互质的数所有[1,piki][1,p_i^{k_i}][1,piki]内与pikip_i^{k_i}piki互质的数的乘积
b. 从积性函数方向理解，φ(n)=∏i=1mφ(piki)\varphi(n)=\prod\limits_{i=1}^{m}\varphi(p_i^{k_i})φ(n)=i=1∏mφ(piki) - φ(pk)=(p−1)(pk−1)\varphi(p^k)=(p-1)(p^{k-1})φ(pk)=(p−1)(pk−1)
a. 因为[1,pk][1,p^k][1,pk]内与ppp不互质的数为 1×p,2×p,…,(pk−1)×p1\times p, 2\times p, \dots, (p^{k-1}) \times p1×p,2×p,…,(pk−1)×p，共pk−1p^{k-1}pk−1个
b. 那么 [1,pk][1,p^k][1,pk]内与ppp互质的数有pk−pk−1=(p−1)×(pk−1)p^k-p^{k-1}=(p-1)\times (p^{k-1})pk−pk−1=(p−1)×(pk−1)
欧拉函数公式证明
对于一个正整数nnn：
由性质333，对nnn分解质因子，n=p1k1p2k2…pmkm=∏i=1mpikin=p_1^{k_1}p_2^{k_2}\dots p_m^{k_m}=\prod\limits_{i=1}^{m}p_i^{k_i}n=p1k1p2k2…pmkm=i=1∏mpiki
由性质444，
φ(n)=∏i=1mφ(piki)=∏i=1m(pi−1)(piki−1)=∏i=1mpi−1pipiki=(∏i=1mpiki)×(∏i=1mpi−1pi)=n×(∏i=1mpi−1pi)\varphi(n)=\prod\limits_{i=1}^{m}\varphi(p_i^{k_i})\\ =\prod\limits_{i=1}^{m}(p_i-1)(p_i^{k_i-1})\\ =\prod\limits_{i=1}^{m}\frac{p_i-1}{p_i}p_i^{k_i}\\=(\prod\limits_{i=1}^{m}p_i^{k_i})\times(\prod\limits_{i=1}^{m}\frac{p_i-1}{p_i})\\=n\times (\prod\limits_{i=1}^{m}\frac{p_i-1}{p_i})φ(n)=i=1∏mφ(piki)=i=1∏m(pi−1)(piki−1)=i=1∏mpipi−1piki=(i=1∏mpiki)×(i=1∏mpipi−1)=n×(i=1∏mpipi−1)
故φ(n)=n×(∏i=1mpi−1pi)\varphi(n)=n\times (\prod\limits_{i=1}^{m}\frac{p_i-1}{p_i})φ(n)=n×(i=1∏mpipi−1)，得证