辗转相减 百科内容来自于: 百度百科

辗转相减法求最大公约数即尼考曼彻斯法其特色是做一系列减法从而求得最大公约数例如 两个自然数35和14用大数减去小数(35,14)->(21,14)->(7,14)此时7小于14要做一次交换把14作为被减数即(14,7)->(7,7)再做一次相减结果为0这样也就求出了最大公约数7
证明:
a=bq1+r1(0<r1<b)
b=r1q2+r2(0<r2<r1)
r1=r2q3+r3(0<r3<r2)
……
只要r1,r2,r3……不是0就可以继续写下去
我们看到
b>r1>r2>r3>……>0
b是有限的r1,r2,r3是整数
所以至多b步后必有rn=0
rn-2=rn-1qn + rn
rn-1 = rn*qn+1+0
由此可以得到(a,b)=rn
证明II:
在介绍这个方法之前先说明整除性的一些特点下文的所有数都是正整数不再重覆我们可以这样给出整除性的定义
对于二个自然数a和b若存在正整数q使a=bq则a能被b整除b为a的因子a为b的倍数
如果a能被c整除并且b也能被c整除则c为ab的公因数公有因数
由此我们可以得出以下推论
推论1如果a能被b整除a=qb若k为正整数则ka也能被b整除ka=kqb
推论2如果a能被c整除a=hcb也能被c整除b=tc则(a±b)也能被c整除
因为将二式相加a+b=hc+tc=(h+t)c 同理二式相减a-b=hc-tc=(h-t)c
所以(a±b)也能被c整除
推论3如果a能被b整除a=qbb也能被a整除b=ta则a=b
因为a=qb b=ta a=qta qt=1 因为qt均为正整数所以t=q=1
所以a=b
辗转相除法是用来计算两个数的最大公因数在数值很大时尤其有用而且应用在电脑程式上也十分简单其理论如下:
如果 q 和 r 是 m 除以 n 的商及余数即 m=nq+r则 gcd(m,n)=gcd(n,r)
证明是这样的: 设 a=gcd(m,n)b=gcd(n,r)
a=gcd(m,n)
m能被a整除并且n也能被a整除则由推论1得qn也能被a整除
由推论2得m-qn也能被a整除
而m-qn=r即r也能被a整除
因为b是最大公约数最大公约数定义所以b能被a整除
同时
b=gcd(n,r)
n能被b整除并且r也能被b整除则由推论1得qn也能被b整除
由推论2得qn+r也能被b整除
而m=qn+r即m也能被b整除
因为a是最大公约数所以a能被b整除
由推论3得到a=b
例如计算 gcd(546, 429)
gcd(546, 429) 546=1*429+117
=gcd(429, 117) 429=3*117+78
=gcd(117, 78) 117=1*78+39
=gcd(78, 39) 78=2*39
=39
$firstVoiceSent
- 来自原声例句
小调查
请问您想要如何调整此模块?

感谢您的反馈,我们会尽快进行适当修改!
进来说说原因吧 确定
小调查
请问您想要如何调整此模块?

感谢您的反馈,我们会尽快进行适当修改!
进来说说原因吧 确定