一次同余方程

一次同余方程 $ax \equiv b \pmod m$ 是同余理论中的基本方程，中国剩余定理把多个这样的方程组合并求解。

解的存在与个数

方程 $ax \equiv b \pmod m$ 有解当且仅当 $\gcd(a,m)\mid b$。有解时，模 $m$ 下恰有 $\gcd(a,m)$ 个互不同余的解。

解法

设 $g = \gcd(a,m)$。当 $g\mid b$ 时：

1. 约去 $g$：令 $a_1 = \dfrac{a}{g}$，$b_1 = \dfrac{b}{g}$，$m_1 = \dfrac{m}{g}$，原方程等价于 $a_1x \equiv b_1 \pmod{m_1}$，此时 $\gcd(a_1, m_1) = 1$
2. 用扩展欧几里得算法（见最大公因数）求 $a_1$ 模 $m_1$ 的逆元 $a_1^{-1}$，满足 $a_1a_1^{-1}\equiv 1 \pmod{m_1}$
3. $x \equiv a_1^{-1}b_1 \pmod{m_1}$，展开为模 $m$ 下的 $g$ 个解 $x_0,\ x_0+m_1,\ \dots,\ x_0+(g-1)m_1$

示例

• 解 $3x \equiv 2 \pmod 7$：$\gcd(3,7)=1$，$3^{-1}\equiv 5 \pmod 7$（$3\cdot 5 = 15 \equiv 1$），故 $x \equiv 5\cdot 2 = 10 \equiv 3 \pmod 7$
• 解 $6x \equiv 4 \pmod{10}$：$g = 2 \mid 4$，约去得 $3x \equiv 2 \pmod 5$，解得 $x \equiv 4 \pmod 5$，即 $x \equiv 4,\ 9 \pmod{10}$
• $2x \equiv 1 \pmod 4$：$g = 2 \nmid 1$，无解（$2x$ 模 $4$ 只取 $0, 2$，不可能等于 $1$）