前言
貝祖曾說：對任意兩整數 $a,b \in \mathbb{Z}$ 一定可以找到 $x,y \in \mathbb{Z}$ 滿足 $gcd(a,b)=ax+by$。此即為貝祖等式 (Bézout's identity)。雖然網路上許多相關證明，但個人認為這些證明都有一個通病，也就是過程中省略許多步驟與解釋，讓人看得不明所以，無法輕易得知該步驟是根據什麼道理得來的。這篇文章主要為這些證明補上個人的想法，使證明過程容易理解。
貝祖係數與擴展歐幾里德演算法
Let a and b be integers with greatest common divisor d. Then there exist integers x and y such that ax + by = d. Moreover, the integers of the form az + bt are exactly the multiples of d.
- 每組 $gcd(a,b)=ax+by$ 的整數解 $x,y$ 都稱為 $(a,b)$ 的貝祖係數 (Bézout coefficients)，貝祖係數並不唯一。
- 貝祖係數可以透過擴展歐幾里得演算法 (Extended Euclidean algorithm) 求出。
證明 Bézout's identity
給任意兩非零整數 $a$ 與 $b$，同時令集合 $S=\{ax+by:x, y \in \mathbb{Z}\ \land \ ax+by>0\}$。$S$ 不為空集合，其至少含有 $a$ (當 $a>0$ 且 $x=1, y=0$) 或 $-a$ (當 $a<0$ 且 $x=-1, y=0$)。又因為 $S$ 集合的每個元素為正整數，根據良序原則 (Well-ordering principle)，我們可以說 $S$ 有最小值 $d$，並將其表示為
為了證明 $d$ 是 $a$ 與 $b$ 的最大公因數 ($d=gcd(a,b)$)，必須依序證明以下兩點
- $(d \mid a) \land (d \mid b)$：$d$ 是 $a$ 與 $b$ 的公因數。
- $c \leq d$：任何其他 $a$ 與 $b$ 的公因數 $c$ 都滿足 $c \leq d$，意味著 $d = gcd(a,b)$。
證明 $(d \mid a) \land (d \mid b)$
證明 $d \mid a$
$a$ 除以 $d$ 的帶餘除法 (Euclidean division) 為
進一步整理式子
已知 $(1-qs), -qt \in \mathbb{Z}$，所以 $r$ 實際上為 $ax+by$ 的形式，因此可以說 $r \in S \cup \{0\}$ (因為 $0 \leq r$)。而 $d$ 為 $S$ 集合中的最小值，使餘數 $r$ 不可能存在於 $S$ (因為 $r \lt d$)，即 $r$ 必須為 0，得證 $d \mid a$。
同理可證，$d \mid b$。
證明 $c \leq d$
令 $c$ 為 $a$ 與 $b$ 的公因數，存在 $u$ 與 $v$ ($u, v \in \mathbb{Z}$) 使 $a = cu,b = cv$，則 $d$ 可表示為
因為 $(ux+vy) \in Z$，所以 $c \mid d$，且 $d \gt0$，因此 $c \leq d$，也就是說 $d = gcd(a,b)$。
得證
