最后更新: 2023-11-09 18:46 查看: 181 次高考专区考研专区公式专区刷题专区词条搜索

一次同余方程

**1. 一次同余方程**

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

例如, 在模 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)$ 个解.
下面看一个解一次同余方程例子.

**2. 大衍求一术**

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

大衍求一术是解一次同余方程 $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)$ 的解.
下面考察一下大衍求一术的算法原理.
我们发现，

$$
\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)$. 这就是大衍求一术的算法原理.
下面看一个用大衍求一术解同余方程的例子.
例 6 解同余方程 $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) .

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

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

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

制作不易，如果您喜欢本站，也欢迎赞助本站。