A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 打滚的橘子 中级黑马   /  2015-11-8 18:36  /  801 人查看  /  1 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

这是我碰到要求2个数的最大公约数时,卡壳卡很久的地方。百度出来都是怎么用辗转相除法,而好好没有解释这个方法为何能求出最大公约数。下面是终于查到的比较简洁好理解的解释:
设两数为a、b(b<a),用gcd(a,b)表示a,b的最大公约数,r=a mod b 为a除以b以后的余数,k为a除以b的商,即a÷b=k.......r。辗转相除法即是要证明gcd(a,b)=gcd(b,r)。

第一步:令c=gcd(a,b),则设a=mc,b=nc
第二步:根据前提可知r =a-kb=mc-knc=(m-kn)c
第三步:根据第二步结果可知c也是r的因数
第四步:可以断定m-kn与n互质【否则,可设m-kn=xd,n=yd,(d>1),则m=kn+xd=kyd+xd=(ky+x)d,则a=mc=(ky+x)dc,b=nc=ycd,故a与b最大公约数成为cd,而非c,与前面结论矛盾】
从而可知gcd(b,r)=c,继而gcd(a,b)=gcd(b,r)。
证毕。

1 个回复

倒序浏览
查的过程中还看到了大衍求一术和完全不想搞懂只能膜拜的孙子定理。古代算术真是博大精深,甩西方几个世纪,闲的人可以去看看。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马