初中数学竞赛 · 整除、同余与不定方程

同余的概念与基本性质

同余是把“除以 m 的余数”变成一套可以运算的语言。学会它，末尾数字、整除证明、大指数求余这一类题就从“找规律”变成了“做算术”。

八~九年级难度 ★★★16 分钟

从“余数相同”开始

整数除以 $7$ ，余数只有七种可能： $0, 1, 2, 3, 4, 5, 6$ 。所有整数因此被分成七堆，同一堆里的数除以 $7$ 余数相同。

既然同一堆里的数在“除以 $7$ ”这件事上没有区别，那就可以给“在同一堆”起个名字，直接拿来运算。这个名字就是同余。

定义

设 $m$ 是正整数。若整数 $a, b$ 除以 $m$ 的余数相同，就说 $a$ 与 $b$ 模 $m$ 同余，记作

a \equiv b (\mod m)

等价的说法： $m$ 能整除 $a - b$ ，即 $m ∣ (a - b)$ 。

三种说法是一回事，做题时按方便挑：验算用“余数相同”，证明用“ $m ∣ a - b$ ”，变形用“ $a = b + k m$ ”。

举几个例子：

17 \equiv 3 (\mod 7), - 1 \equiv 6 (\mod 7), 100 \equiv 0 (\mod 4)

第二条值得停一下。 $- 1$ 除以 $7$ 余 $6$ ，所以 $- 1 \equiv 6$ 。它说明同余里的数可以是负的，而 $- 1$ 这个写法在后面的计算里极其好用，因为它让“接近整倍数”的数变得很短： $99 \equiv - 1 (\mod 100)$ 。

为什么它能当运算用

同余最值钱的地方，是它和加、减、乘、乘方全都相容。这不是规定，是可以证明的。

设 $a \equiv b (\mod m)$ ， $c \equiv d (\mod m)$ ，那么存在整数 $k_{1}, k_{2}$ 使 $a = b + k_{1} m$ ， $c = d + k_{2} m$ 。

加法： $a + c = (b + d) + (k_{1} + k_{2}) m$ ，所以 $a + c \equiv b + d (\mod m)$ 。

减法： $a - c = (b - d) + (k_{1} - k_{2}) m$ ，同理。

乘法：

a c = (b + k_{1} m) (d + k_{2} m) = b d + (b k_{2} + d k_{1} + k_{1} k_{2} m) m

后面那一坨是 $m$ 的整数倍，所以 $a c \equiv b d (\mod m)$ 。

乘方：把乘法用 $n$ 次，得 $a^{n} \equiv b^{n} (\mod m)$ 。

这条链子的意义

只要两个数同余，就可以在任何只含加减乘和乘方的式子里互相替换，替换之后同余关系保持。于是“求 $2^{100}$ 除以 $7$ 的余数”这种看似无从下手的问题，被拆成了“在模 $7$ 的世界里做乘法”。

除法要小心

加法、减法、乘法都能随便用，除法不行。

在普通算术里 $6 = 6$ ，两边同时除以 $2$ 还是相等。但在同余里， $6 \equiv 0 (\mod 6)$ ，两边除以 $2$ 得 $3 \equiv 0 (\mod 6)$ ，这就不对了。

原因在于同余的信息是“模 $m$ 之后”的，除以一个数和 $m$ 有公因数时，会把模也跟着改变。

正确的处理办法是乘逆元，不是除。若 $gcd (c, m) = 1$ ，存在整数 $c^{- 1}$ 使 $c \cdot c^{- 1} \equiv 1 (\mod m)$ ，此时才能在两边乘 $c^{- 1}$ 来“约掉” $c$ 。

例：解 $3 x \equiv 5 (\mod 7)$ 。因为 $3 \times 5 = 15 \equiv 1 (\mod 7)$ ，所以 $3$ 的逆元是 $5$ 。两边乘 $5$ ： $x \equiv 25 \equiv 4 (\mod 7)$ 。验证： $3 \times 4 = 12 \equiv 5$ ，成立。

例题

例1 大指数求余：先找循环

求 $2^{100}$ 除以 $7$ 的余数。

思路：直接算 $2^{100}$ 是不可能的。但在模 $7$ 下， $2$ 的幂只有 $7$ 种可能，一定会循环。先算几项看周期。

解： $2^{1} \equiv 2, 2^{2} \equiv 4, 2^{3} \equiv 8 \equiv 1 (\mod 7)$

出现 $1$ 就意味着循环开始： $2^{3} \equiv 1$ ，所以 $2^{3 k} \equiv 1$ 。
$100 = 3 \times 33 + 1 ⟹ 2^{100} = (2^{3})^{33} \cdot 2 \equiv 1^{33} \cdot 2 \equiv 2 (\mod 7)$
余数是 $2$ 。

关键动作：找到 $2^{k} \equiv 1$ 的那个 $k$ 。找到了，指数再大也只是做一次带余除法。

例2 连续整数乘积

求证：对任意整数 $n$ ， $n^{3} - n$ 能被 $6$ 整除。

思路一（因式分解）： $n^{3} - n = n (n - 1) (n + 1)$ ，是连续三个整数之积。三个连续整数里必有一个是 $3$ 的倍数，也必有一个是偶数（其实是 $2$ 的倍数，三个里至少一个还是 $2$ 的倍数），所以乘积被 $2 \times 3 = 6$ 整除。

思路二（同余）：把 $n$ 按模 $6$ 分成六类，逐一验证太笨。分两步更省：模 $2$ 和模 $3$ 分别验证。

模 $2$ ： $n \equiv 0$ 时 $n^{3} - n \equiv 0$ ； $n \equiv 1$ 时 $1 - 1 = 0$ 。模 $3$ ： $n \equiv 0, 1, 2$ 分别代入， $0, 0, 8 - 2 = 6 \equiv 0$ 。

两步都成立，说明 $n^{3} - n$ 同时被 $2$ 和 $3$ 整除，故被 $6$ 整除。

两种思路的差别：第一种靠结构（连续整数），第二种靠分类（模 $2$ 、模 $3$ ）。分类法虽然笨一点，但它是通用套路——模 $m$ 的问题拆成模 $m$ 的各个素因子幂，几乎总能奏效。

例3 末位数字

求 $3^{2026}$ 的个位数字。

思路：个位数字就是模 $10$ 的余数。

解： $3^{1} \equiv 3, 3^{2} \equiv 9, 3^{3} \equiv 27 \equiv 7, 3^{4} \equiv 81 \equiv 1 (\mod 10)$

周期是 $4$ 。 $2026 = 4 \times 506 + 2$ ，所以 $3^{2026} \equiv (3^{4})^{506} \cdot 3^{2} \equiv 1 \cdot 9 \equiv 9 (\mod 10)$

个位数字是 $9$ 。

这一类题的通用模板：算前几项 → 找到 $1$ → 指数带余除法 → 回到对应的那一项。个位、末两位、除以某个小质数的余数，全是同一个套路，只换了模。

例4 先找 1 的幂

求证： $7^{2026} - 7^{2024}$ 能被 $48$ 整除。

思路：题目给了模数 $48$ ，先看它和底数 $7$ 有什么关系： $7^{2} = 49 = 48 + 1$ ，也就是 $7^{2}$ 除以 $48$ 余 $1$ 。一旦某个幂同余于 $1$ ，高次幂就全部塌缩成 $1$ ，题目立刻变简单。

解： $7^{2} = 49 \equiv 1 (\mod 48)$ ，所以 $7^{2 k} \equiv 1 (\mod 48)$ 。

$2026 = 2 \times 1013$ ， $2024 = 2 \times 1012$ ，指数都是偶数，于是 $7^{2026} \equiv 1, 7^{2024} \equiv 1 (\mod 48)$

相减得 $7^{2026} - 7^{2024} \equiv 0 (\mod 48)$ ，即被 $48$ 整除。

顺便说一句：这道题也能用提公因式做。 $7^{2026} - 7^{2024} = 7^{2024} (49 - 1) = 48 \times 7^{2024}$ 。两条路都对，同余这条路更适合模数不规整的场合。做题时两条路都想到，才算真懂。

例5 同余方程

求满足 $3 x \equiv 5 (\mod 7)$ 的所有整数 $x$ 。

解： $3$ 在模 $7$ 下的逆元是 $5$ （因为 $3 \times 5 = 15 \equiv 1$ ）。两边乘 $5$ ： $x \equiv 25 \equiv 4 (\mod 7)$

所以 $x = 7 k + 4$ （ $k$ 为任意整数）。

验证： $x = 4$ 时 $3 x = 12 \equiv 5$ ； $x = 11$ 时 $33 \equiv 5$ 。都对。

提醒：这里之所以能乘，是因为 $gcd (3, 7) = 1$ 。若方程是 $6 x \equiv 3 (\mod 9)$ ，两边不能除以 $3$ ，得先把式子化成 $2 x \equiv 1 (\mod 3)$ 再处理——模也跟着变了。

三个坑

负数余数直接写负数： $n \equiv - 1 (\mod 7)$ 是对的，但答案是“余数”时要写成 $6$ 。同余关系里可以用负号，答题时要还原。
随便约分：同余式两边除以一个与模不互素的数，结论会错。要先确认 $gcd (c, m) = 1$ 。
模数混用：同一个式子里所有项必须对同一个 $m$ 取模。中途换模数必须单独说明并重新论证。

练习（先做，再看答案）

求 $2^{2026}$ 除以 $7$ 的余数。
求 $7^{2026}$ 的个位数字。
求证：对任意整数 $n$ ， $n^{5} - n$ 能被 $30$ 整除。
解同余方程 $5 x \equiv 3 (\mod 11)$ 。
求证： $3^{2026} + 3^{2024}$ 能被 $10$ 整除。

看答案

1. $2^{3} \equiv 1 (\mod 7)$ ， $2026 = 3 \times 675 + 1$ ，故 $2^{2026} \equiv 2 (\mod 7)$ ，余数 $2$ 。

2. $7^{1} \equiv 7, 7^{2} \equiv 9, 7^{3} \equiv 3, 7^{4} \equiv 1 (\mod 10)$ ，周期 $4$ 。 $2026 = 4 \times 506 + 2$ ，故余 $7^{2} \equiv 9$ ，个位是 $9$ 。

3. $n^{5} - n = n (n^{4} - 1) = n (n - 1) (n + 1) (n^{2} + 1)$ 。模 $2$ 、模 $3$ 、模 $5$ 分别验证：模 $2$ 时 $n^{5} \equiv n$ ；模 $3$ 时由费马小定理 $n^{3} \equiv n$ 可推 $n^{5} \equiv n$ ；模 $5$ 时同样 $n^{5} \equiv n$ 。故被 $2 \times 3 \times 5 = 30$ 整除。

4. $5 \times 9 = 45 \equiv 1 (\mod 11)$ ，逆元是 $9$ 。 $x \equiv 3 \times 9 = 27 \equiv 5 (\mod 11)$ ，即 $x = 11 k + 5$ 。

5. $3^{2026} + 3^{2024} = 3^{2024} (9 + 1) = 10 \times 3^{2024}$ ，故被 $10$ 整除。

一页速记

$a \equiv b (\mod m)$ 三说法：余数相同 / $m ∣ a - b$ / $a = b + k m$
加减乘、乘方全能替换；除法不行，要乘逆元（要求 $gcd (c, m) = 1$ ）
大指数求余：先找 $2^{k} \equiv 1$ 或 $a^{k} \equiv 1$ ，再对指数做带余除法
末位数字 = 模 $10$ ；末两位 = 模 $100$
证明整除：能分解就分解，不能分解就分模（拆成素因子幂分别验证）
见 $m^{2} - 1$ 、 $m^{2} + 1$ 这类数，先想 $\pm 1$ 的幂

看完了？ 去整除、同余与不定方程做配套练习，或回到竞赛总览挑下一个专题。想动手刷题、看看这些方法在题目里怎么用，去奥数挑战。