[基础数论]同余方程笔记
前言
在学习本节内容前，请确保已完成了二元不定方程的学习。
同余方程
有无解的判别
对于一个方程形如：
\[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\) 不同余的解。