下载此文档

欧几里德辗转相除法.doc.doc


文档分类:通信/电子 | 页数:约11页 举报非法文档有奖
1/11
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/11 下载此文档
文档列表 文档介绍
(mondivisor)的求法。C++代码如下:intgcd(inta,intb){if(b==0)returna;elsereturngcd(b,a%b);}这个算法就是利用了gcd(a,b)=gcd(b,amodb)。证明:对于a,b的任意公约数r,则r|a,r|b。那么amodb=a-[a/b]*b,[a/b]是取整函数由于r|a,r|b所以r|(amodb)。对于b,amodb的公约数r,则r|b,r|(amodb)a=amodb+[a/b]*b,所与r|a。这样就证明了a,b的公约数和b,amodb完全相同,则最大公约数也相同。费马小定理(1)p为素数,则p|(a^p-a)(2)p为素数,gcd(a,p)=1,则p|(a^(p-1)-1)证明:对于(2),p是素数,a是整数且gcd(a,p)=1即他们的最大公约数是1。由于a,2a,3a,……,(p-1)a模p的余数都不相同。否则若(i*a)modp=(j*a)modp其中1=<i<j<=p-1则p|(j-i)*a,而gcd(a,p)=1,那么p|(j-i),这是不可能的,所以a,2a,3a,……,(p-1)a对p的余数取遍1,2,……p-1。所以a*2a*3a*4a*……*(p-1)a对p的余数等于1*2*……(p-1)对p的余数。这是由于性质:amodp=x,bmodp=y,那么(a*b)modp=(x*y)modp。1*2*……(p-1)*a^(p-1)modp=(p-1)!modp((a^(p-1)-1)*(p-1)!+(p-1)!)modp=(p-1)!modp则(a^(p-1)-1)*(p-1)!modp=0由于p是素数,gcd(p,(p-1)!)=1所以a^(p-1)-1modp=0就是p|(a^(p-1)-1)。因此(2)得证。对于(1)若gcd(a,p)?1,那么由于p是素数必然p|a因此p|a*(a^(p-1)-1)显然得证。如果gcd(a,p)=1,则由(2)得p|(a^(p-1)-1)因此因此p|(a^(p-1)-1)*a显然得证。欧拉函数是指:对于一个正整数n,小于n且和n互质的正整数的个数,记做:φ(n)欧拉定理:gcd(a,n)=1,则a^φ(n)?1modn对于互质的整数a和n,有a^φ(n)?1modn证明:首先证明下面这个命题:对于集合Z={X1,X2,...,Xφ(n)},Xi为第i个小于n且和n互质的正整数考虑集合S={aX1modn,aX2modn,...,aXφ(n)modn}则S=Z证明:a,n互质,Xi与n互质,那么aXi与n互质对于Z中两个元素Xi和Xj,如果Xi?Xj则aXimodn?aXjmodn,若aXimodn=aXjmodn,那么a(Xi-Xj)modn=0,a,n互质那么Xi-Xjmodn=0由于0<Xi,Xj<n显然不可能。因此S中的元素各不相同,这样S中含有φ(n)个与n互质的正整数,且满足每个元素小于n所以,很明显,S=Z既然这样,那么(aX1×aX2×...×aXφ(n))modn=(aX1modn×aX2modn×...×aXφ(n)modn)modn=(x1×x2×...×xφ(n))modn考虑上面等式左边和右边最左边等于(a^φ(n)×(x1×x2×...×xφ(n))modn最右边等于(x1×x2×...×xφ(n))modn得到(a^φ(n)-1)(x1×x2×...×xφ(n))modn=0而(x1×x2×...×xφ(n))modn和n互质,所以a^φ(n)?1modn推论:当n为素数时,φ(n)=n-1,a^(n-1)-1modn=0就是费马小定理(2)模p乘法逆元对于整数a、p,如果存在整数b,满足a*bmodp=1,则说,b是a的模p乘法逆元。定理:a存在模p的乘法逆元的充要条件是gcd(a,p)=1证明:首先证明充分性如果gcd(a,p)=1,根据欧拉定理,a^φ(p)?1modp,因此显然a^(φ(p)-1)是a的模p乘法逆元。再证明必要性假设存在a模p的乘法逆元为b,a*b?1modp则a*b=k*p+1,所以1=a*b-k*p因为gcd(a,p)=d所以d|1所以d只能为1扩展欧几里德定理如果gcd(a,b)=d,那么一定存在整数x,y满足a*x+b*y=d证明,可以设a=p*d,b=q*d,显然gcd(p,q)=1a*x+b*y=p*d*x+q*d*y若要a*x+b*y=d必需p*x+q*y=1,由gcd(p,q)=1则p^φ(q)?1modq令x=p^(φ(q)-1)也就是x是p的模q逆元,则p*x-1=p^φ(q)-1modq=0,那么y=(p^φ(q)-1)/q显然是整数,当然也可以y=q^(φ(p)-1)

欧几里德辗转相除法.doc 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数11
  • 收藏数0 收藏
  • 顶次数0
  • 上传人文库旗舰店
  • 文件大小28 KB
  • 时间2019-11-22