扩展欧几里得算法详细举例解析_第1页
扩展欧几里得算法详细举例解析_第2页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

扩展得算？②amodba-[a/b]b（[a/b]Pascaladivb）a|bmoda=0③(a,b)表示a和b的最大公约（这很重要现在证明一个重要的定理：(a,b)是a和b的最小的正线性组合例：a=6b=4，最小正线性组合为1*a+(-1)*b=2=(a,b)证明设(a,b)为d，ab的最小的正线性组合为∵d|a∴d|samods=a- =a- =a(1-[a/s]x)-ab的线性组∵amods<s，amodsab∴amods=0s|a同理由s|b∴s为a,b的公约∴d=s。证由这条定理易推知：若d|a且d|b，则d|Euclid首先先提出一个定理：(a,b)=(b,a- 为正整数）证明 (b,a-bx)=e,∴d|a- (b,a-bx)，即∵e|b,e|a- (a,b)，即 (a,b)，即∴d=e。证当x=1时，(a,b)=(b,a-b)。这就是辗转相减法当x达到最大时，即x=[a/b]时，(a,b)=(b,amodb)。这个就是Euclid算法它是不是Euclid我不知道但听说是在Euclid时代形成的所以就叫Euclidfunctionifb=0thenelseexit(Euclid(b,amod一次递归就会转为(b,a)，接着就能正常运行了。扩展前面，(a,b)可以表示为a和b的最小的正线性组合。现在就要求这个最小的正线性组合ax+by中的x和y。这个可以利用的Euclid算法。当b=0时，取x=1,y=0例：a=5，b=0，最小正线性组合为5*1+y*0=5,y为任意整数。这里为方便起见规定y=0性组合表示bx'+(amodb)y'，则 =bx'+(amod =bx'+(a- =ay'+b(x'-那么，x=y'，y=x'-[a/b]y'。这样就可以在Euclid的递归过程中求出x和yfunctionvarifb=0thenp:=(b,amodb);y:=n-adivb*y;现在还有一个问题：x,y是不是确定的？答案：不是。如果x,y符合要求，那么际上y可以取任何正整数。以(26,15)为例X=-4Y=3-1*(-4)=726*(-↑X=3Y=-1-1*3=-415*3+11*(-X=-1Y=1-2*(-1)=311*(-X=1Y=0-1*1=-14*1+3*(-X=0Y=1-3*0=1X=1Y=0种特殊情况，实际上呢，不定方程却是用Euclid算法解的。对于不定方ax+by=c，设(a,b)=d，如果ax+by=c有解，则d|c（这也是许多奥数题的切入点）。所以一旦d不是c的约数，那么ax+by=c一定无解d|c时，先求ax’+by’=d=(a,b)x'y'ax’+by’=dax’+by’=c，将c/d倍x=x'*c/d，y=y'*c/dax+by=cEuclid算法还可以求解同余方程ax≡b(modm)及其最小x。这其实和不定方程没有区别。（不定方程和同余方程一般都有范围限制，这其实也很容易解决，就不说了

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论