同余方程与不定方程

Dec 18, 2025

不定方程

在引入同余方程前，我们先讨论一种最简单的二元一次不定方程的解的有关问题

假设有不定方程

ax + by=c

则有结论：该方程有解的充要条件是 $gcd(a,b) | c$

引理：贝祖定理，设 $d = gcd(a,b)$ ，则存在整数 $u,v$ 使得

au + bv = d

贝祖定理的证明有两种方法。

考虑集合

S = \{ax + by | x,y \in \mathbb{Z} \}

设

S^+ = \{m \in S | m>0 \}

由于 $a,b$ 不全为 $0$ ，则假设 $a \not ={0}$ ，考虑 $x = \pm 1$ 使得 $ax > 0$ ,显然有 $|a| \in S^+$ ，故 $S^+$ 非空。

由良序原理知， $S^+$ 有最小元

d = \underset{min}{S^+}

此时设 $d = ax_0 + by_0$

用 $d$ 对 $a$ 做带余除法：

a = qd + r \,\, (0 \le r < d)

则

r = a - qd = a - q(ax_0 + by_0) = a(1 - qx_0) + b(-qy_0)

则显然有 $r \in S$

若 $r > 0$ ，则 $r \in S^+$ ，且 $r < d$ ，与 $d$ 的最小性矛盾，故 $r = 0$

故 $d | a$ ，同理可证 $d | b$

下证 $d$ 在 $a,b$ 的正约数集合中的最大性

设 $c$ 为 $a,b$ 的一个正约数，则有 $c | (ax_0 + by_0 = d)$ ，所以 $c \le d$ ，故 $d$ 为 $a,b$ 的最大公约数。

则此时取 $u = x_0,v = y_0$ ，即有贝祖定理得证。

由扩展欧几里得算法可推出，此处不再赘述。

下面回到对充分性的证明：

考虑贝祖定理的表达式：

au + bv = d

由 $d | c$ 得，存在整数 $k$ ，使得 $c = kd$

则方程两边同乘 $k$ 得：

a(uk) + b(vk) = dk = c

则取 $x_0 = uk,y_0 = vk$ ，此时 $x_0,y_0$ 为方程的一组解，充分性成立。

设存在一组解 $x_0,y_0$ 使得 $ax_0 + by_0 = c$ ，则由公约数的性质得：

d | ax_0 +by_0 =c

故 $d|c$ ，必要性得证。

我们先介绍最简单的一次同余方程：

ax \equiv b \,\, (mod \,\, m)

设 $ax = k_1c + r ,b = k_2c + r$ ,两式相减得：

ax - b = (k_1 - k_2)m

整理得：

ax + m(k_2 - k_1) = b

设 $t = k_2 - k_1$ ，则

ax + mt = b

显然这是一个二元一次不定方程，套用我们刚刚的结论， $x$ 有解当且仅当

gcd(a,m) | b

而对于一次同余方程的解，设 $d = gcd(a,m)$ ，则同样有贝祖定理

au + mv = d

设 $b = kd$

a(uk) + m(vk) = dk = b

则 $x = uk$ 即为原一次同余方程的解，此时我们要求解 $u$ ,可以使用扩展欧几里得算法来求解。