数论——欧拉函数与相关定理

??? 一个正整数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;}

?