裴蜀定理
裴蜀定理
描述
对于任何整数 \(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\) 依然有整数解。
推广
裴蜀定理可以从两个数推广到三个数及以上。
