定义
设 ((a, b) = d), 则对于任意整数 (x, y), 有 (d | (ax + by)) 成立;
特别地, 一定存在 (x, y) 满足 (ax + by = d).
等价的表述:不定方程 (ax + by = c (a, b, c) 为整数 ()) 有解的充要条件为 ((a, b) | c)
推论
(a,b) 互质等价于 (ax + by = 1) 有解
证明
((1)) 若 (b = 0), 则 ((a, b) = a).这时定理显然成立
((2)) 若 (a, b) 都不等于 (0)
设 (a, b > 0) 且 (a geqslant b, (a, b) = d)
对 (ax + by = d) ,两边同时除以 (d), 可得 (a_1x + b_1y = 1), 其中 ((a1, b1) = 1)
所以现在就需要证 (a_1x + b_1y = 1)
我们可以先设整数 (r_1, r_2, r_3...r_n , q_1, q_2, q_3...q_{n + 1})
令 (a_1 = q_1b_1 + r_1,) 其中 (0 leqslant r_1 < b_1)
令 (b_1 = q_2r_1 + r_2,) 其中 (0 leqslant r_2 < r_1)
令 (r_1 = q_3r_2 + r_3,) 其中 (0 leqslant r_3 < r_2)
令 (r_2 = q_4r_3 + r_4,) 其中 (0 leqslant r_4 < r_3)
令 (r_{n - 3} = q_{n - 1}r_{n - 2} + r_{n - 1},) 其中 (0 leqslant r_{n - 1} < r_{n - 2})
令 (r_{n - 2} = q_{n}r_{n - 1} + r_{n},) 其中 (0 leqslant r_{n} < r_{n - 1})
令 (r_{n - 1} = q_{n + 1}r_{n}) ,即一直到 (r_n = 1)
于是有 ((a_1, b_1) = (b_1, r_1) = (r_1, r_2) = ... = (r_{n - 1}, r_n) = 1)
所以 (r_{n - 2} = q_nr_{n - 1} + 1)
即 (1 = r_{n - 2} - q_nr_{n - 1})
同理可以把以上式子全部转换
把 (r_{n - 1} = r_{n - 3} - q_{n - 1}r_{n - 2}) 带入上式, 得
(1 = (1 + x_nx_{n - 1})r_{n - 2} - q_nr_{n - 3})
然后不断地往上带, 逐个的消去 (r_{n - 2}, r_{n - 3}...r_1)
然后即可证得 (1 = a_1x + b_1y)