最大公因數是other公因數的倍數?

要證明這個命題，我們可以使用如下兩個定理：
(1) 除法算式(Division Algorithm)：
給定任何正整數a和b，均存在整數q和r使得
a = bq＋r，且0≦r＜b。
(2) 裴蜀(Bezout)恆等式：
若正整數m和n互素（即m和n的最大公因數是1），則存在整數u和v使得mu＋nv = 1。
原命題可改寫成：
設F是正整數a和b的最大公因數。
若f是a和b的公因數，則F是f的倍數。
證明：
設a = mF，b = nF，其中m、n是正整數。
（步驟1：m和n互素）
假設m和h的最大公因數為d(≧1)。
則存在整數s、t使得m = sd及n = td。
故a = sdF及b = tdF。
所以dF是a和b的公因數。
由於F是a和b的最大公因數，故dF≦F，即d≦1。
由此得知，m和n的最大公因數是1。
（步驟2：求F被任意公因數相除時的餘數r）
設f是a和b的公因數。
則存在整數h、k使得a = hf及b = kf。
根據除法算式，存在正整數q和r使得F = fq＋r，且0≦r＜f。
由於a = mF及b = nF，所以
hf = m(fq＋r)及kf = n(fq＋r)。
移項後得mr = (h - mq)f及nr = (k - nq)f。
（步驟3：證明r = 0）
由於m和n互素，由裴蜀恆等式可知，存在整數u和v使得mu＋nv = 1。
由mr = (h - mq)f及nr = (k - nq)f可知，
r = (mu＋nv)r = [(h - mq)u + (k - nq)v]f。
然而，由於0≦r＜f而且[(h - mq)u + (k - nq)v]為整數，所以r = 0。
所以F = fq＋0 = fq，即F是f的倍數。證畢。
***
其實有些數學教科書會以下述方法定義「最大公因數」，可供參考：
設a和b為正整數。
整數d稱為a和b的最大公因數當且僅當：
(1) a和b均被d整除；及
(2) 若d'是a和b的公因數，則d被d'整除。

2008-07-23 22:45:18 補充：
出現亂碼：
"≧"為「大於或等於」、"≦"為「小於或等於」。

方便起見,informal prove就算:

A,B為該2數,
C為最大公因數,
所以D(任一公因數)一定在C中,
見:
http://hk.geocities.com/chorccp/pic.JPG
(拙圖)