歐幾裡德算法的證明

在學習算法的過程中，與歐幾裡德算法來了一次邂逅，于是又去學習了一下。。。

歐幾裡德算法又稱輾轉相除法，用于計算兩個數的最大公約數。

定理：

設a=qb+r，其中a,b,q,r都是正整數，則gcd(a,b)=gcd(b,r)，即gcd(a,b)=gcd(b, a(modb)) 。

在網上看到的證明方法大多是這樣：

a可以表示成a = kb + r（a，b，k，r皆為正整數），則r = a mod b

假設d是a,b的一個公約數，記作d|a,d|b，即a和b都可以被d整除。

而r = a - kb，兩邊同時除以d，r/d=a/d-kb/d=m，等式左邊可知m為整數，是以d|r

是以d也是（b,a mod b）的公約數

是以（a,b）和（b,a mod b）的公約數是一樣的，其最大公約數也必然相等，得證。

不過對于這個證明過程的最後兩句結論有個疑問：

“是以d也是（b,a mod b）的公約數”這句沒什麼問題，但是同樣也可以得到“d也是（a,a mod b）的公約數”。

而這個結論“是以（a,b）和（b,a mod b）的公約數是一樣的，其最大公約數也必然相等”就完全不知道是怎麼得出的。。。

後面和老師溝通了一下，其實這個證明過程是有問題的。

“是以d也是（b,a mod b）的公約數”這個結論并不能得出“是以（a,b）和（b,a mod b）的公約數是一樣的”。隻能得出“如果d是(a,b)的公約數，那麼也d是（b,a mod b）的公約數”的結論，如果d是(a,b)的最大公約數，但d不一定是（b,a mod b）的最大公約數。是以并不能證明“（a,b）和（b,a mod b）的公約數是一樣的”。

完整的證明過程應該是這樣：

a可以表示成a=kb+r（a，b，k，r皆為正整數；且a>b）

則r=amodb

假設d是a,b的一個公約數，為了友善，我們記d=(a,b)

則d|a,d|b，即a和b都可以被d整除 。

而 r=a−kb

兩邊同時除以d得到

r/d=a/d−kb/d

因為d|a,d|b，顯然可以得到d|r

是以d是r的一個約數，是以d是（a,b,r）的公約數，即d=(a,b,r)

設A是(a,b)的公約數集，B是(b,r)的公約數集，R是(a,r)的公約數集

那麼可以得到A⊆B,A⊆R

可見現在并不能得到(a,b)和(b,r)的公約數相同

隻能說(a,b)的公約數是(b,r)公約數的一部分，同時也是(a,r)公約數的一部分

假設d′是(b,r)的公約數，則d′|b,d′|r； a=kb+r，等式兩邊都除以d′,可得

a/d′=(kb+r)/d′=kb/d′+r/d′ 因為d′|b,d′|r； 顯然d′|a

是以如果d′=(b,r),那麼在a=kb+r的情況下，d′也是a的約數，d′=(a,b,r)

是以(b,r)的約數集是(a,b)的約數集的一部分，也是(a,r)約數集的一部分 是以B⊆A，B⊆R 綜上，A=B

由此得證，(a,b)的公約數與(b,r)的公約數相同，當然它們的最大公約數也必定相同。 即

　　　　　　　　　　　　 gcd(a,b)=gcd(b,r)

可見必須要滿足兩個條件才能得到(a,b)的公約數與(b,r)的公約數是相同的結論。

條件一：

假設d=（a,b），那麼在a=qb+r的情況下，有 d=（b,r）

即證明A⊆B

條件二：

假設d=（b,r），那麼在a=qb+r的情況下，有 d=（a,b）

即證明B⊆A

而網上的那個方法隻是證明了條件一，是以并不能得出最後的結論。

在證明條件一的時候，也得到了 d=（a,b）,A⊆R

那麼是否能得到 A=R 成立呢?

同樣，我們也需要證明條件二是否成立，

即

“ 假設d=（a,r），那麼在a=qb+r的情況下，有d=（a,b） ”是否成立。

假設 d=（a,r）,則d|a,d|r

在a=qb+r 等式兩邊同時除以d，得到

a/d=(qb+r)/d=qb/d+r/d

因為d|a,d|r，是以我們能得到d|qb成立，但是并不能得到d|b成立

是以，假設d=（a,r），那麼在a=qb+r，且d|q時，才有d=（a,b）

顯然這個沒什麼意義。。。

其實 A=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），得證

—– 有的人活着，他已經死了，有的人死了，也不讓人好好活，比如歐幾裡德、徐志摩。。。