最后更新: 2025-10-16 08:49 查看: 288 次纠错评论(0) 课件开VIP

同余及其性质

## 同余的概念

观察下面的月历：

![图片](/uploads/2025-06/b5815e.jpg){width=400px}
 
在月历表中位于同一列的整数被 7 除后的余数是相同的, 如 $1,8,15,22,29$ 被 7 除后, 余数都是 1 . 在其他的月历中也有同样的规律.
我们把这些被 7 除后余数相同的整数称作是模 7 同余的.

> 一般地, 设 $n$ 为正整数, $a$ 和 $b$ 为整数. 如果 $a$ 和 $b$ 被 $n$ 除后余数相同, 那么称 $a$ 和 $b$模 $n$ 同余, 记作 $a \equiv b(\bmod n)$. 若 $a$ 和 $b$ 被 $n$ 除后余数不同, 则称 $a$ 和 $b$ 模 $n$ 不同余, 记作 $a \neq b(\bmod n)$.

例如, 12 与 -6 被 9 除后余数均为 3 , 所以 $12 \equiv$ $-6(\bmod 9)$, 而 -15 与 21 被 7 除后余数分别为 6 和 0 ,所以 $-15 \not \neq 21(\bmod 7)$.

## 同余与整除关系
由同余的概念, 我们容易知道, 同余与整除存在密切的关系.
设 $a, b$ 被 $n$ 除后的商分别为 $q, q^{\prime}$, 余数分别为 $r$, $r^{\prime}$, 则

$$
a=n q+r, \quad b=n q^{\prime}+r^{\prime} .
$$

若 $a \equiv b(\bmod n)$, 则 $r=r^{\prime}$, 并且 $a-b=n\left(q-q^{\prime}\right)$, 于是 $n \mid a-b$. 反过来, 若 $n \mid a$ $-b=n\left(q-q^{\prime}\right)+r-r^{\prime}$, 则 $n \mid r-r^{\prime}$, 而 $-n<r-r^{\prime}<n$, 故 $r-r^{\prime}=0$, 从而 $r=r^{\prime}$, 因此 $a \equiv b(\bmod n)$.
因此, 我们有

$$
\boxed{
a \equiv b(\bmod n) \Leftrightarrow n \mid a-b 
}

根据 $a \equiv b(\bmod n) \Leftrightarrow n \mid a-b$, 探索同余满足下面同余的三条性质:
（1）$a \equiv a(\bmod n)$;
（2）若 $a \equiv b(\bmod n)$, 则 $b \equiv a(\bmod n)$;
（3）若 $a \equiv b(\bmod n)$, 且 $b \equiv c(\bmod n)$, 则 $a \equiv c(\bmod n)$.

由上可知, 模 $n$ 同余给出了整数之间的一种关系, 这种关系我们称之为**同余关系**. 利用同余关系, 我们可以对整数集进行分类: 将整数集中所有模 $n$ 同余的整数放在一起构成一个集合.

例如, 利用模 2 同余可将整数集分成两个集合:
（1）模 2 同余于 0 的整数构成偶数集;
（2）模 2 同余于 1 的整数构成奇数集;

`例` 说明 $-1 \equiv 4(\bmod 5)$ 
解：$-1=(-1) \times 5+4$ ，此式表明，-1 除以 5 的余数是 4 ．

`例` 证明：对任何整数 $x, x^2 \equiv 0$ 或 $1(\bmod 4)$ ．
解：设 $x=4 k+r, r=0,1,2,3$ ，则

$$
\begin{aligned}
x^2 & =16 k^2+8 k r+r^2 \\
& =4\left(4 k^2+2 k r\right)+r^2, \\
\Rightarrow x^2 & \equiv r^2 \equiv 0 \text { 或 } 1(\bmod 4) .
\end{aligned}
$$

## 同余的性质 
从同余的概念和上面的探究, 我们不难发现, 同余式 $a \equiv b(\bmod n)$ 与等式 $a=b$ 有许多类似的性质.
 
1. 若 $a \equiv b(\bmod n)$, 且 $c \equiv d(\bmod n)$, 则
   (1) $a+c \equiv b+d(\bmod n)$;
   (2) $a c \equiv b d(\bmod n)$;
   (3) $k a \equiv k b(\bmod n), k$ 为任意整数;
   (4) $a^m=b^m(\bmod n), m$ 为正整数.
2. 若 $a b \equiv a c(\bmod n)$, 且 $(a, n)=1$, 则 $b \equiv c(\bmod n)$.

我们给出性质 1(1) 及性质 2 的证明, 余下的请同学们自己证明:
$1^{\circ}$ 证明：因为 $a \equiv b(\bmod n), c \equiv d(\bmod n)$,
所以 $n|a-b, n| c-d$,
因此 $n \mid c-d+a-b$, 即 $n \mid(a+c)-(b+d)$.
所以 $a+c=b+d(\bmod n)$.

性质1 说明, 类似整数集中两个等式两端对应加、减、乘仍得到等式, 同余式两端对应加、减、乘仍然是同余的.

$2^{\circ}$ 证明: 因为 $(a, n)=1$,
所以存在一对整数 $k, l$, 使得

$$
a k+n l=1 .
$$

因此 $n \mid n l=1-a k$, 即

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

又因为 $a b \equiv a c(\bmod n)$,
所以 $k a b \equiv k a c(\bmod n)$. 而 $k a \equiv 1(\bmod n)$,
因此 $b \equiv c(\bmod n)$.

性质2 可以看作是同余意义下的消去律, 消去律的前提是 $a$ 与 $n$ 必须互素, 否则结论不一定成立.

利用同余的这些性质, 我们可以简化数论中的许多问题.
先看星期几问题. 如果今天为星期天, 过 $n$ 天后的今天是星期几? 这个问题并不难回答, 我们只需对 $n$ 和 7 用带余除法, 由余数即可确定. 但是, 有时直接应用带余除法求余数是困难的, 特别是当被除数较大时, 如下例.

`例`今天为星期日, 过 $2004^{2004}$ 天后的今天是星期几?
分析: $2004^{2004}$ 这个数很大, 我们很难直接判断 7 除 $2004^{2004}$ 的余数是几. 现在, 我们想办法把 $2004^{2004}$ 变小. 一个自然的考虑是 7 除底数 2004 的余数是几, 利用这个余数替换底数 2004 , 然后降次, 反复进行这个过程, 直至去掉指数.
解: 因为 $2004=7 \times 286+2$, 所以 $2004 \equiv 2(\bmod 7)$.
由同余的性质, 有

$$
2004^{2004} \equiv 2^{2004}(\bmod 7),
$$

而 $2^{2004}=8^{668}$, 所以 $2^{2004} \equiv 8^{668}(\bmod 7)$.
又因为 $8 \equiv 1(\bmod 7)$, 所以 $8^{668} \equiv 1^{668}=1(\bmod 7)$.
因此 $2004^{2004} \equiv 1(\bmod 7)$, 即 7 除 $2004^{2004}$ 的余数为 1 , 所以过 $2004^{2004}$ 天后的今天是星期一.
再看一个整除问题的例子.

`例` 证明: $17 \mid 19^{1000}-1$.
分析: 类似例 1 , 我们想办法把 $19^{1000}$ 变小, 用 17 除底数 19 的余数替换底数 19 , 然后降次, 反复进行这个过程, 直至去掉指数.
证明: 要证 $17 \mid 19^{1000}-1$, 只需证 $19^{1000} \equiv 1(\bmod 17)$,因为 $19 \equiv 2(\bmod 17)$, 所以

$$
19^{1000} \equiv 2^{1000}=16^{250}(\bmod 17) .
$$

又由于 $16 \equiv-1(\bmod 17)$, 故 $16^{250} \equiv(-1)^{250}=1(\bmod 17)$.因此 $17 \mid 19^{1000}-1$.

`例` 证明： $641 \mid F_5$ ，其中 $F_5=2^{32}+1$ ．
证明： $2^8=256,2^{16}=65536 \equiv 154(\bmod 641)$ 。 $2^{32} \equiv(154)^2=23716 \equiv 640 \equiv-1(\bmod 641)$.
这个结果否定了费马的一个猜想：若 $n$ 为自然数，则 $2^{2^*}+1$ 都是素数．

`例` 求 $23^{23}$ 的末位数字．
解 ： $23^{23} \equiv 3^{23} \equiv\left(3^2\right)^{11} \cdot 3 \equiv(10-1)^{11} \cdot 3 \equiv-1 \cdot 3 \equiv 7(\bmod 10)$ ．因此 $23^{23}$ 的末位数字是 7 ．

其他版本
【高等代数】同余式与剩余类

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：算术基本定理

下一篇：剩余类及其运算

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