同余

我们先留在 17 个圆片、每包 5 个的例子里。下面每个蓝色实线框装了 5 个圆片，金色虚线框里只有剩下的 2 个；它还不是一个完整的 5 个一包。

5 告诉我们一整组有多大，在除法里它叫除数。3 或 4 数的是完整的组数，叫商。最后留下的 2 叫余数。余数必须不小于 0，而且小于每组大小。如果还剩至少 5 个，我们就还能装满一包，也就是说分组还没有完成。

为了让一句话同时描述不同的总数，我们用字母。$a$ 是一个整数，也就是 …，$-3$，$-2$，$-1$，0，1，2，3，… 这些没有小数或分数部分的数。$a \in \mathbb Z$ 的意思就是“$a$ 是整数”。$m$ 是固定的正整数分组大小，这里至少是 2。$q$ 是整数商，$r$ 是余数：

$qm$ 中两个字母挨着写表示相乘，也就是 $q \times m$。负数不能直接当作实际圆片的包数，不过数轴让同一个等式继续成立：从一个不超过 $a$ 的倍数 $qm$ 出发，向右走 $r$ 个单位，就到达 $a$。例如 $-1 = (-1) \times 5 + 4$，表示从 $-5$ 向右走 4 个单位到 $-1$。商是 $-1$，可余数是 4，并不是 $-1$。

图片替几个整数找到了余数。不过要在这个基础上建立规则，我们还需要两件事：每个整数都能这样写，而且不能同时有两个不同的正确余数。我们分开证明。

先证明每个整数都写得出来

如果 $a$ 不小于 0，我们从 $a$ 开始，只要剩下的数至少是 $m$，就减去一个 $m$。每次减法拿走一整组。剩下的数每次至少减少 1，而且不会变成负数，所以一定会停下：从 0 到 $a$ 总共只有 $a + 1$ 个非负整数。如果一共减了 $q$ 次，最后的数叫 $r$，那么 $a = qm + r$，而且 $0 \le r < m$。

如果 $a$ 是负数，我们写 $a = -n$，其中 $n$ 是正数。对 $n$ 使用刚才的分组方法，得到 $n = qm + r$。如果 $r = 0$，等式两边变号就得到 $a = (-q)m + 0$。如果 $r > 0$，变号后的式子是 $-qm - r$，但这里的 $-r$ 是负数。为了得到非负余数，我们从完整倍数中减去一个 $m$，并把同样的 $m$ 补到余数部分：

右边展开是 $-qm - m + m - r = -qm - r$，所以数值没有改变。又因为 $0 < r < m$，$m$ 减去 $r$ 后满足 $0 < m - r < m$，新余数符合要求。这两种情况包括所有负整数，因此存在性已经证明。

再排除两个不同的答案

假设有人给出了两种写法 $a = qm + r$、$a = sm + t$，其中 $r$、$t$ 都在 0 到 $m - 1$ 之间。用第一种写法减去第二种，因为描述的是同一个 $a$，左边就抵消了：

$r$、$t$ 都在这个范围里，所以 $t - r$ 严格处在 $-m$ 与 $m$ 之间。可是一个整数倍的 $m$，要么是 0，要么大小至少是 $m$，因为非零整数的大小至少是 1。因此这里的倍数只能是 0。于是 $q - s = 0$，也就是 $q = s$；接着 $t - r = 0$，也就是 $t = r$。商和符合范围要求的余数都只有一个。

回到 17 和 22。它们的差是 $22 - 17 = 5$，正好是一整包。添加或拿走完整的包会改变总数，却不改变余数。我们需要一个记号来描述这种准确的相同：$a \equiv b \pmod{m}$，读作“$a$ 与 $b$ 模 $m$ 同余”，意思是它们除以 $m$ 的余数相同。固定的 $m$ 叫模数。

余数相同的所有整数合在一起，叫一个余数类。我们可以拿其中任何一个数来代表这一整类，这个数就叫代表元。例如模 5 时，2 所在的类包含 …，$-8$，$-3$，2，7，12，17，22，…，因为每一个都等于 5 乘以某个整数再加 2。用 2 作代表，并不意味着这一类只有整数 2。

这里的 $\equiv$ 不表示两个整数相等，也不表示大约相等。它准确地说的是：在指定模数下，余数相同。推理时不能忘掉模数：17 和 22 模 5 同余，可是除以 3 时，它们的余数分别是 2 和 1。

还有一种说法更方便计算。记号 $m \mid n$ 表示“$m$ 整除 $n$”，也就是 $n$ 等于 $m$ 乘以某个整数；中间的竖线不是除号。我们现在从两个方向证明：余数相同，恰好等价于两数的差是 $m$ 的倍数。

先假设余数相同。写成 $a = qm + r$、$b = sm + r$。相减得到 $a - b = qm + r - sm - r = m(q - s)$。$q - s$ 仍是整数，所以这个差是 $m$ 的整数倍。

反过来，假设 $a - b = mk$，其中 $k$ 是整数。先不假设余数相同，分别写 $a = qm + r$、$b = sm + t$。代入，再把已经是 $m$ 的倍数的部分移到另一边：

$r - t$ 又严格处在 $-m$ 与 $m$ 之间，同时它又是 $m$ 的倍数。刚才唯一性证明里的理由迫使它只能为 0，所以 $r = t$。两个方向都证明了。双向箭头的意思就是：任意一边成立，都能推出另一边成立。

接下来会用到的三个小动作，也能直接解释。每个数与自己同余，因为 $a - a = m \times 0$。同余两边可以交换，因为 $a - b = mk$ 就意味着 $b - a = m(-k)$。同一个模数下还可以把两段关系接起来：如果 $a - b = mk$、$b - c = mh$，相加得到 $a - c = m(k + h)$。所以 $a$ 与 $b$ 同余、$b$ 与 $c$ 同余，就能推出 $a$ 与 $c$ 同余；模数始终必须相同。

如果我们只知道余数，还能加或乘吗？设 $a \equiv b \pmod{m}$、$c \equiv d \pmod{m}$。刚才证明的差的说法让我们可以写 $a = b + mk$、$c = d + mh$，其中 $k$、$h$ 是整数。这两个等式准确地告诉我们省略了什么：若干个完整的 $m$。

加法与减法

$k + h$ 和 $k - h$ 都是整数，因此两行算出的差都是 $m$ 的倍数。根据已经证明的描述，$a + c \equiv b + d \pmod{m}$，$a - c \equiv b - d \pmod{m}$。特别地，两边加上同一个整数是允许的，因为这个整数总与自己同余。

乘法

乘法里，我们必须把每一项都算进去，包括两个被省略的倍数之间的乘积。展开括号后，所有含 $m$ 的项都可以合成一个 $m$ 的倍数：

括号里只有整数的和与积，所以它还是整数。因此 $ac \equiv bd \pmod{m}$。这就是为什么我们能先把因数换成余数。例如模 5 下，$17 = 3 \times 5 + 2$，所以 $17 \equiv 2$；$22 = 4 \times 5 + 2$，所以 $22 \equiv 2$。于是 $17 \times 22 \equiv 2 \times 2 = 4 \pmod{5}$。算完整乘积检查，$374 = 74 \times 5 + 4$。更小的计算准确保留了我们要的余数。

正整数次幂

$a^{n}$ 中的 $n$ 是正整数时，意思是把 $n$ 个 $a$ 乘起来。如果 $a$ 与 $b$ 同余，乘法规则先给出 $a^{2}$ 与 $b^{2}$ 同余。再把 $a^{2} \equiv b^{2}$ 和 $a \equiv b$ 相乘，就得到 $a^{3} \equiv b^{3}$。为什么这不只是两个例子，而能包括每个正整数 $n$？起点 $n = 1$ 就是已知的同余。只要 $n$ 这一步成立，把它再与 $a \equiv b$ 相乘，就证明 $n + 1$ 这一步成立。从 1 开始不断这样前进，就能到达任意正整数 $n$。这种“起点成立，而且每一步能推到下一步”的证明叫归纳证明。

看 $2x \equiv 2 \pmod{6}$。普通等式 $2x = 2$ 只有 $x = 1$。可现在的要求不同：我们要的是 $2x - 2$ 为 6 的倍数。$x = 1$ 和 $x = 4$ 都成立，因为 $2 \times 1 - 2 = 0 = 6 \times 0$，而 $2 \times 4 - 2 = 6 = 6 \times 1$。可是 1 和 4 并不模 6 同余，因为 $4 - 1 = 3$ 不是 6 的倍数。

初始表格里，起始余数 1 和 4 乘以 2 后，模 6 都变成 2。两个起点合在一起之后，仅凭结果就无法分辨我们来自哪个起点。没有理由的约分，丢掉的正是这部分信息。

真正的等式仍然可以做除法。我们把条件写成 $2x - 2 = 6k$，其中 $k$ 是整数。这个等式的每一项都除以 2，得到 $x - 1 = 3k$。它说的是 $x \equiv 1 \pmod{3}$，模数已经变成 3。把步骤倒过来，任何这样写出的 $x$ 都成立。因此全部整数解是 $x = 1 + 3k$，也就是 …，$-5$，$-2$，1，4，7，10，…。消去因数时，模数也跟着改变了。

什么时候能保留原来的模数？不能保留时，到底应该怎么改？要完整回答，我们需要一个工具：用整数倍组合出 1，或者组合出更大的公因数。接下来我们把这个工具证明出来，而不是直接假设它存在。

取正整数 $A$、$M$。一个正整数如果同时整除它们，就是正公因数。至少总有 1，而且这样的数只有有限个：若 $A = gh$，$g$、$h$ 都是正整数，那么 $h \ge 1$，所以 $g \le A$。因此每个正因数都在 1，2，…，$A$ 这个有限列表里。其中最大的叫最大公因数，记作 $\gcd (A, M)$。我们不仅要找到它，还要证明它能写成整数倍的组合 $uA + vM$。

换一对数，同时保留全部公因数

把 $A$ 除以 $M$，写 $A = qM + r$。如果正整数 $g$ 同时整除 $A$、$M$，就能写 $A = gu$、$M = gv$。那么 $r = A - qM = gu - qgv = g(u - qv)$，所以 $g$ 也整除 $r$。反过来，如果 $M = gv$、$r = gw$，那么 $A = qM + r = qgv + gw = g(qv + w)$，所以 $g$ 也整除 $A$。因此 $(A, M)$ 与 $(M, r)$ 这两对数拥有完全相同的正公因数。

只要余数不为 0，就继续这样替换。每个新余数都是非负整数，而且比前一个除数小，所以正余数不可能永远下降。最终会到达 $(d, 0)$。$d$ 的每个正因数也都整除 0，因为 0 等于这个因数乘以 0；所以最后一对数的最大公因数就是 $d$ 本身。每次替换都保留了全部公因数，因此 $d$ 也是最初 $A$、$M$ 的最大公因数。这个过程叫辗转相除法，也叫欧几里得算法。

把每个余数是怎么来的也留下

最开始，$A = 1A + 0M$、$M = 0A + 1M$ 已经是 $A$、$M$ 的整数倍组合。假设当前两个数写成 $uA + vM$、$sA + tM$。用第一个数减去第二个数的 $q$ 倍，就得到 $(u - qs)A + (v - qt)M$，系数仍然是整数。因此每个新余数也是这样的组合。起点成立，每一步都保留这个性质，所以最后留下的非零数 $d$ 也一定能这样写，即使它本来就是起始数之一：

这个等式叫贝祖等式。$u$、$v$ 可以是负数；“整数倍组合”既允许加，也允许减。我们已经证明了这些系数一定存在，并不是假设我们总能猜到它们。

把数算完整：用 7 和 12 组合出 1

对于 7 和 12，先用较大的数除以较小的数。随后每一行都取上一行的除数和余数：

最后一个非零余数是 1，所以 $\gcd (7, 12) = 1$。怎样用最初的 7 和 12 写出这个 1？等式 $1 = 5 - 2 \times 2$ 告诉我们它来自哪里。其中的 2 可以换成 $7 - 5$，剩下的 5 可以换成 $12 - 7$，这样式子里就只留下 7 和 12。中间的展开也全部保留：

检查一下，$36 - 35 = 1$。这里没有除以 7；我们找到的是 7 的一个整数乘数 $-5$，使乘积与 1 相差一个 12 的倍数。这正是我们在寻找的、能够代替除法的办法。

先处理乘数 $c$ 与模数 $m$ 的最大公因数为 1 的情况。这样的两个正整数叫互质，意思只是它们唯一的正公因数是 1。贝祖等式给出整数 $u$、$v$，使 $uc + vm = 1$。假设 $cA \equiv cB \pmod{m}$，也就是 $c(A - B) = mk$。现在把贝祖等式乘以 $A - B$：

括号里是整数，所以 $m$ 整除 $A - B$，也就是 $A \equiv B \pmod{m}$。我们选贝祖等式，是为了让一边变成 $A - B$，另一边又能用上已经知道是 $m$ 的倍数的 $c(A - B)$。这样就证明了：乘数与模数互质时，可以保留模数消去乘数。

有公因数时，到底改变什么？

设 $d = \gcd (c, m)$，这里 $c$ 是正整数。把两者都除以 $d$，记 $c' = c/d$、$m' = m/d$，它们仍然是整数。它们互质：如果正整数 $h$ 同时整除 $c'$、$m'$，那么 $dh$ 就同时整除 $c$、$m$；由于 $d$ 已是最大公因数，$dh \le d$，两边除以正数 $d$ 得到 $h \le 1$。因此 $h$ 只能是 1。

先证明向右的方向。写 $c(A - B) = mk$，把这个等式除以 $d$，得到 $c'(A - B) = m'k$。$c'$、$m'$ 互质，刚才的证明就给出 $m'$ 整除 $A - B$。反过来，如果 $A - B = m'j$，其中 $j$ 是整数，乘以 $c = dc'$ 后得到 $c(A - B) = dc'm'j = mc'j$，它是 $m$ 的倍数，因此原同余成立。两个方向都成立。

还有一个边界情况需要说清楚。如果 $m/d = 1$，那么除以 1 的余数总是 0，因为每个整数 $n$ 都有 $n = n \times 1 + 0$。因此所有整数模 1 都同余，化简后的条件没有施加任何限制。刚才的证明仍然成立，因为 1 整除所有整数。起初我们用 $m \ge 2$，但消去之后可能出现这个情况。

用另一次乘法撤销乘法

普通算术里，乘以 $1/c$ 能撤销乘以 $c$。在这里，我们要找的是整数 $u$，使 $cu \equiv 1 \pmod{m}$。这样的 $u$ 叫 $c$ 模 $m$ 的乘法逆元。它是在余数关系里起逆作用的整数，并不是普通分数 $1/c$。如果 $cx \equiv b$，两边乘以 $u$ 得到 $ucx \equiv ub$；再用 $uc \equiv 1$ 和乘法规则，就得到 $x \equiv ub$。

逆元存在的条件恰好是 $\gcd (c, m) = 1$。如果最大公因数是 1，贝祖等式给出 $uc + vm = 1$，因此 $uc - 1 = -vm$，证明了 $uc \equiv 1$。反过来，如果 $uc \equiv 1$，就有 $uc - 1 = mk$，也就是 $1 = uc - mk$。$c$、$m$ 的每个正公因数都要整除这个组合，所以都要整除 1。如果 $1 = gh$，$g$、$h$ 都是正整数，$h \ge 1$ 就迫使 $g \le 1$，因此 1 的正因数只有 1，最大公因数就是 1。存在的条件和必要性都证明了。

刚才的 $1 = 3 \times 12 - 5 \times 7$ 说明，$-5$ 是 7 模 12 的一个逆元。加上 12，可以换成代表元 7。检查一下，$7 \times 7 = 49 = 4 \times 12 + 1$。逆元不是唯一的整数，因为加上模数的倍数还能成立，但它的余数只有一个。理由是：如果 $cu \equiv cv \equiv 1$，而且 $\gcd (c, m) = 1$，刚才证明的消去规则就给出 $u \equiv v \pmod{m}$。

现在我们可以解 $ax \equiv b \pmod{m}$：$a$ 是正整数，$b$ 是任意整数，$m \ge 2$，$x$ 是待求整数。“一次”说的是 $x$ 只乘上一个系数 $a$，没有平方或更高次幂。我们要回答三个问题：有没有解？怎么找出一个？又怎么知道已经找全？

先判断能不能有解

记 $d = \gcd (a, m)$。如果 $x$ 是解，就有整数 $k$ 使 $ax - b = mk$。移项得到 $b = ax - mk$。再把 $a = d(a/d)$、$m = d(m/d)$ 代入，就得到 $b = d((a/d)x - (m/d)k)$。括号里全部是整数，因此 $d$ 必须整除 $b$。例如 $6x \equiv 4 \pmod{9}$ 不可能成立：任何 $6x - 9k$ 都是 3 的倍数，可 $4 = 1 \times 3 + 1$ 不是。

现在假设 $d$ 的确整除 $b$，写 $b = dh$，其中 $h$ 是整数。贝祖等式给出 $ua + vm = d$。把整个等式乘以 $h$：$a(uh) + m(vh) = dh = b$。移项得到 $a(uh) - b = -m(vh)$。因此 $x_{0} = uh$ 就是一个解，因为它乘以 $a$ 后与 $b$ 的差是 $m$ 的倍数。于是有没有解的条件，两个方向都证明了：

再找全解，既不漏掉，也不添错

设 $x_{0}$ 是一个已经找到的解，$x$ 是任意另一个解。从 $ax \equiv b$ 中减去 $ax_{0} \equiv b$，减法规则给出 $a(x - x_{0}) \equiv 0 \pmod{m}$。使用刚才证明的正确消去规则，其中 $d = \gcd (a, m)$，得到 $x - x_{0} \equiv 0 \pmod{m/d}$。这意味着 $x - x_{0} = (m/d)t$，$t$ 是整数。所以每个解都必须长成下面这样：

还不能停下：我们得检查这样写出的每个整数都真的成立。代入可得 $ax - b = a(x_{0} + (m/d)t) - b = (ax_{0} - b) + m(a/d)t$。第一项是 $m$ 的倍数，因为 $x_{0}$ 已经是解；第二项也是，因为 $a/d$、$t$ 都是整数。两项之和仍是 $m$ 的倍数。因此这个公式给出了全部解，而且没有混入错误的解。

为什么按原模数分类，恰好有 $d$ 类解？

整数解有无限多个，但它们除以 $m$ 的余数并没有无限多个。在上面的公式里取 $t = 0$，1，…，$d - 1$，就得到 $d$ 个不同的余数类。为什么不同？如果 $t = i$、$t = j$ 对应的答案模 $m$ 同余，它们的差 $(m/d)(i - j)$ 就等于 $mk$。把这个等式除以正数 $m/d$，得到 $i - j = dk$。可是 $-d < i - j < d$，所以用唯一性证明里的理由，只能有 $i = j$。

这些类也包括其他所有整数 $t$。把 $t$ 除以 $d$，写 $t = dq + j$，其中 $0 \le j < d$；$d = 1$ 时余数就是 0。那么 $x_{0} + (m/d)t = x_{0} + (m/d)j + mq$。最后的 $mq$ 不改变模 $m$ 的余数，所以它已经落在 $j$ 所代表的那一类里。只要有解，就恰好有 $d$ 类。

完整算一次：$4x \equiv 2 \pmod{6}$

$6 = 1 \times 4 + 2$、$4 = 2 \times 2 + 0$ 给出 $d = 2$。2 整除右边的 2，所以有解。倒代得到 $2 = 6 - 4 = (-1) \times 4 + 1 \times 6$。这里 $h = b/d = 2/2 = 1$，因此 $x_{0} = (-1) \times 1 = -1$ 是一个解。间隔是 $m/d = 6/2 = 3$，所以全部解是 $x = -1 + 3t$。

我们也可以让这串数从 2 来写，因为 $-1 + 3t = 2 + 3(t - 1)$，而 $t - 1$ 仍然能取遍所有整数。写成 $x = 2 + 3k$ 后，模 6 的两个代表元就容易读出来了：2 和 5。直接代回去，可以检查整个解族，而不仅是这两个数：

每个整数 $k$ 都让这个式子成为 6 的倍数。反过来，上文又证明了每个解必须是这个形式。一个完整解答需要这两个方向的检查。

现在回到开头的巨大乘积。一个非负十进制整数 $N$ 的末位数字 $r$ 在 0 到 9 之间。前面的数字数的是完整的十，所以 $N = 10q + r$。因此末位数字恰好就是除以 10 的余数。我们要找的是 $7^{2026}$ 的余数，而不是整个很大的数。

只写出四行，不能证明规律永远重复。它之所以重复，是因为乘法规则：任何 $7^{n}$ 再乘以 $7^{4}$，就相当于把余数乘以 1，所以 $7^{n+4} \equiv 7^{n} \pmod{10}$。其中 $7^{n+4} = 7^{n} \times 7^{4}$，是把 $n$ 个因数 7 和另外 4 个因数 7 接在一起。

现在把因数的个数除以 4：$2026 = 4 \times 506 + 2$。2026 个因数可以分成 506 块，每块 4 个，最后再剩 2 个因数。每块的余数是 1，最后两个因数乘起来的余数是 9，因此：

末位就是 9。注意，我们把指数按已经证明的循环长度 4 来分组，并不是把 2026 换成它除以 10 的余数。数值使用的模数与循环长度，是两件不同的事。

为什么各位数字之和能判断是否被 9 整除？

一个四位数的数字依次为 $a$、$b$、$c$、$d$，表示 $N = 1000a + 100b + 10c + d$。这就是十进制位值的意思：$a$ 数千，$b$ 数百，$c$ 数十，$d$ 数个。因为 $10 = 1 \times 9 + 1$，所以 $10 \equiv 1 \pmod{9}$。幂的规则给出 $100 = 10^{2} \equiv 1^{2} = 1$，$1000 = 10^{3} \equiv 1^{3} = 1$。再用乘法、加法规则：

位数更多或更少也一样：额外的每一位的权重都是 10 的正整数次幂，余数仍然为 1；个位的权重本来就是 1。反复使用加法规则，就证明了任意有限位数都成立。一个数被 9 整除，恰好是余数为 0，所以它被 9 整除，当且仅当各位数字之和被 9 整除。

对于 2349，各位和是 $2 + 3 + 4 + 9 = 18 = 2 \times 9$，所以余数是 0；直接除也有 $2349 = 261 \times 9$。对于 2026，各位和是 $2 + 0 + 2 + 6 = 10 = 1 \times 9 + 1$，所以余数是 1；直接检查，$2026 = 225 \times 9 + 1$。这个规则现在有了理由，而且不只回答“能不能整除”，还给出了余数。

同余还能证明一个整数方程根本没有答案。看 $x^{2} = 4y + 2$，其中 $x$、$y$ 都是整数。我们不必不断试数，而可以先问两边模 4 的余数分别可能是什么。每个整数 $x$ 都恰好属于余数 0、1、2、3 中的一种。如果 $x \equiv r \pmod{4}$，已经证明的乘法规则给出 $x^{2} \equiv r^{2}$。因此下面四种情况能覆盖每一个整数：

因此整数的平方模 4 只能余 0 或 1，绝不余 2。右边 $4y + 2$ 总是余 2，即使 $y$ 是负数也一样，因为 $y$ 是整数商，而且 $0 \le 2 < 4$。两个相等的整数必须有同一个唯一的余数，现在两边却不可能有相同余数，所以没有任何整数对 $(x, y)$ 满足这个方程。