同余的概念与基本性质

在只有 m 个刻度的钟面上，相差 m 的倍数的数落在同一格——它们同余，做加减乘时可以互相替换。

📖 配合《整除、同余与不定方程》§2.1阅读M14 选择合适的模线

观察

$n$ 每加 $1$ ，指针走一格。连加 $7$ 次，指针回到原处——数表里它往下挪了一行，还在同一列。
在同一列里随便挑两个数相减。差总是谁的倍数？
把 $n$ 拖到 $- 3$ 。它落在哪一列？和你心里想的余数一样吗？
切到“加法”。反复按 $a + 7$ 、 $a - 7$ 、 $b + 7$ ：三个读数里，哪一个纹丝不动？
切到“乘法”，再做一遍第 4 条。

定义设 $m$ 是正整数。如果 $m ∣ (a - b)$ ，就说 $a$ 与 $b$ 模 $m$ 同余，记作 $a \equiv b (mod m)$ 。

同余就是“被 $m$ 除余数相同”，也就是“落在数表的同一列”。每一列叫一个剩余类，模 $m$ 一共有 $m$ 个。

先猜后证

今天是星期三。再过 $100$ 天是星期几？

星期三星期四星期五星期六

先选定答案，才能看到结论。

为什么

第 4、5 条观察说的是：做加法、乘法之前，可以先把每个数换成同一列里别的数。为什么换了没事？

同余的数可以互相替换

第 1 / 5 步

先算一次
模 $7$ 。 $9 + 5 = 14$ ，落在“余 $0$ ”那一列。

$9 + 5 = 14 \equiv 0 (mod 7)$
把 a 换成同列的数
换成乘法
再换一次 a
所以挑最小的来算

乘法可以换，乘方（连乘）也就可以换： $a \equiv b$ 则 $a^{n} \equiv b^{n}$ 。于是大得写不下来的数，余数也能算。

例求 $2^{100}$ 被 $7$ 除的余数。 $2^{3} = 8 \equiv 1 (mod 7)$ ，而 $100 = 3 \times 33 + 1$ ，所以

2^{100} = (2^{3})^{33} \times 2 \equiv 1^{33} \times 2 = 2 (mod 7) .

如果去掉一个条件

加、减、乘都可以放心做。除法（约分）不行，除非多一个条件。

Break it

反例实验室：去掉一个条件

结论： $c a \equiv c b (mod m)$ 时可以约去 $c$ ，得到 $a \equiv b (mod m)$

模 $7$ ，乘以 $3$ 。每个 $x$ 一支箭头，指向 $3 x$ 的余数。七支箭头落在七个不同的位置： $3 a$ 和 $3 b$ 落在同一处，只可能是 $a$ 、 $b$ 本来就在同一处。所以可以约。

练一练

练习 1基础

求 $2024$ 被 $9$ 除的余数。

练习 2基础

求 $37 \times 58 + 46$ 被 $7$ 除的余数。

练习 3提高

求 $3^{100}$ 被 $13$ 除的余数。

练习 4挑战

证明：对任意正整数 $n$ ， $3^{2 n + 1} + 2^{n + 2}$ 能被 $7$ 整除。

错误博物馆 · 本站展品

离站之前，看看别人在这里踩过的坑。去博物馆看全部展品 →

展品

同余式两边随手约分

4 \times 6 \equiv 4 \times 1 (mod 10)

，两边约去

4

，得

6 \equiv 1 (mod 10)

。

错在哪里？先想一想，再打开

病因　 $24 \equiv 4 (mod 10)$ 没错，但 $6 - 1 = 5$ 不是 $10$ 的倍数。 $4$ 和 $10$ 有公因数 $2$ ： $10 ∣ 4 \times 5$ 时， $10$ 的一部分是被 $4$ “吃掉”的。

约去

c

时，模要同时除以

(c, m)

：由

4 \times 6 \equiv 4 \times 1 (mod 10)

只能得到

6 \equiv 1 (mod 5)

。只有

(c, m) = 1

时才能原样约掉。

「加减乘随便做，约分先看互素」

展品

负数的余数写成负的

- 3

除以

7

，余数是

- 3

（或者是

3

）。

错在哪里？先想一想，再打开

病因　余数规定在 $0$ 到 $m - 1$ 之间。 $- 3$ 往回走 $3$ 格，从 $0$ 倒退到刻度 $4$ ；而 $3$ 和 $- 3$ 相差 $6$ ，不是 $7$ 的倍数，根本不在同一列。

- 3 = (- 1) \times 7 + 4

，余数是

4

，即

- 3 \equiv 4 (mod 7)

。

「负数就倒着绕钟面」

展品

把指数也按模 m 取余

10 \equiv 3 (mod 7)

，所以

2^{10} \equiv 2^{3} (mod 7)

。

错在哪里？先想一想，再打开

病因　同余的数可以在底数的位置上互换，指数不是“被加、被乘的数”，没有这条规则。实际上 $2^{10} = 1024 \equiv 2$ ，而 $2^{3} = 8 \equiv 1$ 。

先找幂的周期：

2^{3} \equiv 1 (mod 7)

，所以指数应当按

3

取余。

10 = 3 \times 3 + 1

，

2^{10} \equiv 2^{1} = 2

。

「底数按 m 约，指数按周期约」