輾轉(zhuǎn)相除法

「輾轉(zhuǎn)相除法」又叫做「歐幾里得算法」,是公元前 300 年左右的希臘數(shù)學(xué)家歐幾里得在他的著作《幾何原本》提出的.利用這個(gè)方法,可以較快地求出兩個(gè)自然數(shù)的最大公因數(shù),即 HCF 或叫做 gcd.所謂最大公因數(shù),是指幾個(gè)數(shù)的共有的因數(shù)之中最大的一個(gè),例如 8 和 12 的最大公因數(shù)是 4,記作 gcd(8,12)=4.

在介紹這個(gè)方法之前,先說明整除性的一些特點(diǎn),注以下文的所有數(shù)都是正整數(shù),以后不再重覆.

我們可以這樣給出整除以的定義:

對(duì)於兩個(gè)自然數(shù) a 和 b,若存在正整數(shù) q,使得 a=bq,則 b 能整除 a,記作 b | a,我們叫 b 是 a 的因數(shù),而 a 是 b 的倍數(shù).

那麼如果 c | a,而且 c | b,則 c 是 a 和 b 的公因數(shù).

由此,我們可以得出以下一些推論:

推論一:如果 a | b,若 k 是整數(shù),則 a | kb.因?yàn)橛?a | b 可知 ha=b,所以 (hk)a=kb,即 a | kb.

推論二:如果 a | b 以及 a | c,則 a | (b±c).因?yàn)橛?a | b 以及 a | c,可知 ha=b,ka=c,二式相加,得 (h+k)a=b+c,即 a | (b+c).同樣把二式相減可得 a | (b-c).

推論三:如果 a | b 以及 b | a,則 a=b.因?yàn)橛?a | b 以及 b | a,可知 ha=b,a=kb,因此 a=k(ha),hk=1,由於 h 和 k 都是正整數(shù),故 h=k=1,因此 a=b.

輾轉(zhuǎn)相除法是用來計(jì)算兩個(gè)數(shù)的最大公因數(shù),在數(shù)值很大時(shí)尤其有用而且應(yīng)用在電腦程式上也十分簡(jiǎn)單.其理論如下:

如果 q 和 r 是 m 除以 n 的商及余數(shù),即 m=nq+r,則 gcd(m,n)=gcd(n,r).

證明是這樣的:

設(shè) a=gcd(m,n),b=gcd(n,r)

則有 a | m 及 a | n,因此 a | (m-nq)(這是由推論一及推論二得出的),即 a | r 及 a | n,所以 a | b

又 b | r 及 b | n,所以 b | (nq+r),即 b | m 及 b | n,所以b | a.因?yàn)?a | b 并且 b | a,所以 a=b,即 gcd(m,n)=gcd(n,r).

例如計(jì)算 gcd(546,429),由於 546=1(429)+117,429=3(117)+78,117=1(78)+39,78=2(39),因此

gcd(546,429)

=gcd(429,117)

=gcd(117,78)

=gcd(78,39)

=39
最小公倍數(shù)就是2個(gè)數(shù)的積除以最大公約數(shù)