貝祖引理與歐幾里得引理
本文簡介初等數論中的貝祖引理（Bézout’s lemma）與歐幾里得引理（Euclid’s lemma）。
1 除法原理
定理 1（除法原理）描述整數除法的基本原理：對任意非負整數 $a$ 與正整數 $b \comma$我們都能找到非負整數 $q$（稱為商）與 $r \in \{0 \cm 1 \cm \ldots \cm b \varminus 1\}$（稱為餘數）使得 $a = bq + r$ 成立。
定理 1（除法原理） 若 $a$ 為非負整數且 $b$ 為正整數，則存在非負整數 $q$ 與 $r \in \{0 \cm 1 \cm \ldots \cm b \varminus 1\}$ 使 $a = bq + r$ 成立。
證明 我們對 $a$ 使用數學歸納法。
首先由 $0 = b \cdot 0 + 0$ 可知定理在 $a = 0$ 時成立。
接著假設定理在 $a = k$ 時成立，亦即我們有 $k = bq + r \comma$其中 $q$ 為非負整數且 $r \in \{0 \cm 1 \cm \ldots \cm b \varminus 1\} \period$我們說明定理在 $a = k + 1$ 時也成立。
狀況 1：$r \leq b - 2 \period$此時有 $k + 1 = bq + (r + 1) \comma$且我們有 $r + 1 \leq b - 1 \period$
狀況 2：$r = b - 1 \period$此時有 $k + 1 = bq + (b-1) + 1 = b(q + 1) + 0 \period$
因而定理得證。
2 貝祖引理
定理 2（貝祖引理）說明對任意兩個正整數 $a \jcomma b \comma$其最大公因數 $d$ 可以表示為 $ax + by \comma$其中 $x \jcomma y$ 均為整數。例如 42 與 55 的最大公因數為 1，此時 1 可表示為 \[\begin{split}1 = 42 \cdot (-17) + 55 \cdot 13 \period\end{split}\]
定理 2（貝祖引理） 若 $a \jcomma b$ 為正整數，且 $d$ 為 $a \jcomma b$ 的最大公因數，則存在整數 $x \jcomma y$ 使 $ax + by = d$ 成立。
證明 我們對 $b$ 使用數學歸納法。
當 $b = 1$ 時，有 $d = 1 \comma$此時 $a \cdot 0 + b \cdot 1 = 1 = d \period$故定理在 $b = 1$ 時成立。
接著假設定理在 $b \leq k-1$ 時皆成立，其中 $k$ 為一正整數；我們說明定理在 $b = k$ 時也成立。根據定理 1（除法原理），存在非負整數 $q$ 與 $r \in \{0 \cm 1 \cm \ldots \cm b \varminus 1\}$ 使 $a = bq + r$ 與 $0 \leq r < b$ 成立。
狀況 1：$r = 0 \period$此時 $a = bq \comma$即 $b$ 是 $a$ 的因數，故 $d = b \period$此時 $(x, y) = (0, 1)$ 即滿足 $ax + by = b = d \period$
狀況 2：$r > 0 \period$此時 $d$ 是 $b$ 與 $r = a - bq$ 的公因數。對任意 $b$ 與 $r$ 的公因數 $d' \comma$由於 $d'$ 能整除 $b$ 與 $a = bq + r \comma$我們有 $d' \leq d \semicolon$因而 $d$ 是 $b$ 與 $r$ 的最大公因數。
由於 $r < b = k \comma$套用歸納假設我們可以找到整數 $x \jcomma y$ 使得 $bx + ry = d \period$因而 \[\begin{split} d &= bx + ry \\ &= bx + (a - bq)y \\ &= ay + b(x - qy) \period \end{split}\] 至此定理得證。
3 歐幾里得引理
定理 3（歐幾里得引理）說明對任意正整數 $a \jcomma b \comma$若 $ab$ 的一個正因數 $c$ 與 $a$ 互質，則 $c$ 必定整除 $b \period$
定理 3（歐幾里得引理） 對任意正整數 $a \jcomma b \jcomma c \comma$若 $c$ 是 $ab$ 的因數，且 $c$ 與 $a$ 互質，則 $c$ 是 $b$ 的因數。
證明 設 $ab = cd \comma$其中 $d$ 為一整數。由於 $c$ 與 $a$ 互質，由定理 2（貝祖引理）知存在整數 $x \jcomma y$ 使得 $cx + ay = 1 \period$此時我們有 \[\begin{split} b &= b(cx + ay) \\ &= bcx + aby \\ &= bcx + cdy \\ &= c(bx + dy) \comma \end{split}\] 故定理得證。