跳至内容
Topos Uranos
中文 (中国)

同余与模算术

摘要

本课把按余数对整数所作的分类变成一种演算。它定义模 nn 同余，证明同余等价于余数相等，证明同余是一个等价关系，并且与加法、乘法和乘方相容，再由它的类构造余数集合 Zn\mathbb{Z}_n 及其加法表和乘法表。借助裴蜀等式，它确定哪些余数有逆元，并完整地解出线性同余方程；它证明中国剩余定理和费马小定理，把整除判别法重新解读为同余，并把这一切应用于校验位、日历以及 RSA 密码体制，并证明该体制的正确性。

学习目标

  1. 证明模 nn 同余是一个与加法、乘法和乘方相容的等价关系，并用它计算大数的余数。
  2. 构造 Zn\mathbb{Z}_n 中的加法表和乘法表，并借助最大公因数确定哪些余数有逆元。
  3. 判断一个线性同余方程是否有解，计算它模 nn 有多少个解，并求出全部解。
  4. 用中国剩余定理解模两两互素的同余方程组，构造出解并证明其唯一性。
  5. 证明费马小定理，并把它应用于幂的余数、对一切整数成立的整除性质以及 RSA 体制的正确性。
  6. 分析校验位能发现哪些错误，并用同余计算星期几。

同余关系

如果今天是星期一，那么 1515 天后是星期二，10001000 天后是星期日：要知道这一点，不必一天一天地数，只需天数除以 77 的余数。同样，在有 55 个刻度的钟面上，99 点钟过 22 小时是 1212 点钟，而一个乘积的末位数字只取决于各因数的末位数字。在这三种情形中，人们都用余数计算而不管商。整除与带余除法一课按照除以一个自然数所得的余数把整数分成类，并证明了和、积与幂的余数只取决于原来各数的余数。本课赋予这些观察一种自己的语言，即同余的语言，它由高斯于 1801 年在《Disquisitiones Arithmeticae》中引入，并把它变成一种计算工具。和那一课一样，整数连同其运算法则和顺序法则是预先使用的，这些法则在整数一课中已得到论证。

定义（同余）。设 nn 为自然数。如果 aa 整除两个整数 bb 与 nn 的差 nn，就说它们模 a−ba - b 同余。记作 a≡b(modn)a \equiv b \pmod{n}，读作“aa 与 bb 模 nn 同余”；自然数 nn 称为这个同余式的模。
a≡b(modn)↔n∣a−ba \equiv b \pmod{n} \leftrightarrow n \mid a - b

例如 17≡2(mod5)17 \equiv 2 \pmod{5}，因为 17−2=1517 - 2 = 15；−3≡9(mod4)-3 \equiv 9 \pmod{4}，因为 −3−9=−12-3 - 9 = -12；一个整数是偶数，当且仅当它与 00 模 22 同余。aa 是 nn 的倍数这件事现在写作 a≡0(modn)a \equiv 0 \pmod{n}。模 11 时所有整数彼此同余，因为 11 整除每一个整数；这种情形没有意义，因此例子中的模至少为 22。三横的记号 ≡\equiv 让人想起等号，因为正如将要看到的，同余几乎在所有方面都像等式一样；例外是除法，由关于逆元的一节处理。

用差来下定义最便于证明，但开头那些例子的直观在于余数。下面的命题保证两种描述说的是同一回事；它的内容在整除一课论证整除判别法时已以另一种形式提到过，这里则给出全部步骤的证明。

命题同余与余数

两个整数模 nn 同余，当且仅当它们除以 nn 所得的余数相同。设 a=nq+ra = nq + r 与 b=ns+tb = ns + t 分别是 aa 与 bb 除以 nn 的带余除法，其中 0≤r<n0 \leq r < n 且 0≤t<n0 \leq t < n。图把从 −10-10 到 2424 的整数排成每行 55 个，使每一列汇集余数相同的数。

证明

  1. a−b=(nq+r)−(ns+r)=n(q−s)a - b = (nq + r) - (ns + r) = \resaltar{n(q - s)}

    如果余数相同，r=tr = t，那么两个除法式相减时余数消去，差是 nn 的倍数。

  2. a=b+nk=ns+t+nk=n(s+k)+ta = \resaltar{b} + nk = \resaltar{ns + t} + nk = \dato{d}{n(s + k) + t}

    反过来，假设 nn 整除 a−ba - b，即 a=b+nka = b + nk，其中 kk 是某个整数。代入 bb 的除法式。

  3. 0≤t<n→r=t0 \leq t < n \rightarrow \resaltar{r = t}

    由于 0≤t<n0 \leq t < n，这个等式就是 aa 除以 nn 的带余除法，余数为 tt。由商和余数的唯一性，tt 是 aa 的余数，即 t=rt = r。

  4. 23≡8≡−2≡−7≡3(mod5)23 \equiv 8 \equiv -2 \equiv -7 \equiv 3 \pmod{5}

    在图中，−7-7、−2-2、33、88、1313、1818 和 2323 位于同一列：它们的余数都是 33，彼此之差都是 55 的倍数。

特别地，每个整数都与它的余数模 nn 同余，这个余数是 nn 个整数 0,1,…,n−10, 1, \ldots, n - 1 中的一个，而且只与其中一个同余，因为其中任意两个数都是自身的余数，若它们不同，余数也不同。模 nn 计算就是把每个数换成它所在列中一个方便的代表：它的余数，有时也可以是一个小的负数，例如用 −1-1 代替 n−1n - 1。