[基础数论]同余方程笔记

· · 个人记录

前言

在学习本节内容前，请确保已完成了二元不定方程的学习。

同余方程

有无解的判别

对于一个方程形如：

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 不同余的解。