證明:若 c 為 a 與 b 之共同因數,則 c 為 gcd(a,b) 之因數。

作者:   發佈於: ,更新於:

此處 gcd(a,b) 為 a 與 b 之最大公因數之表記。

因 c 為 a, b 之因數,可知有兩整數 m, n 使得:

a = mc
b = nc

令 d = gcd(a,b)。依 Bézout's identity,可知存在有兩整數 x, y 使得:

d = xa + yb

將 a 與 b 代換後,得:

d = xmc + ync
  = (xm + yn)c

因 d 為 a,b 之最大公因數, d ≥ c > 0 。 xm + yn 必為正。

因 m, n, x, y 全為整數,xm + yn 必為整數。

綜合上述兩點,xm + yn 為正整數。d 為 c 之倍數。亦即 c 為 gcb(a,b) 之因數。證明完畢。