最后更新: 2025-10-16 09:45 查看: 263 次纠错评论(0) 课件开VIP

一次同余方程

## 一次同余方程

前面已经提到, 剩余类可以看作特殊的 “数”, 剩余类环可以看作是定义了剩余类加法和剩余类乘法运算的“数集”. 类似于实数集情形, 我们也可以在剩余类环中解方程或方程组.

例如, 在模 6 的剩余类环中解方程 $[5][x]=[3]$, 这里, $[x]$ 是模 6 的剩余类环中的未知剩余类. 注意到在模 6 的剩余类环中, 有

$$
[5][x]=[3] \Leftrightarrow[5 x]=[3] \Leftrightarrow 6 \mid 5 x-3 \Leftrightarrow 5 x \equiv 3(\bmod 6),
$$

因此, 原方程可表示成下面含未知数的同余式:

$$
5 x \equiv 3(\bmod 6) .
$$

通常, 我们把含有未知数的同余式叫做**同余方程**. 方程 $5 x \equiv 3(\bmod 6)$ 是一类形式最简单的同余方程, 叫做**一次同余方程**. 一次同余方程的一般形式为

$$
a x \equiv b(\bmod n),
$$

其中 $n$ 为正整数, $a, b$ 为整数, 且 $a$ 不等于零.
若存在整数 $c$, 使得同余式 $a c \equiv b(\bmod n)$ 成立, 则把 $x \equiv c(\bmod n)$ 叫做一次同余方程 $a x \equiv b(\bmod n)$ 的解. 例如, $x \equiv 3(\bmod 6)$ 是 $5 x \equiv 3(\bmod 6)$ 的解.

如果 $x \equiv d(\bmod n)$ 也是同余方程 (1) 的解, 且 $c \equiv d(\bmod n)$, 那么我们将这两个解视作一样的. 实际上, 在这种意义下, 一次同余方程的解可理解为模 $n$ 的一个剩余类, 是一个集合, 而不是一个整数. 因此, 要判断一个模 $n$ 的剩余类是不是同余方程的解, 只需选取剩余类中的一个代表元, 看它是否使同余式成立即可.

由上面的分析可知, 解剩余类环中的方程总可以转化为解某个同余方程. 与我们熟悉的解一元一次方程、一元二次方程等过程类似, 对于一次同余方程, 我们关心下面几个问题:
(1) 一次同余方程 $a x \equiv b(\bmod n)$ 什么情况下有解?
(2) 有多少解?
(3) 有解时如何描述所有的解?
$1^{\circ}$ 先讨论特殊情形, 即当 $(a, n)=1$ 的情形.
我们知道, 当 $(a, n)=1$ 时, 存在整数 $k, l$, 使得 $a k+n l=1$, 于是 $n \mid n l=1-a k$,
即

$$
a k \equiv 1(\bmod n) .
$$

因此, $a x \equiv b(\bmod n) \Leftrightarrow a x \equiv(a k) b=a(k b)(\bmod n) \Leftrightarrow x \equiv k b(\bmod n)$.
因此, 同余方程 (1) 仅有一个解 $x \equiv k b(\bmod n)$.
$2^{\circ}$ 再讨论 $(a, n)=d>1$ 的情形.
若同余方程 (1) 有解, 不妨设 $x \equiv c(\bmod n)$ 为它的一个解, 则 $a c \equiv b(\bmod n)$, 从而 $n \mid a c-b$. 由于 $d|a, d| n$, 故 $d|a c, d| a c-b$, 从而 $d \mid a c-(a c-b)=b$. 这表明,同余方程(1)有解时, 必有 $d \mid b$.
那么, 当 $d \mid b$ 时, 同余方程(1) 是否一定有解呢?
记 $a=a^{\prime} d, n=n^{\prime} d, b=b^{\prime} d$, 则 $\left(a^{\prime}, n^{\prime}\right)=1$. 注意到,

$$
a x \equiv b(\bmod n) \Leftrightarrow n\left|a x-b \Leftrightarrow n^{\prime} d\right|\left(a^{\prime} x-b^{\prime}\right) d \Leftrightarrow n^{\prime} \mid a^{\prime} x-b^{\prime},
$$

于是同余方程(1)可化简为

$$
a^{\prime} x \equiv b^{\prime}\left(\bmod n^{\prime}\right) .
$$

由于 $\left(a^{\prime}, n^{\prime}\right)=1$, 由情形 $1^{\circ}$ 的讨论知, 同余方程 (2) 有惟一解 $x \equiv k^{\prime} b^{\prime}\left(\bmod n^{\prime}\right)$, 此时 $x=k^{\prime} b^{\prime}+n^{\prime} l$, 其中 $l$ 为任意整数.
对 $l, d$ 用带余除法: $l=d q+r, 0 \leqslant r \leqslant d-1$, 则

$$
x=k^{\prime} b^{\prime}+n^{\prime}(d q+r)=k^{\prime} b^{\prime}+n q+n^{\prime} r,
$$

其中 $0 \leqslant r \leqslant d-1, q$ 为整数. 于是

$$
x \equiv k^{\prime} b^{\prime}+n^{\prime} r(\bmod n), r=0,1, \cdots, d-1 .
$$

容易检验, 它们都是同余方程 (1) 的解.
综上所述, 我们得到下面的结论.

> 一次同余方程 $a x \equiv b(\bmod n)$ 有解, 则 $(a, n) \mid b$, 反过来, 当 $(a, n) \mid b$ 时, 一次同余方程 $a x \equiv b(\bmod n)$ 恰有 $(a, n)$ 个解.

下面看一个解一次同余方程例子.

`例` 解一次同余方程 $9 x \equiv 6(\bmod 15)$ 。
解：注意到 $(9,15)=3$ ，且 $3 \mid 6$ ，故同余方程有三个解．原同余方程可化简为 $3 x \equiv$ $2(\bmod 5)$ 。由于 $3 \times 2 \equiv 1(\bmod 5)$ ，故 $x \equiv 2 \times 2=4(\bmod 5)$ 。所以，原同余方程的三个解分别为 $x \equiv 4+5 \times 0=4(\bmod 15), x \equiv 4+5 \times 1=9(\bmod 15), x \equiv 4+5 \times 2=14(\bmod 15)$ ．

### 大衍求一术

对于一次同余方程的解法, 我们古代一些数学家曾做出过巨大的贡献, 其中比较有名的是大衍求一术.

大衍求一术是解一次同余方程 $a x \equiv 1(\bmod n)$, 其中 $a$ 为正整数, $a<n$, 且 $(a, n)=1$的一种算法程序. 我国宋代大数学家秦九韶（约 1202 - 约 1261）继承前人造历算法经验,在其所著的《数书九章》中给出了解法:
秦九韶称 $a$ 为衍母, $n$ 为定母, 并称满足同余式的最小正整数为乘率. 大衍求一术的
法则是：
置衍右上, 定居下. 立天元一于左上. 先以右上除右下, 所得商数与左上一相生并人左下. 然后乃以右行上下, 以少除多, 递互除之. 所得商数, 随即递互累乘. 归左行上下……须使右上末后奇一而止. 乃验左上所得, 以为乘率.
用现代数学的语言, 大衍求一术的算法步骤可表述为:
先规定 $k_1=1, r_1=a$,
对 $n, a$ 用带余除法: $n=a q_2+r_2$, 记 $k_2=-q_2 k_1$;
对 $a, r_2$ 用带余除法: $a=r_2 q_3+r_3$, 记 $k_3=k_1-q_3 k_2$;
对 $r_2, r_3$ 用带余除法: $r_2=r_3 q_4+r_4$, 记 $k_4=k_2-q_4 k_3$;
对 $r_3, r_4$ 用带余除法: $r_3=r_4 q_5+r_5$, 记 $k_5=k_3-q_5 k_4$;

重复这种运算, 直到余数 $r_n=1$, 那么最后所得 $k_n=k_{n-2}-q_n k_{n-1}$ 满足 $a k_n \equiv 1(\bmod n)$. 于是 $x \equiv k_n(\bmod n)$ 就是一次同余方程 $a x \equiv 1(\bmod n)$ 的解.

**试将大衍求一术算法步骤中的余数 $r_2, r_3, r_4, r_5$ 分别写成 $a x+n y$ 的形式，从中你能发现什么规律？**

下面考察一下大衍求一术的算法原理.
我们发现，

$$
\begin{aligned}
& r_1=a=a k_1(\bmod n), \\
& r_2=n-r_1 q_2 \equiv a\left(-q_2 k_1\right)=a k_2(\bmod n), \\
& r_3=r_1-r_2 q_3 \equiv a\left(k_1-q_3 k_2\right)=a k_3(\bmod n), \\
& r_4=r_2-r_3 q_4 \equiv a\left(k_2-q_4 k_3\right)=a k_4(\bmod n), \\
& \cdots \cdots
\end{aligned}
$$

而 $r_n=1$, 故 $a k_n \equiv 1(\bmod n)$. 这就是大衍求一术的算法原理.
下面看一个用大衍求一术解同余方程的例子.

`例`解同余方程 $33 x \equiv 1(\bmod 74)$.
解: 显然 $(33,74)=1$.
由于 $74=33 \times 2+8,33=8 \times 4+1$, 故 $q_2=2, q_3=4, r_3=1$. 依次可计算出

$$
k_2=-2 \times 1=-2, k_3=1-4 \times(-2)=9 .
$$

因此原方程的解为

$$
x \equiv 9(\bmod 74) .

## 欧几里得算法

**同余方程** 是形如：
$$
a x \equiv b \pmod{m}
$$
的方程，其中 $ a, b, m $ 是已知整数，$ m > 0 $，$ x $ 是未知整数。

它的意思是：寻找所有整数 $ x $，使得 $ a x - b $ 能被 $ m $ 整除。

**方法1**：转化为线性丢番图方程

原方程 $ a x \equiv b \pmod{m} $ 等价于：
$$
a x - b = m y \quad \text{（其中 } y \text{ 是整数）}
$$
即：
$$
a x - m y = b
$$
这是一个线性丢番图方程，可以用**扩展欧几里得算法**求解。

**方法2**：具体步骤（举例说明）

**例**：解 $ 6x \equiv 4 \pmod{10} $

1. **检查是否有解**：
   $$
   \gcd(6, 10) = 2, \quad 2 \mid 4 \ \Rightarrow\ \text{有解，且恰有 2 个解（模 10）}
   $$

2. **化简方程**：
   两边同时除以最大公约数 2：
   $$
   3x \equiv 2 \pmod{5}
   $$

3. **求乘法逆元**：
   在模 5 下，求 3 的逆元。因为 $ 3 \times 2 = 6 \equiv 1 \pmod{5} $，所以 3 的逆元是 2。

4. **两边乘以逆元**：
   $$
   2 \times 3x \equiv 2 \times 2 \pmod{5}
   $$
   $$
   x \equiv 4 \pmod{5}
   $$

5. **写出模 10 下的所有解**：
   从 $ x \equiv 4 \pmod{5} $ 可知，在 0 到 9 范围内，$ x $ 可以是 4 和 4+5=9。
   $$
   x \equiv 4 \ \text{或}\ 9 \pmod{10}
   $$

**方法3**：利用扩展欧几里得算法

对于 $ a x \equiv b \pmod{m} $：

1. 令 $ d = \gcd(a, m) $。
2. 如果 $ d \nmid b $，则无解。
3. 如果 $ d \mid b $，用扩展欧几里得算法求：
   $$
   a u + m v = d
   $$
   的一组解 $ (u_0, v_0) $。
4. 那么原方程的一个特解是：
   $$
   x_0 = u_0 \cdot \frac{b}{d}
   $$
5. 所有解为：
   $$
   x \equiv x_0,\ x_0 + \frac{m}{d},\ x_0 + 2\frac{m}{d},\ \dots,\ x_0 + (d-1)\frac{m}{d} \pmod{m}
   $$

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：费马小定理与欧拉定理

下一篇：拉格朗日插值与孙子定理

本文对您是否有用？有用 (0) 无用 (0)