原根的个数 POJ_1284

首先e[m,a]表示使得a^e[m,a]=1(mod m)的最小的正整数.那么我们有e[m,a^k]=e[m,a]/gcd(e[m,a],k)(k>0).证明如下:记x=e[m,a],x’=x/gcd(x,k);x’’=e[m,a^k];先证明x’|x’’.

由题意可知a^x=1(mod m) (a^k)^x’’=1(mod m)

由性质又因为e[m,a]|kx’’,所以 x’=(x/gcd(x,k)) | (kx’’/(gcd(x,k)).又gcd(x/gcd(x,k),k/gcd(x,k))=1.所以x’|x’’.

再证明x’’|x’

a^(kx’)=(a^k)^x’=1(mod m)—>x’’|x’

所以x’=x’’;

推论如果gcd(k,e[m,a])=1,e[m,a^k]=e[m,a];我们可以用这个来求原根的个数.假设一个数n存在原根,且最小的原根等于g.n的欧拉函数为phi[n].那么n的原根的个数就是phi[phi[n]].也就是g的t次方[gcd(t,phi[n])=1 1<=t<phi[n])也是一个原根,当然这里也包含了所有的原根[想想为什么?似乎只能说明原根数至少是phi[phi[n]]个?再好好想想就出来了.注意a^k != 1(mod m)(k<e[m,a])]

那么1284就直接求一个数的欧拉函数了.代码如下: