0%

Bézout's identity 貝祖等式的詳細證明

前言

貝祖曾說:對任意兩整數 $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.

  1. 每組 $gcd(a,b)=ax+by$ 的整數解 $x,y$ 都稱為 $(a,b)$ 的貝祖係數 (Bézout coefficients),貝祖係數並不唯一。
  2. 貝祖係數可以透過擴展歐幾里得演算法 (Extended Euclidean algorithm) 求出。

證明 Bézout's identity

目標:證明 $gcd(a,b)=ax+by$ 有整數解

給任意兩非零整數 $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)$),必須依序證明以下兩點

  1. $(d \mid a) \land (d \mid b)$:$d$ 是 $a$ 與 $b$ 的公因數。
  2. $c \leq d$:任何其他 $a$ 與 $b$ 的公因數 $c$ 都滿足 $c \leq d$,意味著 $d = gcd(a,b)$。

證明 $(d \mid a) \land (d \mid b)$

  1. 證明 $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$。

  2. 同理可證,$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)$。

得證

參考資料

  1. Bézout's identity

  2. Extended Euclidean algorithm

  3. Well-ordering principle

很高興能在這裡幫助到您,歡迎登入 Liker 為我鼓掌 5 次,或者成為我的讚賞公民,鼓勵我繼續創造優質文章。
以最優質的內容回應您的鼓勵