欧拉定理
内容
若正整数 a,n互质,则aϕ(n)≡1(modn)其中ϕ(n)是1-n中与n互质的数的个数
证明
不妨设X1,X2,⋯,Xn为1~n中与n两两互质的数
那么对一些数进行讨论aX1,aX2,⋯,aXn
引理1
aX1,aX2,⋯,aXn中,任意两个数模n的余数一定不同。
证明
设aX1≡aX2(modn)
则 a(X1−X2)≡0(modn)
因为a与n互质,并且X1−X2≠n
所以不存在aX1≡aX2(modn)
因此aX1,aX2,⋯,aXn中,任意两个数模n的余数一定不同。
证毕
引理2
aX1,aX2,⋯,aXn中,任意的aXi≡1(modn)
证明
因为a与n互质,Xi与n互质,所以aXi与n互质,即gcd(aXi,n)==gcd(n,aXi%n)==1;
因此aXi(modn)≡1(modn)
证毕
总结
把aX1,aX2,⋯,aXn都模n看成一个集合,根据引理1,这个集合具有互异性,引理2,我们发现集合中的元素与X1,X2,⋯,Xn中的元素是一致的。那么就有
aX1(mod n)∗aX2(mod n)∗⋯∗aXϕ(n)==X1∗X2∗⋯∗Xϕ(n)就可以得出
aϕ(n)∗X1∗X2∗⋯∗Xϕ(n)(mod n)==X1∗X2∗⋯∗Xϕ(n)因为X1∗X2∗⋯∗Xϕ(n)与n互质,所以得到
aϕ(n)∗X1∗X2∗⋯∗Xϕ(n)==1(mod n)欧拉降幂
欧拉降幂其实就是下面这个式子
ab≡{ab%ϕ(p) gcd(a,p)=1ab gcd(a,p)≠1,b<ϕ(p)ab%ϕ(p)+ϕ(p) gcd(a,p)≠1,b≥ϕ(p)(mod p)证明
证一
ab≡ab%ϕ(p)gcd(a,p)=1(mod p)这个证明用到上面讲的欧拉定理
∵b=b%ϕ(p)+k∗ϕ(p)
∴ab=ab%ϕ(p)+k∗ϕ(p)(mod p)
∵aϕ(p)≡1(mod p)
∴ab%ϕ(p)+k∗ϕ(p)=ab%ϕ(p)(mod p)
即ab≡ab%ϕ(p)gcd(a,p)=1(mod p)
证毕
证二
ab gcd(a,p)≠1,b<ϕ(p)直接得此结论
证三
ab%ϕ(p)+ϕ(p) gcd(a,p)≠1,b≥ϕ(p)不妨设b=k∗ϕ(p)+c(a≥1,c≥0)
要证ab%ϕ(p)+phi(p) gcd(a,p)≠1,b>ϕ(p)
则证ak∗ϕ(p)+c≡aϕ(p)+c (mod p)
即 ak∗ϕ(p)≡aϕ(p) (mod p)
即 a2∗ϕ(p)≡aϕ(p) (mod p)
即证 aϕ(p)∗(aϕ(p)−1)≡0(mod p)
接下来假设
N=pgcd(p,aϕ(p))假设gcd(pgcd(p,aϕ(p)),A)≡1(mod p)(1)
因为欧拉函数为积性函数,所以有
假设k=gcd(p,aϕ(p))(3)
根据(1)(2)(3)以及欧拉定理,有
得到
aϕ(p)≡1(mod pgcd(p,aϕ(p)))移项
p∣(aϕ(p)−1)∗gcd(p,aϕ(p))因为gcd(pgcd(p,aϕ(p)),A)≡1(mod p)(1)
所以
p∣(aϕ(p)−1)∗aϕ(p)
与上述需证明的一致,于是证明完毕。
但是,我们是基于假设上的,也就是
gcd(pgcd(p,aϕ(p)),A)≡1(mod p)
所以,我们现在需要证明我们的假设
对a进行素因子分解
前面是相同的部分,后面是不同的部分。
gcd(a,p)=qmin(k1,u1)1∗qmin(k2,u2)2∗⋯∗qmin(kt,ut)t根据欧拉函数的性质
ϕ(p)=qu1−11∗qu2−12∗⋯∗qut−1t∗(q1−1)∗(q2−1)∗(qt−1)∗⋯(不相同部分不管)∴
ki∗ϕ(p)≥ki∗qui−1i∗(qi−1)≥qui−1i现在需证明
qui−1i≥ui这个证明可以化成函数xa−1−a求导后判断单调性和最小值可以证明
得出这个结果之后
即可得到
回到原式子以及进行质因数分解的出来的a,p;
gcd(pgcd(p,aϕ(p)),a)≡1(mod p)因为他们相同的素因子已经被除去了因此。
gcd(pgcd(p,aϕ(p)),a)≡1(mod p)到这里全部的欧拉降幂就证明完成了。
v1.3.10