同余

玻尔百科

核心要点

同余通过将整数按除法余数分组，简化了算术运算，将时钟上所见的“环绕”式数学形式化。
解线性同余方程的关键在于找到乘法逆元，当系数与模数互素时，乘法逆元存在，并可通过扩展欧几里得算法找到。
中国剩余定理为求解联立同余方程组提供了一种强有力的方法，这对于调度和密码学中的问题至关重要。
除了寻找解之外，同余还可以通过在一个有限的模系统中显示矛盾，来证明整数问题的解不存在。

引言

在我们熟悉的数字世界里，等于是绝对的。七等于七，不多不少。但如果我们考虑一种不同的等价关系，一种相距甚远的数字可以被视为相同的关系，情况会怎样呢？这就是同余的核心思想，它是现代数论的基石，将我们在看时间时本能使用的周期性、“环绕”式算术形式化了。虽然这个概念看似一个抽象的数学游戏，但它为解决那些用传统方法显得复杂甚至不可能的问题提供了一个极其强大的视角。本文将揭开同余世界的神秘面纱，弥合抽象理论与其对技术和科学的深远影响之间的鸿沟。

首先，在原理与机制一章中，我们将从零开始构建理论。我们将探索这种新算术的规则，学习如何在其中解方程，并发现像中国剩余定理这样的强大工具。然后，在应用与跨学科联系一章中，我们将看到这一理论的实际应用，揭示其在从计算机算法和密码安全到逻辑证明的极限等各个领域中的作用。让我们从探索支配这个迷人数学世界的基本原理开始吧。

原理与机制

一种新的等价关系：时钟的世界

想象一下你正在看一个标准的模拟时钟。如果是上午10点，有人问你5小时后是几点，你会说下午3点。你本能地进行了计算 $10 + 5 = 15$ ，然后意识到15点和3点是一样的。你刚刚做的就是模算术。在一个12小时制的时钟世界里，数字会“环绕”。数字3、15、27和-9在某种意义上是等价的——它们都指向时钟表盘上的同一个位置。

这种“环绕”的思想正是同余的核心。我们将其形式化为：如果两个整数 $a$ 和 $b$ 被 $n$ 除时余数相同，则称它们模 $n$ 同余。我们使用的记法是 $a \equiv b \pmod{n}$ 。一个等价且通常更强大的表述是，它们的差 $a-b$ 是 $n$ 的整数倍。也就是说， $n \mid (a-b)$ 且没有余数。

所以，对于我们的时钟，我们可以说 $15 \equiv 3 \pmod{12}$ ，因为它们的差 $15 - 3 = 12$ 是12的倍数。这种新型的等价关系——同余，比我们通常的等价概念要弱。虽然 $15 \neq 3$ ，但它们模12是同余的。同余将无限的整数直线分成 $n$ 个不同的“箱子”，我们称之为同余类或剩余类。对于模12，一个箱子包含 $\{\dots, -9, 3, 15, 27, \dots\}$ ，另一个包含 $\{\dots, -8, 4, 16, 28, \dots\}$ ，以此类推。

这似乎是一种奇怪的数学方式，但正是这种对等价关系的“粗化”使其如此强大。在计算机科学和密码学中，我们常常只关心计算的余数。例如，在著名的RSA密码系统中，所有的运算——加密和解密——都是在模某个非常大的数 $n$ 的情况下进行的。系统不关心底层的数是 $m$ 还是 $m + kn$ ；在模 $n$ 的世界里，密码学操作的结果将是相同的。

这个新世界有其自身的直观规则。例如，如果你知道两个数模30同余，你就能自动知道它们也模6同余，因为任何30的倍数也必然是6的倍数。如果 $30 \mid (a-b)$ ，那么必然有 $6 \mid (a-b)$ 。这就像知道时钟上的确切分钟数；由此你当然可以推断出你处于哪个10分钟的区间，但反之则不然。

游戏规则：解方程

现在我们有了一个拥有自己等价关系的新世界，我们能在其中进行代数运算吗？我们能解像 $34x \equiv 12 \pmod{89}$ 这样的方程吗？在普通代数中，我们会简单地“除以34”。但在同余的世界里，除法意味着什么呢？

除法实际上只是乘以一个逆元。要除以34，我们需要找到一个数，我们称之为 $34^{-1}$ ，使得 $34 \cdot 34^{-1} \equiv 1 \pmod{89}$ 。这个特殊的数被称为乘法逆元。如果我们能找到它，我们就能解我们的方程：

34^{-1} \cdot 34x \equiv 34^{-1} \cdot 12 \pmod{89}

1 \cdot x \equiv 34^{-1} \cdot 12 \pmod{89}

因此，核心问题变成了：一个整数 $a$ 何时存在模 $n$ 的乘法逆元？答案非常简单而深刻：逆元存在当且仅当 $a$ 和 $n$ 除了1之外没有其他公因数。换句话说，它们的最大公约数(GCD)必须是1，即 $\gcd(a,n) = 1$ 。这样的数被称为模 $n$ 的单位。

这个条件对于构建简单密码之类的应用至关重要。如果你用函数 $C(x) = (ax+b) \pmod{n}$ 加密一条消息，只有当 $a$ 是模 $n$ 的单位时，你才能保证唯一的解密。否则，多个不同的明文字母可能会加密成同一个密文字母，你的秘密消息就会在歧义中丢失。

但我们如何找到这个逆元呢？我们需要一个工具，一把解开答案的数学“钥匙”。这个工具就是扩展欧几里得算法。这个古老而强大的算法，仅仅是带余数除法的巧妙重复应用，不仅能找到两个数的GCD，还能将其表示为这两个数的线性组合。例如，对于我们的问题 $34x \equiv 12 \pmod{89}$ ，该算法揭示了这样一个优美的恒等式：

13 \cdot 89 - 34 \cdot 34 = 1

在模89的情况下看这个方程， $13 \cdot 89$ 项变为零，我们剩下 $-34 \cdot 34 \equiv 1 \pmod{89}$ 。所以，34的逆元是-34，它模89同余于 $-34+89=55$ 。现在我们可以解我们最初的方程了： $x \equiv 55 \cdot 12 = 660 \equiv 37 \pmod{89}$ 。

当 $\gcd(a,n) > 1$ 时会发生什么？在这种情况下， $a$ 不是一个单位；它是一种叫做零因子的东西。考虑模12的算术。数字4不是一个单位，因为 $\gcd(4, 12) = 4 \neq 1$ 。让我们看看当它与其他非零数相乘时会发生什么： $4 \cdot 3 = 12 \equiv 0 \pmod{12}$ 。我们把两个非零的东西相乘得到了零！这在常规数字中是不可能的，但在具有合数模的模世界里却是常态。零因子的存在意味着我们熟悉的消去律失效了。例如， $4 \cdot 3 \equiv 4 \cdot 6 \pmod{12}$ (因为两边都是0)，但我们不能“消去”4来得出 $3 \equiv 6 \pmod{12}$ 的结论。

这就引出了求解线性同余方程 $ax \equiv b \pmod n$ 的完整图景：

解存在当且仅当 $\gcd(a,n)$ 整除 $b$ 。
如果解存在，则恰好有 $\gcd(a,n)$ 个模 $n$ 不同余的解。

例如，对于同余方程 $96x \equiv 72 \pmod{252}$ ，我们发现 $\gcd(96, 252)=12$ 。由于12能整除72，解是存在的。并且恰好会有12个解！。在单位的情况下， $\gcd(a,n)=1$ ，它可以整除任何 $b$ ，所以总是有且仅有一个解，这与我们之前看到的完全一致。

玩转多个世界：中国剩余定理

如果我们必须同时满足几个同余条件怎么办？一个古老的谜题可能会问：“找一个数，它除以4余1，除以5余1，除以9余1。”这是一个同余方程组：

x \equiv 1 \pmod{4}

x \equiv 1 \pmod{5}

x \equiv 1 \pmod{9}

（当然，我们可以通过观察看出 $x=1$ 是一个解。）宏伟的中国剩余定理 (CRT) 告诉我们，只要模数（本例中为4、5和9）两两互素（任意两个都没有公因数），就总存在一个模这些模数之积（ $4 \times 5 \times 9 = 180$ ）的唯一解。这就像在不同维度中有坐标一样；给定一组有效的坐标，你就能精确定位一个单一、唯一的位置。

但如果模数不互素呢？考虑方程组：

x \equiv 101 \pmod{420}

x \equiv 59 \pmod{378}

这里，模数不互素； $\gcd(420, 378) = 42$ 。我们还能找到解吗？稍加思索就会发现一个潜在的冲突。如果一个数 $x$ 满足两个条件，它必须在模数的公共基础上表现一致。从第一个同余式推导出的任何性质都不能与从第二个同余式推导出的性质相矛盾。由于 $\gcd(420, 378)=42$ ，任何解 $x$ 都必须有特定的模42的余数。从第一个同余式， $x \equiv 101 \equiv 17 \pmod{42}$ 。从第二个同余式， $x \equiv 59 \equiv 17 \pmod{42}$ 。条件是一致的！广义中国剩余定理指出，解存在当且仅当 $a \equiv b \pmod{\gcd(n,m)}$ 。在我们的例子中， $101 \equiv 59 \pmod{42}$ ，所以解存在。当解存在时，它在模这些模数的最小公倍数 (LCM)，即 $\operatorname{lcm}(420, 378) = 3780$ 的意义下是唯一的。这个优雅的规则显示了小学概念中的GCD和LCM如何支配着这些系统的整个结构。

时钟的对数：指数运算

我们已经掌握了线性方程。但是对于更棘手的问题，比如 $x^9 \equiv 8 \pmod{13}$ ，该怎么办呢？这是一个多项式同余，试图通过暴力破解（测试从1到12的所有 $x$ 值）来解决它似乎既乏味又没有启发性。我们需要更深刻的洞察力。

关键在于找到与对数的深层类比。对数通过将乘法转化为加法来帮助我们解指数方程。我们能在我们的模世界里做同样的事情吗？可以，但仅当模数是素数时，比如 $p$ 。模素数的非零剩余类集合 $\mathbb{F}_p^\times = \{1, 2, \dots, p-1\}$ 有一个非常简单的结构：它是循环的。这意味着存在一个特殊的元素，称为原根或生成元，我们称之为 $g$ ，它的幂 $g^0, g^1, g^2, \dots, g^{p-2}$ 能生成集合中的每一个元素。

对于我们模13的问题，数字 $g=2$ 是一个原根。我们可以为模13的算术建立一个“对数表”： $2^0 \equiv 1$ $2^1 \equiv 2$ $2^2 \equiv 4$ $2^3 \equiv 8$ $2^4 \equiv 16 \equiv 3$ ... 以此类推。指数被称为指标或离散对数。例如， $\operatorname{ind}_2(8) = 3$ 。这个指标映射提供了一个同构——一个完美的、保持结构的转换——从 $\mathbb{F}_{13}^\times$ 的乘法世界到模 $p-1=12$ 的整数加法世界。

现在，让我们用这个“魔法”来解决我们的问题。设 $x \equiv 2^t \pmod{13}$ ，其中 $t = \operatorname{ind}_2(x)$ 是一个未知的指数。同余式 $x^9 \equiv 8 \pmod{13}$ 变为：

(2^t)^9 \equiv 2^3 \pmod{13}

2^{9t} \equiv 2^3 \pmod{13}

因为2是一个阶为12的生成元，这等价于指数模12同余：

9t \equiv 3 \pmod{12}

看发生了什么！困难的九次幂同余被转换成了一个简单的线性同余——一个我们已经知道如何解决的问题！。

我们检查解的存在性： $\gcd(9, 12) = 3$ ，并且3能整除3。所以指数 $t$ 模12恰好有3个解。这三个 $t$ 的值中的每一个都会给我们一个原始世界中 $x$ 的不同解。我们甚至不需要找到这些解，就能知道恰好有3个解。这项优美的技术揭示了数学深层的统一性，一个领域中的难题，通过纯粹的结构线索转换到另一个领域后，就变得简单了。

应用与跨学科联系

我们花了一些时间学习同余这个令人愉快的游戏的规则，这门只关注余数的艺术。但这一切是为了什么？这种看似抽象的数学在何处触及现实世界？你可能会感到惊讶。这并非仅限于黑板上的枯燥练习。这种思维方式被证明是观察世界的一个极其强大的透镜，它的印记出现在最意想不到的地方——从我们计算机的硅架构到关于逻辑和素性的最深层问题。那么，让我们来一次巡游，看看这个单一而优美的思想构建了什么。

日常数学与计算机的秘密机制

也许我们最直接看到同余作用的地方是在小学算术中学到的“技巧”中。你是否曾想过，为什么检查一个数是否能被3或9整除，你只需将其各位数字相加？这不是巧合或神奇的属性；这是模算术的直接结果。我们十进制系统中的一个数只是变量10的多项式： $N = d_t 10^t + \dots + d_1 10^1 + d_0 10^0$ 。当我们看这个数模9时会发生什么？由于 $10 \equiv 1 \pmod{9}$ ，10的任何次幂也模9同余于1。这个表达式优美地简化为： $N \equiv d_t(1) + \dots + d_1(1) + d_0(1) \pmod{9}$ 所以，一个数模9的余数与其各位数字之和相同！同样的原理使我们能够为任何基数下的任何数发明整除性检验。例如，要检验是否能被7整除，我们找到10的幂模7的重复序列（ $10^0 \equiv 1$ , $10^1 \equiv 3$ , $10^2 \equiv 2$ , $10^3 \equiv 6$ 等），并用它们作为各位数字的权重。这把一个乏味的长除法变成了一个简单的加权和，全靠同余的性质。

这种通过“模某个数”来简化结构的思想不仅仅用于心算；它对计算机的设计至关重要。当计算机程序将一个项目列表存储在数组中时，元素 A[i] 的内存地址是作为基地址加上一个偏移量来计算的。但现代处理器很挑剔；为了达到最快速度，它们通常要求所访问的数据在特定边界上“对齐”，比如64字节边界。这意味着内存地址必须是64的倍数。那么，如果我们有一个数组起始于一个未对齐的基地址，在数组开始前需要添加多少“填充”才能确保特定元素，比如 A[i]，被正确对齐？这无非是在同余式中求解填充量 $p$ 的问题： $\mathrm{address}(A) + p + i \cdot s \equiv 0 \pmod{k}$ 其中 $k$ 是对齐大小（例如64字节）， $s$ 是每个元素的大小， $i$ 是索引。这个简单的线性同余式，在我们的机器内部每秒被求解数十亿次，决定了数据在内存中的最优布局。

计算机算法的世界也充满了同余的应用。一个经典问题是在链表中检测循环，链表是一种每个元素指向下一个元素的数据结构。如果一个指针最终指回一个已经访问过的元素，你就有一个环。一个巧妙的检测方法是“龟兔赛跑”算法，其中一个指针每次移动一步（ $v_1=1$ ），另一个每次移动两步（ $v_2=2$ ）。如果有一个长度为 $n$ 的环，它们何时会相遇？它们的位置由环上的模算术决定。它们的相遇保证在它们的位置模 $n$ 同余时发生。求解它们相遇的时间 $t$ 归结为求解一个形如 $(v_1 - v_2)t \equiv d \pmod n$ 的线性同余式，其中 $d$ 是它们的初始距离。数据结构中的物理环是模 $n$ 整数环的完美镜像。

调度与同步的艺术

现实世界中的许多问题都涉及到对齐以不同周期重复的事件。想象一组天体，每个都有不同的轨道周期。它们下一次将在天空中的什么时间对齐？或者，考虑一个更接地气的例子：一个分布式系统运行几个独立的备份任务，每个任务都有自己的时间表。任务A每5小时运行一次，从第2小时开始。任务B每7小时运行一次，从第3小时开始。两个任务第一次同时运行是什么时候？这是一个关于寻找一个时间 $t$ 来满足一个同余方程组的问题： $t \equiv 2 \pmod{5}$ $t \equiv 3 \pmod{7}$ 古老的中国剩余定理（CRT）为我们提供了一个优美且具建设性的方法来解决这类系统。它不仅告诉我们解是否存在，还告诉我们如何找到它，并保证解本身形成一个简单的算术级数。这个强大的工具被用来从稀疏样本中重建信号，加速密码学中的计算，并解决无数的调度和同步难题。

当然，现实世界往往比经典定理的简洁条件要混乱，该定理假设模数是两两互素的。如果我们的任务运行在具有公因数的时间表上怎么办？同余的数学机制足够强大来处理这种情况。通过小心地使用扩展欧几里得算法，我们可以开发出通用的求解器，即使在模数不互素时也能工作，正确地识别出时间表何时不兼容，或者将它们合并成一个描述所有可能同时发生的事件的单一、统一的同余式。这种从一个优雅的定理到一个健壮、通用的算法的转变，是数学工程的精髓。

阻碍与抽象的力量

到目前为止，我们一直使用同余来寻找解。但它们在证明不存在解方面同样强大。这是数学中一个深刻而微妙的方面。你如何证明某事是不可能的？最优雅的方法之一是证明，如果一个解存在于广阔、无限的整数世界中，它也必须存在于小而有限的模 $n$ 整数世界中。如果我们能找到一个模数 $n$ ，使得问题在该模下无解，那么我们就证明了不可能存在任何整数解。

这种“同余阻碍”的一个壮观例子来自一个困扰了数学家几个世纪的问题：哪些数可以写成三个完全平方数之和？无论你怎么尝试，你永远无法将数字7写成三个平方数之和。为什么？让我们在模8的情况下看这个问题。任何平方数（ $x^2$ ）除以8的余数只能是0、1或4。所以，三个平方数之和 $x^2+y^2+z^2$ 除以8的余数只能是0、1、2、3、4、5或6。它永远不能产生7的余数。因此，任何形如 $8b+7$ 的整数都不能是三个平方数之和。这个基于有限可能性集合的简单论证，证明了关于无限整数集合的一个深刻事实。Legendre的三平方和定理将此精炼为：不能写成三个平方数之和的数，恰好是那些形如 $4^a(8b+7)$ 的数。相比之下，Lagrange的四平方和定理指出，每个正整数都可以写成四个平方数之和——同余阻碍消失了。

这种使用同余作为过滤器的方法是数论学家的标准工具。它为形如 $ax+by=c$ 的线性丢番图方程的可解性条件提供了最简单的证明。整数解 $(x,y)$ 存在当且仅当 $d = \gcd(a,b)$ 整除 $c$ 。“当”的部分需要更多的工作，但“仅当”的部分是一个惊人地简单的同余论证。如果我们看这个方程模 $d$ 的情况，我们知道 $a \equiv 0 \pmod d$ 和 $b \equiv 0 \pmod d$ 。因此，整个左边 $ax+by$ 必须模 $d$ 同余于0。为了使等式成立，右边 $c$ 也必须模 $d$ 同余于0，这只是说 $d$ 必须整除 $c$ 的另一种方式。

同余的力量在于其结构性，这意味着这个思想可以从整数提升到更抽象的领域。我们可以谈论矩阵、多项式或任何代数环中元素的同余。例如，我们可以解决一个矩阵同余系统，比如找到一个 $2 \times 2$ 矩阵 $A$ 同时满足模2和模3的两个不同条件。中国剩余定理同样适用，我们只需将整数版本独立地应用于矩阵的每个元素即可解决问题。这暗示了在抽象代数中发现的广泛推广，其中同余被用来从旧的数学世界构建新的数学世界。

逻辑与计算的前沿

我们的巡游在现代科学的前沿结束，同余在这里在我们对计算和逻辑本身的理解中扮演着主角。

现代密码学的一个基石是能够有效地确定一个非常大的数是否是素数。第一次尝试可能是使用费马小定理，该定理指出，如果 $n$ 是一个素数，那么对于任何整数 $a$ ，有 $a^n \equiv a \pmod n$ 。这提供了一个强大的基于同余的测试。但它并不完美；存在一些合数，称为卡迈克尔数，它们公然说谎并对所有的 $a$ 满足这个同余式。几十年来，一个“完美”测试的问题一直悬而未决。

突破出现在2002年，随着Agrawal–Kayal–Saxena（AKS）素性测试的问世。其核心思想是对费马测试的惊人推广。它不是检查一个数的同余，而是检查一个多项式的同余。条件变为： $(x+a)^n \equiv x^n + a \pmod{n}$ 这个测试，在系数模 $n$ 的多项式环中进行，要强大得多。整数测试只是一个单一的约束，而多项式测试是一束同时的约束，多项式的每个系数对应一个。事实证明，这个多项式恒等式成立当且仅当 $n$ 是素数。没有“说谎者”。通过巧妙地将这些多项式再模一个精心选择的 $x^r-1$ ，作者们将这个理论上完美但计算上不可行的测试，转变成了一个可证明的高效、确定性算法。

最后，同余出现在计算机能做什么和不能做什么的根本基础上。在数理逻辑中，一个核心问题是计算机是否能自动确定任何给定数学陈述的真伪。对于大多数数学领域，答案是否定的（哥德尔不完备定理）。但对于某些受限的领域，这是可能的。其中一个领域是普莱斯伯格算术——只带加法和序的自然数理论。该理论可判定性的一个关键是一种称为“量词消去”的过程。这是一种算法，可以取一个像“存在一个数 $y$ 使得...”这样的陈述，并将其转换为一个没有“存在”的等价陈述。而驱动这种消去的机制是什么？正是我们解决线性不等式系统和——你猜对了——同余的能力。算法上可判定的概念本身就与我们对这些基本概念的掌握程度紧密相连。

从简单的课堂技巧到我们机器的架构，从安排宇宙时钟到证明某些几何形式的不可能性，从我们数据的安全到形式逻辑的极限，同余的概念展现开来。这样一个简单的思想——只关心余数——能够在人类思想的整个版图上编织出如此丰富而复杂的织锦，这证明了数学深刻的美。