證明輾轉相除法(歐幾裡德算法)

定理：兩個整數的最大公約數等于其中較小的那個數和兩數的相除餘數的最大公約數。最大公約數（greatest common divisor）縮寫為gcd。

證明：

gcd(a,b) = gcd(b,a mod b) (不妨設a>b 且r=a mod b ,r不為0) a可以表示成a = kb + r（a，b，k，r皆為正整數），則r = a mod b

• 12，18的公因數有：1，2，3，6。
• 由算法gcd（a，b）=gcd(b,a%b)有gcd（12，18）=gcd(18,12%18)=gcd(18,12)
• 18,12的公因數有：1，2，3，6。
• 接着往下算，gcd（18，12）=gcd(12,18%12)=gcd(12,6)
• 12,6的公因數有：1，2，3，6。
• 再往下，gcd（12，6）=gcd(6,12%6)=gcd(6,0)
• 0,6的公因數有：1，2，3，6。

• 最後，就由gcd（0，n)=n得gcd（0，6）=6

  第1，3，5，7他們的公因數集都是相等的，自然的，集合裡的最大值也是相等的。

證明：也就是證明如果a=bq+r，那麼d是a和b的公因數，當且僅當d是b和r的公因數。

1)設d是a和b的公因數，則d|a且d|b，于是d|(a−bq)。也就是說d|r, 因為r=a−bq. ==》d是b,r的公因數。

這裡解釋一下d|（a-bq)：

因為d|a，d|b,是以有a=dx,b=dy;把d代入a-bq有dx-dyq=d(x-yq).

是以d|（a-bq)

2)設d是b和r的公因數，則d|r且d|b。于是，d|（bq+r）.是以d|a ==》是以d是a,b的公因數。

綜上，a,b的所有公因數和b,r的所有公因數是一樣的。那麼，d是a，b的最大公因數，當且僅當d是b和r的最大公因數。