從最大公因數到所有可達的值
固定不全為零的整數 。正的最大公因數 同時整除兩數。因此每個整數組合 都被 整除。這是方程 有整數解的必要條件:若 ,便無解。值得注意的是,這個基本障礙也是唯一的障礙。
定義 3.5.1
(最大公因數與貝祖證書)
對不全為零的整數 , 是同時整除兩者的最大正整數。它的貝祖(Bézout)證書是一對整數 ,滿足 。
定理 3.5.2
(貝祖等式與可達的值)
若 不全為零,且 ,則存在整數 使 ,並且
證明
(最小的正組合就是最大公因數)
至少有一個非零;必要時改變符號,即得一個正整數組合。令 是最小的正組合。用 除 得 ,其中 。由於 和 都是 的整數組合, 也是。若 ,便與 的最小性矛盾;故 。同理 。 的每個公因數都整除每個整數組合,特別是 。因此 ,其構造正給出貝祖等式。
至於集合等式,每個組合都被 整除。反過來,若 , 為整數,把 乘以 便得 。
這裏把除法算法當作前置知識,而不是暗中容許負餘數。約定 保證非零餘數會成為更小的正組合。集合等式包含兩個方向。它並非說任意組合都等於最大公因數,也沒有說貝祖係數唯一。
不只一個解,而是所有解
定理 3.5.3
(整數解的完整解族)
設 不全為零,,且 。設 是 的一組整數解,並令 、。則 ,而所有整數解為
證明
(先代入,再相減)
直接代入可證每一對都有效。反過來,設另一組解為 ,寫 、。相減得 。
若 ,則 。由互質及貝祖等式可得 :若 ,兩邊乘 便把 寫成 的倍數之和。令 ;原式給出 ,故消去得 。若 ,則 ,方程強迫 ;任意整數 都可對某個整數 寫成 。因此同一公式也涵蓋這個零係數情況。證明包含負係數,整除均按整數定義理解。
證明透視
互質性在解族證明中的位置
這個論證只有一個真正的想法:除以 之後, 互質,而正是互質性把 變成 。在此之前都只是整理:兩組解相減會消去右邊,剩下齊次方程 。貝祖等式在這裏第二次出現,這次用於 ,寫出 ,把整除性從乘積移到單一因數。最後消去 之所以合法,是因為 ; 的情形不是事後補充的退化例子,而是必須單獨處理,因為此時消去不合法。若不先除以 ,論證只能得到 ,無法除掉 ,這就是解族中步長是 而不是 的原因。
若 ,則我們採用的正最大公因數約定不適用。方程變為 :當 時每一對整數都是解;當 時無解。這個情況必須分開處理,不能除以零的最大公因數。
反例模式
步長是係數除以最大公因數,而不是係數本身
命題:若 是 的一組解,則所有解為 、。以 及 檢驗,後者成立,因為 。數對 也是解:,,而 。但 不是 的倍數,所以命題漏掉了它。正確的步長是 和 :取 得 、。補救辦法是先除以最大公因數。
下面的互動圖對選定的 a、b、c 作擴展歐幾里得(Euclid)算法,列出解族 、 並逐一核對各成員,也顯示你輸入的數對在解族中的位置。
ax + by = c 的全部整數解
選定 a、b、c。互動圖對 |a|、|b| 作擴展歐幾里得算法,並按 a、b 的正負號調整,得 a·u + b·v = d;然後列出整個解族 x = x₀ + (b/d)t、y = y₀ − (a/d)t,或給出無整數解的整除理由。你也可以輸入自己的數對,看它對應哪一個參數 t。
輸入至多四位的整數。把任何一格清空即取消檢驗。
方程: 84x + 66y = 6
第 0 行與第 1 行分別是 |a|、|b|。其後每行等於上兩行減去 q 乘上一行(q 是兩個餘數的商),並滿足 |a|·s + |b|·t = r。最後一個非零的 r 就是 d;把 s、t 分別乘以 a、b 的正負號,便得 u、v。
| 行 | 商 q | 餘數 r | s(對應 |a|) | t(對應 |b|) |
|---|---|---|---|---|
| 0 | — | 84 | 1 | 0 |
| 1 | — | 66 | 0 | 1 |
| 2 | 1 | 18 | 1 | −1 |
| 3 | 3 | 12 | −3 | 4 |
| 4 | 1 | 6 | 4 | −5 |
| 5 | 2 | 0 | −11 | 14 |
貝祖憑證: 84·4 + 66·(−5) = 6
因為 d = 6 整除 6,取 k = 6/6 = 1。則 (x₀, y₀) = (u·k, v·k) = (4, −5) 是一組解,而所有解為 x = 4 + 11t、y = −5 − 14t,其中 t 為整數。
| t | x | y | a·x + b·y | 是否等於 c |
|---|---|---|---|---|
| −3 | −29 | 37 | 6 | ✓ |
| −2 | −18 | 23 | 6 | ✓ |
| −1 | −7 | 9 | 6 | ✓ |
| 0 | 4 | −5 | 6 | ✓ |
| 1 | 15 | −19 | 6 | ✓ |
| 2 | 26 | −33 | 6 | ✓ |
| 3 | 37 | −47 | 6 | ✓ |
檢驗你自己的數對
請同時輸入 x 與 y 才能檢驗。
直線 a·x + b·y = c 與標出的整數解
圓圈標出 t = −3, …, 3 的七個成員,上表列出相同的點。虛線是 a·x + b·y = c,實線是坐標軸。若你的檢驗數對是解且落在圖框內,較大的實心圓就是它。
- gcd(a, b)
- 6
- 貝祖憑證
- 84·4 + 66·(−5) = 6
- 是否有整數解
- 是
- 特解 (x₀, y₀)
- (4, −5)
- x 每次改變 b/d =
- 11
- y 每次改變 −a/d =
- −14
84x + 66y = 6:d = 6 整除 6;解為 x = 4 + 11t、y = −5 − 14t。
請同時輸入 x 與 y 才能檢驗。
為甚麼解族是完整的
因為 d 整除 a 和 b,所以每個 a·x + b·y 都是 d 的倍數;故 d ∤ c 時無解。若 d | c,把貝祖等式 a·u + b·v = d 乘以 k = c/d,得 a(uk) + b(vk) = c。
若 (x, y) 是另一組解,相減得 a′(x − x₀) + b′(y − y₀) = 0,其中 a′ = a/d、b′ = b/d 互質。於是 b′ 整除 x − x₀,設 x − x₀ = b′t,約去 b′ 得 y − y₀ = −a′t。反過來,每個整數 t 都給出解,因為含 t 的項互相抵消。
係數為零的情形也包括在內。若 b = 0,則 b′ = 0 且 a′ = ±1:x 固定在 x₀,參數要由 y 讀出。若 a = 0,則 b′ = ±1,由 x 讀出 t。若 a = b = 0,方程是 0 = c:c = 0 時每一對都是解,否則無解,且最大公因數沒有定義。
本圖涵蓋 |a| ≤ 99、|b| ≤ 99、|c| ≤ 200;解族有無限多個,只列出 t = −3, …, 3。切換預設或修改數值會重算整個過程。檢驗的數對只留在本頁,不會被儲存。
常見錯誤
(除同餘式後仍保留原來的模)
把 除以公因數 時,模也要一併除去:結果是 ,不是 。除後仍保留模 是錯誤的;它會排除原同餘式中成立的解 (),因為 ,而 。
例題
例題 3.5.4
(從歐幾里得到完整解族)
求 的全部整數解,給出貝祖證書並證明列出的解族完整。
反覆做除法得
最後的非零餘數是 。回代得
因此 ,一組解是 。由於 、,完整解族為
代入時參數項互相抵消;上面的定理證明沒有其他解。
例題 3.5.5
(無解的方程與可解的同餘式)
說明為何 沒有整數解,然後求滿足 的全部整數。
,因為 、、。每個 都被六整除,而七不是;因此方程不可能成立。
同餘式表示 ,等價於對某個整數 有 。此處可以用公因數六除同餘式,得到 。由於 且 ,乘以三得 。反過來,若 ,則 被 整除。因此所有解為 ,。
例題 3.5.6
(係數為零的情形)
求 的全部整數解。這裏 、,所以 ,它整除 。一組解是 。取 、,解族為 、。所以每個解都有 ,而 任意。直接看, 迫使 ,對 沒有任何條件,公式與此一致。若對 使用未約簡的步長 ,會把 限制為 的倍數,漏掉解 ,因為 。
練習
快速檢查
( 有整數解嗎?)
先計算係數的最大公因數。
解答 · 答案
,而 。每個值 都是 的倍數,所以沒有整數解。
快速檢查
(求 的全部整數解。)
先找 的貝祖證書,再按比例放大。
解答 · 答案
,乘以 得 ,故 。取 、,解為 、,。以 檢驗:、,而 。
快速檢查
(求所有滿足 的整數 。)
把同餘式寫成對某個整數 有 。
解答 · 答案
把 除以 得 ,所以 。解為 ;例如 時 。相除之後,模由 變成 。