你最愿意做的哪件事,才是你的天赋所在

0%

欧拉降幂证明及应用

欧拉定理

内容

正整数 a,n互质,则aϕ(n)1(modn)其中ϕ(n)是1-n中与n互质的数的个数

证明

不妨设X1,X2,,Xn为1~n中与n两两互质的数
那么对一些数进行讨论aX1,aX2,,aXn

引理1

aX1,aX2,,aXn中,任意两个数模n的余数一定不同。

证明

aX1aX2(modn)
a(X1X2)0(modn)
因为a与n互质,并且X1X2n
所以不存在aX1aX2(modn)
因此aX1,aX2,,aXn中,任意两个数模n的余数一定不同。
证毕

引理2

aX1,aX2,,aXn中,任意的aXi1(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)==X1X2Xϕ(n)

就可以得出

aϕ(n)X1X2Xϕ(n)(mod n)==X1X2Xϕ(n)

因为X1X2Xϕ(n)与n互质,所以得到

aϕ(n)X1X2Xϕ(n)==1(mod n)
aϕ(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)

证明

证一

abab%ϕ(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)
abab%ϕ(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(a1,c0)
要证ab%ϕ(p)+phi(p)   gcd(a,p)1,b>ϕ(p)
则证akϕ(p)+caϕ(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)
因为欧拉函数为积性函数,所以有

ϕ(p)=ϕ(gcd(p,aϕ(p))ϕ(pgcd(p,aϕ(p)))(2)

假设k=gcd(p,aϕ(p))(3)
根据(1)(2)(3)以及欧拉定理,有

aϕ(p)(apgcd(p,aϕ(p)))k1(mod pgcd(p,aϕ(p)))

得到

aϕ(p)1(mod pgcd(p,aϕ(p)))
pgcd(p,aϕ(p))(aϕ(p)1)

移项

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进行素因子分解

a=qk11qk22qkttpl11pl22plt1t
p=qu11qu22quttwv11wv22wvt1t

前面是相同的部分,后面是不同的部分。

gcd(a,p)=qmin(k1,u1)1qmin(k2,u2)2qmin(kt,ut)t
gcd(aϕ(p),p)=qmin(k1ϕ(p),u1)1qmin(k2ϕ(p),u2)2qmin(ktϕ(p),ut)t

根据欧拉函数的性质

ϕ(p)=qu111qu212qut1t(q11)(q21)(qt1)()

kiϕ(p)kiqui1i(qi1)qui1i

现在需证明

qui1iui

这个证明可以化成函数xa1a求导后判断单调性和最小值可以证明
得出这个结果之后
即可得到

k1ϕ(p)u1
gcd(aϕ(p),p)=qu11qu22qutt

回到原式子以及进行质因数分解的出来的a,p;

gcd(pgcd(p,aϕ(p)),a)1(mod p)
p=qu11qu22quttwv11wv22wvt1t
a=qk11qk22qkttpl11pl22plt1t
pgcd(p,aϕ(p))=wv11wv22wvt1t

因为他们相同的素因子已经被除去了因此。

gcd(pgcd(p,aϕ(p)),a)1(mod p)

到这里全部的欧拉降幂就证明完成了。

-------------你最愿意做的哪件事才是你的天赋所在-------------
表情 | 预览
快来做第一个评论的人吧~
Powered By Valine
v1.3.10