1804 年索菲·热尔曼给高斯写信时，两人说的是一种刚刚诞生的语言。三年前，在《算术研究》中，高斯引入了一个新符号 $\equiv$，以及一种看待整数的新方式：不看它们是什么，而看它们在除法中留下的余数。索菲后来关于费马的所有工作，都是用这种语言写成的。值得学一学。

钟表上的算术

如果现在是 9 点，5 小时后是几点？看指针表盘的人不会回答 14，而会回答 2。钟表只记住除以 12 的余数。高斯把它写成

$$14\equiv2\pmod{12},$$

读作“14 模 12 同余于 2”。一般地，$a\equiv b\pmod m$ 表示 $a$ 和 $b$ 除以 $m$ 余数相同，也就是 $a-b$ 是 $m$ 的倍数。

最大的好处是，同余式可以像等式一样相加、相乘。如果 $a\equiv b$ 且 $c\equiv d\pmod m$，那么

$$a+c\equiv b+d\qquad\text{且}\qquad a\cdot c\equiv b\cdot d\pmod m.$$

这样就可以在计算中途用很小的余数代替巨大的数。例如，$7^{100}$ 的个位数是多少？个位数就是除以 10 的余数。7 的幂的个位依次是 $7, 9, 3, 1$，然后循环，因为 $7^4=2401\equiv1\pmod{10}$。所以

$$7^{100}=\left(7^4\right)^{25}\equiv1^{25}=1\pmod{10}.$$

$7^{100}$ 有 85 位，我们不用算出其他任何一位，就知道了最后一位。

幂与余数

高斯最喜欢的题目，后来也是索菲最喜欢的，是模一个素数的幂。取素数 $p=7$，把每个数立方，只保留除以 7 的余数：

$x$ 0 1 2 3 4 5 6
$x^3 \bmod 7$ 0 1 1 6 1 6 6

只出现三个余数：$0$、$1$ 和 $6$，也就是 $0$ 和 $\pm1$，因为 $6\equiv-1\pmod7$。在 7 小时的钟表上看，立方数非常贫乏。索菲·热尔曼在她的费马定理中利用的正是这种贫乏。

为什么会这样？根据费马小定理，如果 $x$ 不是 7 的倍数，那么 $x^6\equiv1\pmod 7$。而 $x^6=(x^3)^2$。所以 $x^3$ 是一个平方等于 1 的数，而模一个素数，这样的数只有 $1$ 和 $-1$。只要 $2p+1$ 是素数，同样的论证都成立：模 $2p+1$ 的 $p$ 次幂只能是 $0$、$1$ 或 $-1$。

信里写了什么

在最初的几封信里，勒布朗先生寄给高斯《算术研究》中一些结果的新证明，以及一些推广。高斯回信时很高兴，因为找到了一位能超越他本人的读者。当他发现这位读者是谁时，他的钦佩更深了。在 1807 年的信中，高斯像送礼物一样，告诉她一些关于幂的余数的新结果，当时还没有发表。

练习：2¹⁰ 除以 11 的余数是多少？

$2^5=32=2\cdot11+10$，所以 $2^5\equiv10\equiv-1\pmod{11}$。于是 $2^{10}=\left(2^5\right)^2\equiv(-1)^2=1\pmod{11}$。这与费马小定理一致：$2^{11-1}\equiv1\pmod{11}$。

练习：五次幂除以 11 会留下哪些余数？

由于 $11=2\cdot5+1$ 是素数，正文中的论证说明只可能出现 $0$、$1$ 和 $-1\equiv10$。验证几个：$2^5=32\equiv10$，$3^5=243=22\cdot11+1\equiv1$，$4^5=1024=93\cdot11+1\equiv1$。从 $0$ 到 $10$ 的十一个数总共只给出余数 $0$、$1$ 和 $10$。

资料来源： Carl Friedrich Gauss，Disquisitiones arithmeticae（1801），第 1、2 条 · 索菲·热尔曼传记，MacTutor · Andrea Del Centina 与 Alessandra Fiocca，“The correspondence between Sophie Germain and Carl Friedrich Gauss”，Archive for History of Exact Sciences（2012）。

索菲·热尔曼的全部主题 · ← 索菲·热尔曼的一生 · 热尔曼定理与费马大定理 →

图片来源.