比舒公式(Bézout's Lemma / Bézout's Identity)係十八世紀法國數學家Étienne Bézout推廣出去(唔係證明)嘅定理。佢主要將兩個數字同佢哋嘅GCD寫成一條數學式。佢可以用喺整數度,除咗整數入面,亦可以擴展到域中多項式。比舒公式係數論入面同抽象代數入面一條好基
假設有兩個整數 a , b ∈ Z {\displaystyle a,b\in \mathbb {Z} } ,而且 a , b ≠ 0 {\displaystyle a,b\neq 0} 。咁樣就一定有一個 x , y ∈ Z {\displaystyle x,y\in \mathbb {Z} } 符合以下:
利用輾轉相除法,得知一系列嘅數學等式:
得知 g c d ( a , b ) = r n − 1 {\displaystyle gcd(a,b)=r_{n-1}} 。利用逆代入法,
如果a同b係相對質數,即係 g c d ( a , b ) = 1 {\displaystyle gcd(a,b)=1} ,咁樣就會有兩個整數 x , y ∈ Z {\displaystyle x,y\in \mathbb {Z} } 令到 a x + b y = 1 {\displaystyle ax+by=1} 。
證明:
因為比舒公式, g c d ( a , b ) = a x + b y {\displaystyle gcd(a,b)=ax+by} 。而同時因為, g c d ( a , b ) = 1 {\displaystyle gcd(a,b)=1} ,所以 a x + b y = 1 {\displaystyle ax+by=1} 。
如果 g c d ( a , b ) = d {\displaystyle gcd(a,b)=d} ,咁呢 ( a d ) x + ( b d ) y = 1 {\displaystyle ({\frac {a}{d}})x+({\frac {b}{d}})y=1} 。
因為比舒公式, d = a x + b y {\displaystyle d=ax+by} 。而同時因為, d | a {\displaystyle d|a} 同 d | b {\displaystyle d|b} ,所以 d | a {\displaystyle d|a} 同 d | b {\displaystyle d|b} 都係一個整數,根據以上定理, g c d ( a d , b d ) = 1 {\displaystyle gcd({\frac {a}{d}},{\frac {b}{d}})=1} ,所以 a d {\displaystyle {\frac {a}{d}}} 同 b d {\displaystyle {\frac {b}{d}}} 都係一個相對質數。