2016 - 2024

感恩一路有你

辗转相除法求最小公倍数例题 谁来解释一下用辗转相除法求最两个数的最大公约数原理?

浏览量:2332 时间:2021-03-13 05:10:44 作者:admin

谁来解释一下用辗转相除法求最两个数的最大公约数原理?

除法求最大公约数的原理:设两个数为a和B(a>B),用GCD(a,B)表示a和B的最大公约数,r=a(MOD B)是a除以B的余数,K是a除以B的商,即a△B=K。。除法是证明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=(kyx)D,然后a=MC=(KY)x)CD,b=NC=yCd,那么a和B有一个公约数CD>C,所以C不是a和B的最大公约数,这与前面的结论相矛盾),所以C也是B和r的最大公约数,所以GCD(B,r)=C,那么GCD(a,B)=GCD(B,r)。结束了。以上步骤的操作是基于开始时R≠0。也就是说,m和N也是互质。

辗转相除法求最小公倍数例题 辗转相除法求最大公约数编程 c求最大公约数和最小公倍数

版权声明:本文内容由互联网用户自发贡献,本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。