数论——欧拉函数与相关定理
??? 一个正整数n的欧拉函数定义为：在1到n-1之间和n互素的数的个数。
??? 欧拉函数公式：
phi(n)=n(1-1/p1)(1-1/p2)(1-1/p3)...(1-1/pk)，其中pi为n的素因子。
??? 例如，phi(12)=12(1-1/2)(1-1/3)=12*1/2*2/3=4。
?
相关定理
?
???欧拉定理
?? 对于任意正整数n>1， a^phi(n)=1 (mod n)， a<n且a与n互质。可以从元素的幂去证明。
?? 费马定理：若p是素数，则 a^p-1=1 (mod n) ，显然是欧拉定理的推论。
?? GCD递归定理
?????? 对任意的非负整数a和任意正整数b有：
?? gcd(a,b) = gcd(b,a%b)
定理1
??? 若a和b是不都为0的任意整数，则gcd(a,b)是a与b的线性组合集合{ax+by,x,y属于整数}中最小的正元素。
定理2
? （元素的幂）一个正整数n有原根，则它恰好有phi(phi(n))个原根。
??? 所谓原根，即给出集合zn，zn的元素为小于n且与n互素的数。若n中的某个元素g的幂模n产生的群的个数为n-1，则g称为zn的原根。比如对模7，3就是一个原根，2不是。
定理3
??? 如果对模n存在1的非平凡平方根，则n是合数。（这个定理为Miller-Rabin素数测试提供依据）
????即对方程 x^2 = 1 (mod n)，方程的解除了1和n-1两个平凡根之外，还有其它的根，那么n肯定是合数。
?
附上求欧拉函数的代码
?
//返回1——n的欧拉函数void Euler2(__int64 n){ getPrime(n); int i,j; for(i = 1; i <= n; i++) PHI[i] = i; for(i = 2; i <= n; i++) { if(isPrime[i]==0) { for(j = i; j <= n; j += i) PHI[j] = PHI[j]/i*(i-1); } }}//返回一个数的欧拉函数__int64 Euler(__int64 n){ __int64 i; __int64 result = n; __int64 t = (__int64)sqrt(n*1.0); for(i = 2; i <= t; i++) { if(n%i==0) { result = result/i*(i-1); while(n%i==0) n = n/i; } } if(n>1) result = result/n*(n-1); return result;}?