一次同余式

1. 标准形式

$a x \equiv b (mod m)$ 其中 $a, b, m$ 为整数，且 $m > 0$ 。

设 $d = g cd (a, m)$ 。

无解：如果 $d ∤ b$ （即 $d$ 不能整除 $b$ ），则方程无解。
有解：如果 $d ∣ b$ ，则方程恰有 $d$ 个 模 $m$ 不同余的解。
- 必要性：若 $(a x \equiv b (mod m))$ ，则 $(m ∣ (a x - b)$ )，即存在整数 k 使得 $(a x - b = mk$ )，整理得 $(a x - mk = b$ )。
- 充分性类似，即 ax - mk = b

假设 $d = (a, m)$ 且 $d ∣ b$ 。

化简方程：将原方程两边及模数同时除以 $d$ ，得到一个新方程： $a^{'} x \equiv b^{'} (mod m^{'})$ 其中 $a^{'} = a / d, b^{'} = b / d, m^{'} = m / d$ 。此时 $g cd (a^{'}, m^{'}) = 1$ 。
求逆元：利用 扩展欧几里得算法 求出 $a^{'}$ 模 $m^{'}$ 的逆元 $(a^{'})^{- 1}$ 。即求解 $a^{'} x + m^{'} y = 1$ ，得到的 $x$ 即为逆元。
求特解：计算特解 $x_{0}$ ： $x_{0} \equiv (a^{'})^{- 1} \cdot b^{'} (mod m^{'})$
写出通解：在模 $m$ 意义下，所有 $d$ 个解为： $x_{k} \equiv x_{0} + k \cdot m^{'} (mod m), k = 0, 1, \dots, d - 1$

题目：求解 $980 x \equiv 1500 (mod 1600)$ 。

解：

判定： $a = 980, m = 1600$ 。计算 $d = (980, 1600) = 20$ 。因为 $20 ∣ 1500$ （ $1500 = 75 \times 20$ ），所以有解，且有 20个解。
化简：除以 20，得到新方程： $49 x \equiv 75 (mod 80)$ 其中 $a^{'} = 49, b^{'} = 75, m^{'} = 80$ 。
求逆：求 $49$ 模 $80$ 的逆元。利用辗转相除法可得 $19 \times 80 - 31 \times 49 = 1$ 。 $⟹ - 31 \times 49 \equiv 1 (mod 80)$ 。 $⟹ 4 9^{- 1} \equiv - 31 \equiv 49 (mod 80)$ 。
特解： $x_{0} \equiv 49 \times 75 (mod 80)$ $x_{0} \equiv 3675 (mod 80) \equiv 75$ 。
通解： $x \equiv 75 + 80 k (mod 1600), k = 0, 1, \dots, 19$