比舒公式

比舒公式（Bézout's Lemma / Bézout's Identity）係十八世紀法國數學家Étienne Bézout推廣出去（唔係證明）嘅定理。佢主要將兩個數字同佢哋嘅GCD寫成一條數學式。佢可以用喺整數度，除咗整數入面，亦可以擴展到域中多項式。比舒公式係數論入面同抽象代數入面一條好基

定理

假設有兩個整數$a,b\in \mathbb {Z}$，而且$a,b\neq 0$。咁樣就一定有一個$x,y\in \mathbb {Z}$符合以下：

$$gcd(a,b)=ax+by$$

證明

利用輾轉相除法，得知一系列嘅數學等式：

$${\begin{aligned}a&=bq_{0}+r_{0}\\b&=r_{0}q_{1}+r_{1}\\.\\.\\.\\r_{n-3}&=r_{n-2}q_{n-1}+r_{n-1}\\r_{n-2}&=r_{n-1}q_{n}+r_{n}\\\end{aligned}}$$

得知$gcd(a,b)=r_{n-1}$。利用逆代入法，

$${\begin{aligned}gcd(a,b)&=r_{n-2}-r_{n-1}q_{n}\\&=r_{n-2}-q_{n}(r_{n-3}-r_{n-2}q_{n-1})\\&.\\&.\\&.\\&=ax+by\end{aligned}}$$

推論

如果a同b係相對質數，即係$gcd(a,b)=1$，咁樣就會有兩個整數$x,y\in \mathbb {Z}$令到$ax+by=1$。

證明：

因為比舒公式，$gcd(a,b)=ax+by$。而同時因為，$gcd(a,b)=1$，所以$ax+by=1$。

如果$gcd(a,b)=d$，咁呢$({\frac {a}{d}})x+({\frac {b}{d}})y=1$。

證明：

因為比舒公式，$d=ax+by$。而同時因為，$d|a$同$d|b$，所以$d|a$同$d|b$都係一個整數，根據以上定理，$gcd({\frac {a}{d}},{\frac {b}{d}})=1$，所以${\frac {a}{d}}$同${\frac {b}{d}}$都係一個相對質數。

睇埋

• 最小公倍數
• 最大公因數
• 歐幾理得推論
• 相對質數