裴蜀定理
描述
對于任何整數 \(a\)、\(b\) 和 \(c\)，關于未知數 \(x\)、\(y\) 的不定方程 \(ax + by = c\) 有整數解時當且僅當 \(c\) 是 \(a\) 及 \(b\) 的最大公約數 \(d\) 的倍數，
即：不定方程 \(ax + by = c\) 有整數解的充分必要條件是 \(d \mid c\)，
裴蜀定理的一個重要推論是 \(a\) 與 \(b\) 互素的充分必要條件是存在整數 \(x\)、\(y\)，使 \(ax + by = 1\)，
證明
要證明裴蜀定理，需要分別證明它的充分性和必要性，
以下約定 \(d = \gcd(a, b)\)，
必要性
命題：若 \(ax + by = c\) 有整數解，\(d \mid c\)，
證明：
顯然 \(d \mid a, d \mid b\)，因為 \(x\) 和 \(y\) 均為整數，可得 \(d \mid ax, d \mid by\)，
將等式兩邊同時除以 \(d\)，得 \(\frac{ax}{d} + \frac{by}{d} = \frac{c}{d}\)，
因為已證 \(d \mid ax, d \mid by\)，顯然 \(\frac{ax}{d} + \frac{by}{d}\) 的值為整數，
所以要使等式成立，\(c\) 必然是 \(d\) 的倍數，即 \(d \mid c\)，
充分性
命題：若 \(d \mid c\)，則 \(ax + by = c\) 有整數解，
證明：
顯然 \(d \mid a, d \mid b\)，可描述：\(a = ud, b = vd\)，
\(c\) 可替代為 \(ud \cdot x + vd \cdot y = d(ux + vy)\)，顯然 \(d \mid c\)，
設 \(s\) 是 \(c\) 的最小正整數值，則 \(s\) 是 \(a\)、\(b\) 的線性組合，
設 \(r = a \bmod s\)，\(p = \lfloor \frac{a}{s} \rfloor\)，
由帶余除法定理可得 \(r = a - ps = a - p(ax + by) = a(1 - px) - bqy\)，
顯然 \(r\) 也是 \(a\)、\(b\) 的線性組合，
因為 \(r = a \bmod s\)，所以 \(0 \leq r < s\)，
若 \(0 < r < s\) 與 \(s\) 是 \(c\) 的最小正整數值矛盾，
所以 \(r = 0\)
因為 \(r = 0\) 且 \(r = a \bmod s\)，可得 \(s \mid a\)，
同理可證 \(s \mid b\)，
所以 \(s\) 是 \(a\) 和 \(b\) 的公約數，
因為 \(d\) 是 \(a\) 和 \(b\) 的最大公約數，
所以 \(d \geq s\)，
又因為已證 \(d \mid c\) 即 \(d \mid s\)，
所以 \(d \leq s\)，
聯立兩個不等式，解得 \(d = s\)，
即 \(ax + by\) 的最小整數解為 \(d\)，
顯然當 \(c\) 為 \(d\) 的整數倍時 \(ax + by = c\) 依然有整數解，
推廣
裴蜀定理可以從兩個數推廣到三個數及以上，
參考文獻
- Cnblog：Mystical-W
- 洛谷博客：ADay
- 洛谷博客：本喵
- 百度百科：充分必要條件
- 百度百科：線性組合
- 百度百科：裴蜀定理
- 知乎：Pecco
- 維基百科：帶余除法
- 維基百科：裴蜀定理
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/423379.html
標籤：其他