参考https://www.jianshu.com/p/8a27f0462d09

对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）

---

 

φ函数的值：

φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n)) 其中p(1),p(2)…p(n)为x的所有质因数;x是正整数; φ(1)=1(唯一和1互质的数，且小于等于1)。注意：每种质因数只有一个。

例如:

φ(10)=10×(1-1/2)×(1-1/5)=4;

1 3 7 9

φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;

φ(49)=49×(1-1/7)=42;

欧拉函数的性质：

(1) p^k型欧拉函数:

若N是质数p(即N=p),φ(n)= φ(p)=p(1-1/p)=p-1。 所以除了p自己本身外,[1,p-1]的任何数都与p互质,所以φ(p)=p-1,另外由公式得到φ(n)= φ(p)=p(1-1/p)=p-1。

若N是质数p的k次幂(即N=p^k)， φ(n)= p^ k -p^(k-1) =(p-1)p^(k-1)。y因为除了p的倍数以外,其他数都与N互质。而是p的倍数的数有p,2p,3p...p^(k-1)*p,一共有p ^ ( k- 1)个,所以有p^k -p ^ (k-1) =(p-1)p^(k-1)个数与p互质。

(2)mn型欧拉函数

设m,n为正整数,若m,n互质，φ(mn)=(m-1)(n-1)=φ(m)φ(n)。容易知道mn与m的倍数或者n的倍数不互质,而n的倍数有n,2n,3n...mn,共有m个,m的倍数有m,2m,3m...nm,共有n个,又mn重复计数,所以共有n+m-1个,至于k1*n和k2*m中会不会有重复计数呢?因为n,m为质数,要使得k1n=k2m,那么k1=n,k2=m;所以与mn互质的有m*n-(n+m-1)=(m-1)*(n-1)=φ(m)φ(n)

(3)特殊性质:

若n为奇数时，φ(2n)=φ(n)。因为n为奇数，与n互质的即也与2n互质

对于任何两个互质 的正整数a,n(n>2)有:a^φ(n)=1 mod n (恒等于)此公式即 欧拉定理，a本来就与n互质，即使乘个φ(n)次也与n互质

当n=p 且 a与素数p互质(即:gcd(a,p)=1)则上式有: a^(p-1)=1 mod p (恒等于)此公式即 费马小定理

如果(a,c)互质，且c是素数，则（a ^ b）%c=a ^ ( b % ( phi(c) ) )%c ， phi(c) 是指c的欧拉函数，详见https://blog.csdn.net/doyouseeman/article/details/51863382

四 欧拉函数的延伸:

( 一 )

小于或等于n的数中，与n互质的数的总和为：φ(n) * n / 2 (n>1)。详见https://www.cnblogs.com/cchun/archive/2012/07/16/2593980.html

根据扩欧：若i与n互质则gcd（i，n）=1 -> gcd（n-i，i）=1

反证法：

         如果存在K!=1使gcd(n,n-i)=k,那么(n-i)%k==0

         而n%k=0

         那么必须保证i%k=0

         k是n的因子,如果i%k=0那么 gcd(n,i)=k,矛盾出现;

         于是问题变的非常简单： ANS=N*phi(N)/2

         i,n-i总是成对出现，并且和是n

        于是可能就有人问了，如果存在n-i=i那不是重复计算？

         答案是不会

         因为:

                 n=2*i->i=n/2

         1.如果n是奇数，那么n!=2*i,自然也不存在 n-i=i和重复计算之说

         2.如果n是偶数,n=2*i成立,gcd(n,n/2)必然为n的一个因子,这个因子为1当且仅当n==2

         于是对于n>2的偶数，绝对不存在gcd(n,n/2)=1所以更别说什么重复计算了

         对于n==2

         ans=2*1/2=1，正好也满足

         所以得到最终公式：ans=N*phi(N)/2