同余是什么

同余，就是把整数放进一个“循环世界”里看。

在普通整数世界里，$3$ 和 $15$ 当然不是同一个数。 但如果我们看的是 $12$ 小时制的时钟，它们就落在同一个位置。

因为：

也就是说，$15$ 除以 $12$ 的余数是 $3$。

而 $3$ 除以 $12$ 的余数也是 $3$。

所以，在“模 $12$”的世界里，我们可以说：

这就是同余。

它不是在说两个数真的相等。

它是在说：如果只看除以某个数后的余数，它们是一样的。

这件事看起来很小，但它非常有用。

大数余数计算、整除性判断、循环问题、密码学里的模运算，背后都离不开同余。

从时钟说起

很多人第一次学同余，会觉得符号有点抽象。其实我们不必先急着看符号，先看时钟就够了。

在 $12$ 小时制里：

为什么？

因为时钟每 $12$ 个小时转一圈。

转完一圈之后，位置又回来了。

所以我们关心的不是这个数本身有多大，而是它除以 $12$ 后落在哪个位置。

比如：

于是：

这些数在模 $12$ 的意义下，都属于同一类。

这就是同余最直观的画面。

同余的定义

现在我们把上面时钟的直觉写成数学语言。

这一定义有两种理解方式。

第一种是直觉版：

$a$ 和 $b$ 除以 $m$ 后余数相同。

第二种是证明版：

$a-b$ 能被 $m$ 整除。

做题时，这两种说法都要会用。

比如：

因为：

而 $12$ 能被 $6$ 整除。

再比如：

因为：

而 $-12$ 能被 $4$ 整除。

处理负数时，用“差能被整除”通常更舒服。

不用纠结负数除法到底余几。

还有一个常用说法：

如果 $a$ 除以 $m$ 的余数是 $r$，并且

那么：

这个 $r$ 叫做 $a$ 关于模 $m$ 的最小非负余数。

你可以把它理解成：$a$ 在模 $m$ 世界里的“标准编号”。

同余到底在分什么类

同余的真正的厉害之处，不只是写一个符号。它其实是在把所有整数分组。

比如模 $4$。

任意整数除以 $4$，余数只可能是：

所以全体整数会被分成四类：

每一类里的数，模 $4$ 意义下都一样。这就是剩余类。

更一般地来说，模 $m$ 时，一共有 $m$ 个剩余类：

它们互不重叠，又合起来覆盖所有整数。 所以同余不是“算余数的小技巧”。

更准确地说，它是在告诉我们：

整数可以按余数被重新组织。

同余为什么像等号

同余符号长得像等号，不是随便设计的。

它确实有很多类似等号的性质。

第一，自反性：

因为：

而任何正整数都整除 $0$。

第二，对称性：

如果：

那么：

因为 $a-b$ 能被 $m$ 整除，那么 $b-a=-(a-b)$ 也能被 $m$ 整除。

第三，传递性：

如果：

并且：

那么：

直觉上也很好理解。

$a$ 和 $b$ 余数一样，$b$ 和 $c$ 余数一样，那 $a$ 和 $c$ 的余数当然也一样。

这三条性质说明，同余是一种等价关系。

它允许我们把一堆不同的整数，看成模 $m$ 世界里的同一种对象。

同余的运算规则

同余最方便的地方在这里：

它和加法、减法、乘法都很合得来。

这意味着什么？

意味着我们可以在计算中不断把大数换成小余数。

比如计算：

不用真的先算乘积。

因为：

所以：

答案就是 $5$。

这就是同余的核心价值：

它让大数计算变成小数计算。

如果 $c$ 和 $m$ 互质，也就是：

那么从

可以推出：

这点很重要。

很多同余题做错，错就错在把除法当成普通等式里的除法。

完全剩余系

我们已经知道，模 $m$ 会把整数分成 $m$ 类。

如果你从每一类里各选一个代表，就得到一个完全剩余系。

最常见的选法是：

这叫最小非负完全剩余系。

比如模 $5$ 时，最常用的一组代表就是：

但代表不是唯一的。

模 $5$ 时，下面这组也可以：

因为它们也刚好分别代表五个不同的余数类。

甚至：

也可以作为模 $5$ 的一组代表。

重点不是数字长什么样。

重点是：每个剩余类刚好出现一次。

这个事实后面证明欧拉定理时很关键。

现在先有个印象就可以。

线性同余方程

同余里最常见的一类方程是：

这叫线性同余方程。

它的问题是：要找哪些整数 $x$，让 $ax$ 除以 $m$ 后和 $b$ 余数相同。

有一个非常重要的判定：

有解，当且仅当：

也就是说，$a$ 和 $m$ 的最大公因数，必须整除右边的 $b$。

比如：

这里：

但：

所以这个方程无解。

直觉上也很明显。

$4x$ 永远是偶数。

要让 $4x-3$ 被 $6$ 整除，几乎不可能，因为 $4x-3$ 永远是奇数。

最常用的是互质情形。

如果：

那么方程：

在模 $m$ 意义下有唯一解。

这时我们可以找 $a$ 关于模 $m$ 的乘法逆元。

也就是找一个数 $a^{-1}$，满足：

然后两边乘以这个逆元，就能解出 $x$。

例题精讲

例题一：判断同余是否成立

题目：判断以下是否成立，并说明理由：

（1）$37 \equiv 13 \pmod 8$

（2）$-15 \equiv 9 \pmod 6$

（3）$100 \equiv 1 \pmod 9$

例题二：计算大数幂的余数

题目：计算 $3^{100}\bmod 7$。

例题三：用同余证明整除性

题目：证明对所有非负整数 $n$，有

例题四：解线性同余方程

题目：解方程

例题五：用同余解释整除判别

题目：不做大数除法，判断 $123456789$ 能否被 $9$ 整除。

例题六：无解的线性同余方程

题目：证明方程

无解。

同余为什么重要

同余不是只为了算几道余数题。

它真正重要的地方在于：它让我们可以在一个有限的循环系统里处理整数。

大数可以先取余。

复杂幂次可以找周期。

整除性可以改写成同余。

方程可以在模 $m$ 的世界里求解。

现代密码学里大量使用的 RSA，也离不开模运算和同余。

当然，RSA 还需要欧拉函数、欧拉定理、大素数分解等内容。

但同余就是那扇门。

你理解了同余，后面很多数论内容都会突然变得顺眼很多。

练习

练习一：求 $7^{200}\bmod 11$。

练习二：解方程 $7x\equiv 2\pmod{10}$，并找出 $-20$ 到 $20$ 范围内的所有解。

练习三：证明对所有正整数 $n$，有

要点收束

这章的主题可以浓缩成一句话：

同余是在用“余数相同”重新理解整数。

它的定义是：

它的直觉是：

它的好处是：

• 大数可以化小
• 幂次可以找周期
• 整除性可以变成余数问题
• 线性方程可以在模世界里求解

需要特别注意的是除法。

同余里加、减、乘都很自然，但除法必须看能不能约。

只有当要约掉的数和模互质时，才能像普通等式那样放心约。

如果用知乎式的一句话来收尾：

同余不是“余数的小技巧”，而是把无限整数压缩进有限循环结构的一种语言。

后面学欧拉定理、中国剩余定理、RSA 时，你会不断看到这句话的影子。

那么就说 $a$ 和 $b$ 关于模 $m$ 同余，记作：

如果 $m$ 不能整除 $a-b$，就记作：

并且对正整数 $n$，还有：

因为两边都是 $0 \pmod 6$。

但：

所以同余里可以放心加、减、乘。

但想“约掉”一个数时，要先看这个数和模是否互质。

成立。

因为：

所以：

有解的条件是：

所以：

而：

所以：

答案是 $1$。

所以：

两边乘以 $3$：

所以：

在 $-20$ 到 $20$ 范围内，解是：

所以：

因为：

所以：

于是：

也就是：