前言
在学习本节内容前，请确保已完成了二元不定方程的学习。
同余方程
有无解的判别
对于一个方程形如：
\[ax \equiv b \pmod m \]其中
\[a,b \in \mathbb Z , m \in \mathbb Z^+ \]并令
\[d=(a,m) \]若
\(d \nmid b\) ，
则方程
\(ax \equiv b \pmod m\)
无解。
若
\(d \mid b\) ，
则方程
\(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\) 不同余的解。
标签：mathbb,方程,数论,笔记,pmod,ax,同余,equiv From： https://www.cnblogs.com/wonder-land/p/17416719.html