欧拉函数

定义：对于一个正整数n,小于且和n互质的正整数的个数。记作φ(n)，例如φ(8)=4。
欧拉函数的计算：
通式：φ（x）=x*(1-1/p1)*(1-1/p2)*...*(1-1/pn)。pi(i=1,2,3,...)为x的所有质因数。
特例：φ（1）=1
注意：每种质因数只出现一次。
欧拉函数的性质：
1.若n是质数p的k次幂，φ（n）=p^k-p^(k-1)=(p-1)*p^(k-1)。推导可参考通式。
2.若m,n互质，则φ（m*N）=φ（m）*φ（n）。
3.若n为奇数，φ（2*n）=φ（n)
4.n中与n互质的数的和为ϕ(n)/2∗n(n>1)。gcd(n,x)=gcd(n,n-x),成对出现且和为n.
5.ϕ(n)(n>2)为偶数.成对出现。

欧拉打表的性质：
1.若p为质数，则φ（p）=p-1；
2.设a为N的质因数
（1）若((N%a)==0&&(N/a)%a==0） φ(N)=φ(N/a)*a;
（2）若((N%a)==0&&(N/a)%a!=0） φ(N)=φ(N/a)*(a-1)
证明：
（1）该情况说明n和n/p有相同的质因子，只是p这一项的指数不同那么我们按照欧拉函数的通式展开，并相除，可得φ(N)=φ(N/a)*a
（2）该情况说明n和n/p互质,可得φ(N)=φ(N/a)*(a-1)