前言
在学习本节内容前，请确保已完成了二元不定方程的学习。
同余方程
有无解的判别
对于一个方程形如：
ax \equiv b \pmod m
其中
a,b \in \mathbb Z , m \in \mathbb Z^+
并令
d=(a,m)
若
则方程
$ax \equiv b \pmod m
无解。
若
则方程
$ax \equiv b \pmod m
恰有 d 个模 m 不同余的解。
证明
线性同余方程 ax \equiv b \pmod m 等价于二元不定方程 ax - my = b.
整数 x 是方程的解，当且仅当存在整数 y 使得 ax - my = b.
由上篇二元一次不定方程的学习，我们可知：若 d \nmid b ，则无解；而 d \mid b 时，则有无穷多解。
且方程 ax - my = b 的解： x=x_0 + (m/d)t , y = y_0 + (a/d)t。
为确定有多少不同余的解，我们来找一下当
x_1 = x_0 + (m/d)t_1
和
x_2 = x_0 + (m/d)t_2
这两个解同余的条件。
x_1 \equiv x_2 \pmod m
x_0 + (m/d)t_1 \equiv x_0 + (m/d)t_2 \pmod m
(m/d)t_1 \equiv (m/d)t_2 \pmod m
由二元一次不定方程的定理5可得：
t_1 \equiv t_2 \pmod d
这表明只要我们将 t 取 0,1,2,…,d-1 , 就可以得到不同余的全部解（共 d 个模 m 不同余的解）。
若
a,b \in \mathbb Z,m \in \mathbb Z^+,(a,m)=1
则对于同余方程
ax \equiv b \pmod m
恰有 1 个模 m 不同余的解。