定义:
性质:
解释：将φ(n)展开成计算式，a,b没有共同质因子，那么 φ(a)和φ(b)中没有共同的pi,所以得证.
gcd(n,i) = 1时,gcd(n,n-i) = 1
反证法:设gcd(n,n-i) = k(k > 1),那么n%k=0且(n-i)%k = 0,所以 那么i%k == 0
,推出gcd(n,i) = k. 与原结论相反，得证,
所以与n互质的数成对存在,且两两之间和为n
所以sum=互质个数/2*n
还是需要证明一个东西：gcd(n,i) = 1 则gcd(n,n+i) = 1;
设gcd(n,n + i) = k(k!=1).设i = ka1,n+i=ka2,(a2 > a1),则n = k(a2 - a1).
则gcd(n,i) = gcd(k(a2 - a1),ka1) = k (因为gcd(a1,a2) = 1 所以gcd(a2 - a1 , a1) = 1(这个已经证明了),所以gcd(k(a2-a1),ka1) = k)。得证
这个证明了就很好办了，因为n是p的倍数，所以n*p并不增加新的质数.所以1~n内与n互质的数一样与n*p互质。
然后设ai为与n互质的数,那么 ai + kn一样与n互质(也就是n*p),所以 φ(n*p) = φ(n)*p;
注：这里也可以根据计算式来分析.
很简单,(素数与一个数不是倍数，那么两者就是互质,根据性质2可得.
⑦欧拉降幂以及广义欧拉降幂
求法:
一.根据公式 可以利用质因子分解来求单个数N的欧拉函数.(太简单了这里不放代码了)
二.求1~N的欧拉函数:借助欧拉筛(利用性质5.1 5.2)
