Question

数学上的辗转相除法

Answer 1

设两数为a、b(b＜a)，求它们最大公约数(a、b)的步骤如下：用b除a，得a＝bq......r
1(0≤r)。若r1=0，则(a，b)＝b；若r1≠0，则再用r1除b，得b＝r1q......r2
(0≤r2).若r2＝0，则(a，b)＝r1，若r2≠0，则继续用r2除r1,……如此下去，直到能整除为止。其最后一个非零余数即为..
原理及其详细证明
在介绍这个方法之前，先说明整除性的一些特点（下文的所有数都是正整数，不再重覆），我们可以这样给出整除性的定义：
对于二个自然数a和b，若存在正整数q，使a=bq，则a能被b整除，b为a的因子，a为b的倍数。
如果a能被c整除，并且b也能被c整除，则c为a、b的公因数（公有因数）。
由此我们可以得出以下推论：
推论1、如果a能被b整除（a=qb），若k为正整数，则ka也能被b整除（ka=kqb）
推论2、如果a能被c整除（a=hc），b也能被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=qb），b也能被a整除（b=ta），则a=b
因为：a=qb
b=ta
a=qta
qt=1
因为q、t均为正整数，所以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为m,n的最大公约数，
∴m能被a整除，且n也能被a整除，
∴由推论1得：qn也能被a整除，
∴
由推论2得：m-qn也能被a整除，
又
∵m-qn=r，
∴r也能被a整除，即a为n和r的公约数（注意：还不是最大公约数）
∵b为n和r的最大公约数，a为n和r的公约数
∴a≤b，
同理
∵b为n,
r的最大公约数，
∴n能被b整除，且r也能被b整除，
∴由推论1得：qn也能被b整除，
∴由推论2得：qn+r也能被b整除，
又∵m=qn+r，
∴m也能被b整除，即b为m和n的公约数，（注意：还不是最大公约数）
∵a为m,n的最大公约数，b为m和n的公约数，
∴b≤a，
由以上可知：
a≤b与b≤a同时成立，
故可得
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