裴蜀定理
裴蜀定理
描述
對於任何整數 \(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\) 依然有整數解。
推廣
裴蜀定理可以從兩個數推廣到三個數及以上。
