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

2019-04-14 16:17发布

站内文章 / 模拟电子
17978 0 1205
    一个正整数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    费马定理：若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; }  

热门文章