离散数学/数论

简介

'数论' 本身就是一个庞大而涵盖面广的学科。我们将在这里探讨数论中的关键概念。

与实分析和微积分处理稠密实数集不同，数论考察的是离散集合中的数学，例如N或Z。如果你不确定集合的概念，你可能需要重新阅读集合论。

数论是研究整数的学科，它是数学中最古老和最丰富的分支之一。它的基本概念包括整除性、素数和方程的整数解——这些概念都很容易理解，但它们立即引出了数学中最著名的定理和最大的未解问题。数论也是一门高度跨学科的学科。组合学（计数的研究）、代数和复分析中的思想都找到了自己的位置，最终成为理解数论各个部分的必要条件。事实上，所有数学中最伟大的开放问题，黎曼猜想，与复分析有着密切的联系。但不要害怕，直接开始学习初等数论吧，它是最热情的纯数学邀请之一，也是应用数学中最令人惊讶的领域之一！

整除性

请注意，在R、Q和C中，我们可以自由地除法，除了零。这个性质通常称为封闭性——两个有理数的商仍然是有理数，等等。但是，如果我们把数学运算限制在Z这样的集合中，就会遇到困难。这是因为，在整数中，两个整数相除的结果可能不是另一个整数。例如，我们当然可以将 6 除以 2 得到 3，但我们不能将 6 除以 5，因为分数 6/5 不属于整数集。

然而，我们可以引入一个新的关系，其中定义了除法。我们把这种关系称为整除性，如果${\frac {b}{a}}$是一个整数，我们就说

• $a$ 整除 $b$
• $a$ 是 $b$ 的一个因子
• $b$ 是 $a$ 的一个倍数
• $b$ 可以被 $a$ 整除

形式上，如果存在一个整数 $q$ 使得 $b=qa$，那么我们说 $a$ **整除** $b$，并写作 $a\mid b$。如果 $a$ 不整除 $b$，那么我们写作 $a\nmid b$

**命题。** 以下是该定义的一些基本推论。令 a，b，c 为整数

• (a) 如果 a|b，那么 a|(bc)。
• (b) 如果 a|b 且 b|c，那么 a|c。
• (c) 如果 a|b 且 a|c，那么对于任意整数 x 和 y，a|(xb+yc) - 换句话说，a 整除其倍数的任何线性组合。
• (d) 如果 a|b 且 b|a，那么 a = b 或 a = -b。
• (e) 如果 c 不为 0，那么 a|b 等价于 ca|cb。

商和余数定理

对于任何整数 n 和任何 k > 0，存在唯一的 q 和 r 使得

n = qk + r (其中 0 ≤ r < k)

这里 n 被称为被除数。

我们称 q 为 **商**，r 为 **余数**，k 为 **除数**。

通过代数重排，这个定理可能更容易理解

n/k = q + r/k (0 ≤ r/k < 1)

模运算

我们能对整除另一个数的数说些什么？以 8 为例。1 除以 8 的余数是多少？使用上面的除数定理

0 = 8*0 + 0

1 = 8*0 + 1

2 = 8*0 + 2

:

8 = 8*1 + 0

9 = 8*1 + 1

10 = 8 * 1 + 2

:

等等

我们对余数有一个表示法，可以将上面的等式写成

0 mod 8 = 0

1 mod 8 = 1

2 mod 8 = 2

3 mod 8 = 3

4 mod 8 = 4

5 mod 8 = 5

6 mod 8 = 6

7 mod 8 = 7

8 mod 8 = 0

9 mod 8 = 1

10 mod 8 = 2

:

我们也可以写成

1 ≡ 1 (mod 8)

2 ≡ 2 (mod 8)

3 ≡ 3 (mod 8)

4 ≡ 4 (mod 8)

5 ≡ 5 (mod 8)

6 ≡ 6 (mod 8)

7 ≡ 7 (mod 8)

8 ≡ 0 (mod 8)

9 ≡ 1 (mod 8)

10 ≡ 2 (mod 8)

:

这些表示法都简短地代表了

a = 8k+r，其中 k 为整数。

因此，例如，x ≡ 1 (mod 8) 等同于说

x = 8k+1

注意，这里比较除数算法的余数是 1。x ≡ 1 (mod 8) 询问哪些数除以 8 的余数为 1？显然，解是 x=8×0+1, 8×1+1,... = 1, 9, ...

通常情况下，我们对除以 n 的所有余数集合感兴趣 - 我们称之为 **模 n** - 并写作 Z_n。注意，该集合是有限的。9 除以 8 的余数是 1，与 1 除以 8 的余数相同。因此，在某种意义上，9 实际上是“与” 1 “相同”。事实上，关系 “≡”

x ≡ y 当且仅当 x mod n = y mod n。

是一个等价关系。我们称该关系为 **同余**。注意，由同余定义的等价类正是 Z_n 的元素。

我们可以通过使用除数算法找到一个模 n 的数 a（或说 a 与 n 同余）。

加法、减法和乘法在 Z_n 中有效 - 例如 3 + 6 (mod 8) = 9 (mod 8) = 1 (mod 8)。这些数字看起来很奇怪，但它们遵循许多正常的性质，例如交换性和结合性。

如果我们有一个大于 n 的数，我们通常先把它归约到模 n - 再次使用除数算法。例如，如果我们想要找到 11+3 mod 8，通常更容易计算 3 + 3 (mod 8)，而不是将 14 归约到模 8。一个常用的技巧是，例如，如果我们有 6 + 7 (mod 8)，我们可以使用 **负** 数代替，使问题变为 -2 + -1 = -3 = 5 (mod 8)。

当我们想要查看包含模某个 n 的数的方程时，我们经常使用第二种表示法。例如，我们可能想要找到一个数 x 使得

3x ≡ 5 (mod 8)

我们可以通过试探法来找到解（遍历从 0 到 7 的所有数字），但如果模数非常大怎么办？我们将在后面研究更系统的解决方案。

**注意：** 我们通常说我们在 Z_n 中工作，并在整个过程中使用等号。熟悉这三种写模运算方程和表达式的形式。

模运算的一致性

令 $n\geq 2$ 表示任意基数。给定任意整数 $x$，整数序列 $...,x-2n,x-n,x,x+n,x+2n,...$ 在模 $n$ 意义下彼此同余。

$...\equiv x-2n\equiv x-n\equiv x\equiv x+n\equiv x+2n\equiv ...\;\;({\text{mod}}\;n)$

在模运算中，两个在模 $n$ 意义下同余的整数 $x$ 和 $y$ ($x\equiv y\;\;({\text{mod}}\;n)$) 都“代表”来自 $\mathbb {Z} _{n}$ 的相同量。只要 $x\equiv y\;\;({\text{mod}}\;n)$，可以用任意整数 $x$ 代替整数 $y$。

这意味着

• 给定任意整数 $x_{1},x_{2}$ 和 $y_{1},y_{2}$，如果 $x_{1}\equiv x_{2}\;\;({\text{mod}}\;n)$ 并且 $y_{1}\equiv y_{2}\;\;({\text{mod}}\;n)$，那么 $x_{1}+y_{1}\equiv x_{2}+y_{2}\;\;({\text{mod}}\;n)$。

证明

由于 $x_{1}\equiv x_{2}\;\;({\text{mod}}\;n)$，存在整数 $k_{x}\in \mathbb {Z}$ 使得 $x_{2}=x_{1}+k_{x}n$。

由于 $y_{1}\equiv y_{2}\;\;({\text{mod}}\;n)$，存在整数 $k_{y}\in \mathbb {Z}$ 使得 $y_{2}=y_{1}+k_{y}n$。

可以推导出 $x_{2}+y_{2}=(x_{1}+k_{x}n)+(y_{1}+k_{y}n)=(x_{1}+y_{1})+(k_{x}+k_{y})n$，因此 $x_{1}+y_{1}\equiv x_{2}+y_{2}\;\;({\text{mod}}\;n)$。

• 对于任意整数 $x_{1},x_{2}$ 和 $y_{1},y_{2}$，如果 $x_{1}\equiv x_{2}\;\;({\text{mod}}\;n)$ 且 $y_{1}\equiv y_{2}\;\;({\text{mod}}\;n)$，则 $x_{1}y_{1}\equiv x_{2}y_{2}\;\;({\text{mod}}\;n)$。

证明

由于 $x_{1}\equiv x_{2}\;\;({\text{mod}}\;n)$，存在整数 $k_{x}\in \mathbb {Z}$ 使得 $x_{2}=x_{1}+k_{x}n$。

由于 $y_{1}\equiv y_{2}\;\;({\text{mod}}\;n)$，存在整数 $k_{y}\in \mathbb {Z}$ 使得 $y_{2}=y_{1}+k_{y}n$。

可以推导出 $x_{2}y_{2}=(x_{1}+k_{x}n)(y_{1}+k_{y}n)=x_{1}y_{1}+k_{x}y_{1}n+x_{1}k_{y}n+k_{x}k_{y}n^{2}$$=x_{1}y_{1}+(k_{x}y_{1}+x_{1}k_{y}+k_{x}k_{y}n)n$ 因此 $x_{1}y_{1}\equiv x_{2}y_{2}\;\;({\text{mod}}\;n)$.

进制

在数学中，不同进制之间的转换是最繁琐的过程之一。

我们日常生活中使用的数字都是十进制的。这意味着用十个数字来表示一个数字。这十个数字是 {0,1,2,3,4,5,6,7,8,9}。

类似地，四进制有四个数字 {0,1,2,3}，二进制有两个数字 {0,1}。二进制有时被称为二进制。

还有大于十进制的进制。对于这些进制，通常使用字母来表示大于十的数字。例如十六进制（Hexadecimal）。此进制中使用的数字是 {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}。

为了在不同进制之间进行转换，必须知道如何进行除法并求余数。

要从十进制转换为其他进制，只需要不断地用目标进制的值进行除法，然后对第一个除法的结果再进行除法，忽略余数，依此类推，直到结果小于目标进制的值（因此除法的结果将为零）。然后，目标进制的数字是从末尾到开头读取的余数。

以下展示了如何将十进制数（105）转换为二进制。

运算	余数
105 / 2 = 52	1
52 / 2 = 26	0
26 / 2 = 13	0
13 / 2 = 6	1
6 / 2 = 3	0
3 / 2 = 1	1
1 / 2 = 0	1

答案： 1101001

完成此过程后，将余数从下到上依次排列，然后将最后一个商（在本例中为 1101001）显示为数字 105 的二进制等价值。

总而言之，将十进制的原始数字反复进行除法，记录余数，直到商小于进制的数值。

这适用于将任何十进制数字转换为任何进制。如果进制中存在任何字母，则使用字母替换大于 9 的任何余数。例如，将十进制中的 11 写成十四进制。

运算	余数
11 / 14 = 0	B (=11)

答案： B

由于 11 只有一个余数，所以它被写成一个数字。根据模式 {10=A, 11=B, 12=C...35=Z}，将其写成 B。如果你写 “11” 作为答案，那就是错误的，因为十四进制的 “11” 等于十进制的 15！

要将任何进制的数字转换为十进制，应使用以下过程

以十进制的 3210 为例。在个位（10⁰）上是 0。在十位（10¹）上是 1。在百位（10²）上是 2。在千位（10³）上是 3。

计算上述数字值的公式为

3×10³ + 2×10² + 1×10¹ + 0×10⁰ = 3000 + 200 + 10 + 0 = 3210。

从任何进制转换为十进制的过程类似。例如，以六进制的 3452 为例。在个位（6⁰）上是 2。在六位（6¹）上是 5。在三十六位（6²）上是 4。在 216 位（6³）上是 3。

计算上述数字值（在十进制中）的公式为

3×6³ + 4×6² + 5×6¹ + 2×6⁰ = 648 + 144 + 30 + 2 = 824。

六进制的 3452 在十进制中为 824。

一种更高效的算法是将最左边的数字加上进制值，然后重复该过程，依次处理下一个数字。

((3 * 6 + 4) * 6 + 5) * 6 + 2 = 824

不同进制之间的转换过程乍看起来可能很困难，但如果经常练习，就会变得很容易。

质数

质数是整数的基石。质数是一个大于 1 的正整数，它只有两个约数：1 和它本身。例如，17 是质数，因为只有 1 和 17 才能整除它。数字 6 不是质数，因为 6 有超过两个约数，分别是 1、2、3、6。此外，请注意 1 不是质数，因为 1 只有一个约数。

一些质数

质数序列的开头是

2, 3, 5, 7, 11, 13, 17, 19, 23, ...

欧几里得证明存在无限多个质数

古希腊数学家欧几里得给出了一个关于质数无穷多的优雅证明。这个证明依赖于这样一个事实，即所有非质数——合数——都可以被唯一地分解成质数的乘积。

欧几里得的证明采用反证法：我们假设质数只有有限个，然后证明我们可以得出逻辑上矛盾的事实。

所以我们开始了。首先，我们假设质数只有有限个

p₁, p₂, ... , p_n

现在考虑以下定义的数字 M

M = 1 + p₁ * p₂ * ... * p_n

关于数字 M 有两个重要的事实——最终是矛盾的

1. 它不可能是质数，因为 p_n 是最大的质数（根据我们的初始假设），而 M 明显大于 p_n。因此，一定存在某个质数 p 可以整除 M。
2. 它不能被 p₁, p₂, ..., p_n 中的任何一个数字整除。考虑一下，如果你试图将 M 除以列表 p₁, p₂, ... , p_n 中的任何一个质数会发生什么。从 M 的定义可以看出，你最终会得到余数 1。这意味着 p——整除 M 的质数——必须大于 p₁, ..., p_n 中的任何一个。

因此，我们证明了 M 可以被一个比 p_n 大的质数 p 整除。因此，不可能存在最大的质数。

这两个事实表明，M 必须被一个大于 p_n 的质数整除。因此，不可能存在最大的质数。

请注意，此证明并未提供直接生成任意大素数的方法，尽管它始终会生成一个被新的素数整除的数字。假设我们只知道一个素数：2。因此，我们的素数列表很简单，即 p₁=2。然后，在证明的符号中，M=1+2=3。我们注意到 M 是素数，因此我们将 3 添加到列表中。现在，M = 1 +2 *3 = 7。同样，7 是素数。因此，我们将其添加到列表中。现在，M = 1+2*3*7 = 43：又是素数。继续此过程一次，我们计算 M = 1+2*3*7*43 = 1807 =13*139。因此，我们看到 M 不是素数。

从另一个角度来看：注意，虽然 1+2、1+2*3、1+2*3*5、1+2*3*5*7 和 1+2*3*5*7*11 是素数，但 1+2*3*5*7*11*13=30031=59*509 不是。

素数测试

有很多简单而复杂的素数测试方法。我们将在本文中介绍一些简单的测试方法。在高级课程中，我们将介绍一些更快、更复杂的方法来测试一个数字是否是素数。

检查

最直接、最简单的排除数字 n 为素数的方法是检查数字的个位数或最后一位。

如果数字 n 以偶数 0、2、4、6、8 结尾，我们可以证明数字 n 不能是素数。例如，取 n = 87536 = 8753(10) + 6。由于 10 可被 2 整除，6 可被 2 整除，因此 87536 必须可被 2 整除。一般而言，任何偶数都可以表示为 n = a*10 + b 的形式，其中 b = 0、2、4、6、8。由于 10 可被 2 整除，b 可被 2 整除，因此 n = a*10 + b 可被 2 整除。因此，任何以偶数结尾的数字 n，例如 7777732 或 8896，都可以被 2 整除，因此 n 不是素数。

在类似的论证中，如果数字 n 以 5 结尾，我们可以证明数字 n 不能是素数。如果 n 的最后一位数字，称之为 b，是 5，我们可以将 n 表示为 n = a*10 + b 的形式，其中 b = 5。由于 10 可被 5 整除，b = 5 可被 5 整除，因此 n = a*10 + b 可被 5 整除。因此，任何以 5 结尾的数字 n，例如 93475，都可以被 5 整除，因此 n 不是素数。

因此，如果大于 5 的数字是素数，它必须以 1、3、7 或 9 结尾。注意，这并不意味着所有以 1、3、7 或 9 结尾的数字都是素数。例如，虽然数字 11、23、37、59 是素数，但数字 21 = 3*7、33 = 3*11、27 = 3*9、39 = 3*13 不是素数。因此，如果数字以 1、3、7 或 9 结尾，我们需要进一步测试。

试除法

要测试以 1、3、7 或 9 结尾的数字 n 是否是素数，我们可以简单地尝试最小的素数，并尝试将其除以 n。如果不能整除，我们将取下一个最大的素数，然后再次尝试，依此类推。当然，如果我们以这种方式取所有小于 n 的素数，并且无法除以 n，那么我们有理由说 n 是素数。然而，可以证明，我们不必取所有小于 n 的素数来测试 n 是否是素数。我们可以使用试除法更早地停止测试。

试除法的理由是，如果数字 n 没有小于或等于 ${\sqrt {n}}$ 的除数，那么 n 必须是素数。我们可以用反证法来证明这一点。假设 n 没有小于或等于 ${\sqrt {n}}$ 的除数。如果 n 不是素数，则必须存在两个数字 a 和 b 使得 $a*b=n$。特别地，根据我们的假设，${\sqrt {n}}<a$ 并且 ${\sqrt {n}}<b$。但是，然后 $n={\sqrt {n}}{\sqrt {n}}<a*b=n$。由于数字不能大于自身，因此数字 n 必须是素数。

试除法是一种素数测试方法，它涉及取一个数字 n，然后依次用小于或等于 ${\sqrt {n}}$ 的素数除以它。

例如，113 是素数吗？${\sqrt {113}}$ 大约为 10.63... 我们只需要测试 2、3、5、7 是否能整除 113（不留余数，即商是整数）。

113/2 不是整数，因为最后一位数字不是偶数。

113/3 (=37.666...) 不是整数。

113/5 不是整数，因为最后一位数字不以 0 或 5 结尾。

113/7 (=16.142857...) 不是整数。

因此，我们不需要查看小于 113 的任何其他素数，例如 11、13、17 等，因为 2、3、5、7 不能整除 113，所以 113 是素数。

注意，在排除了 2 和 3 作为除数之后，我们接下来考虑下一个素数 5，而不是下一个数字 4。我们知道不要考虑 4，因为我们知道 2 不能整除 113。如果 2 不能整除 113，那么 4 肯定也不能，因为如果 4 整除 113，并且 2 整除 4，那么 2 就应该整除 113。所以我们只使用下一个最便宜的素数来测试，而不是下一个连续的数字。

如果我们测试 91，我们会得到：

91/2 不是整数，因为最后一位数字不是偶数。

91/3= (30.333) 不是整数。

91/5= 不是整数，因为最后一位数字不以 0 或 5 结尾。

91/7=13 是整数

所以我们知道，由于 7 整除 91，所以 91 不是素数。

试除法通常只用于相对较小的数字，因为它效率低下。但是，该技术有两个优点：首先，一旦我们测试了数字，我们就可以确定它是素数；其次，如果数字不是素数，它也会给出数字的因子。

为了获得一些小的素数，最好使用 埃拉托斯特尼筛法，而不是使用试除法顺序测试每个数字。 埃拉托斯特尼筛法基本上是一个通过消除来寻找素数的过程。 我们首先从一个连续数字列表开始，比如 1 到 100。 将数字 1 删除，因为该数字不是素数。 选择下一个最小的未划去的数字 2，并将其圈起来。 现在，在列表中划去所有 2 的倍数。 接下来，选择下一个最小的未圈起的数字 3。 将数字 3 圈起来，并划去所有 3 的倍数。 下一个最小的未圈起的数字应该是 5，因为 4 是 2 的倍数，应该已经被划去了。 将数字 5 圈起来，并划去所有 5 的倍数。 下一个最小的未圈起的数字应该是 7，因为 6 是 2 的倍数。 将 7 圈起来，并划去所有 7 的倍数。 现在，下一个未划去的数字应该是 11，因为 8、9、10 分别是 2、3 和 2 的倍数。 如果我们继续以这种方式进行，剩下的就是圈起来的数字，即素数。 但是请注意，在划去 7 的倍数后，我们实际上可以停止并圈起所有未划去的数字，因为根据结果，由于 ${\sqrt {100}}=10$ 小于 100 的任何非素数都必须能被 2、3、5 或 7 整除。

算术基本定理

算术基本定理是一个关于数字分解的重要定理。 该定理基本上指出，每个正整数都可以以唯一的方式写成素数的乘积（忽略素数乘积的顺序）。

特别是，算术基本定理意味着任何数字，例如 1,943,032,663，要么是素数，要么可以分解成素数的乘积。 如果像 1,943,032,663 这样的数字可以分解成素数，例如 11×13×17×19×23×31×59，那么尝试寻找另一个不同的素数组合来得到相同的数字是徒劳的。

为了使该定理对数字 1 仍然适用，我们认为 1 是零个素数的乘积。

更正式地说，

对于所有 n∈N

n=p₁p₂p₃...

其中 p_i 都是素数，可以重复。

以下是一些示例。

4 = 2 × 2 = 2²

12 = 2 × 2 × 3 = 2² × 3

11 = 11.

在建立贝祖等式之后，将给出算术基本定理的证明。

最小公倍数和最大公约数

我们可以根据两个数字的分解确定它们的两个特征：最小公倍数，即LCM，和最大公约数，即GCD（也称为最大公因数，即GCF）

最小公倍数

两个数字 a 和 b 的最小公倍数（或最小公倍数）是指由 LCM(a,b) 表示的最小数字，该数字既能被数字 a 整除，又能被数字 b 整除。 我们可以通过找到 a 和 b 的素数分解，并为每个素数因子选择最大幂来找到 LCM(a,b)。

换句话说，如果数字 a 分解成 $p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{n}^{\alpha _{n}}$，而数字 b 分解成 $p_{1}^{\beta _{1}}p_{2}^{\beta _{2}}\cdots p_{n}^{\beta _{n}}$，那么 LCM(a,b) = $p_{1}^{\gamma _{1}}p_{2}^{\gamma _{2}}\cdots p_{n}^{\gamma _{n}}$，其中 $\gamma _{i}=Maximum(\alpha _{i},\beta _{i})$ 对于 i = 1 到 n。

例如，让我们看看如何找到 5500 和 450 的最小公倍数，它恰好是 49500。 首先，我们找到 5500 和 450 的素数分解，即

5500=2² 5³ 11

450=2 3 ² 5²

注意，我们为数字 5500 和数字 450 得出的不同素数是 2、3、5 和 11。 现在，让我们用这些素数的适当幂来完全表示 5500 和 450。

5500=2² 5³ 11 = 2² 3⁰ 5³ 11¹

450=2 3² 5² = 2¹ 3² 5² 11⁰

LCM(5500,450) 将以 2^? 3^? 5^? 11^? 的形式出现。 现在我们只需要找到每个素数的幂是多少。

因此，我们比较 5500 和 450 中每个素数的幂。 让我们考虑第一个素数 2 的幂。 在数字 5500 中，素数 2 的幂是 2，而在数字 450 中，素数 2 的幂是 1。 由于素数 2 的幂在 2 和 1 之间的最大值是 2，因此我们使用 2 作为素数 2 的幂。

现在让我们考虑素数 3 的幂。 在数字 5500 中，素数 3 的幂是 0，而在数字 450 中，素数 3 的幂是 2。 由于素数 3 的幂在 0 和 2 之间的最大值是 2，因此我们使用 2 作为素数 3 的幂。

类似地，让我们考虑下一个素数 5 的幂。 在数字 5500 中，素数 5 的幂是 3，而在数字 450 中，素数 5 的幂是 2。 由于素数 5 的幂在 3 和 2 之间的最大值是 3，因此我们使用 3 作为素数 5 的幂。

最后，让我们考虑素数 11 的幂，它是我们列表中的最后一个素数。在数字 5500 中，素数 11 被提升到第一幂，在数字 450 中，素数 11 被提升到零次幂。由于素数 11 的幂在 1 和 0 之间的最大值为 1，因此我们使用 1 作为最后一个素数 11 的幂。

因此，我们结果的乘积是 LCM(5500,450)=2² 3² 5³ 11¹ = 49500。

GCD

两个数字 a 和 b 的最大公约数是表示为 GCD(a,b) 的最大数字，它同时可以整除数字 a 和数字 b。与查找 LCM(a,b) 的过程类似，我们可以通过查找 a 和 b 的质因数分解来找到 GCD(a,b)，但选择每个质因子的最小幂。

换句话说，如果数字 a 分解为 $p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{n}^{\alpha _{n}}$，而数字 b 分解为 $p_{1}^{\beta _{1}}p_{2}^{\beta _{2}}\cdots p_{n}^{\beta _{n}}$，那么 GCD(a,b) = $p_{1}^{\gamma _{1}}p_{2}^{\gamma _{2}}\cdots p_{n}^{\gamma _{n}}$ 其中 $\gamma _{i}=Minimum(\alpha _{i},\beta _{i})$ 对于 i = 1 到 n。

例如，让我们看一下如何找到 5500 和 450 的最大公约数，它恰好是 50。首先，我们找到 5500 和 450 的质因数分解，即

5500=2² 5³ 11

450=2 3 ² 5²

注意，我们为数字 5500 和数字 450 得出的不同素数是 2、3、5 和 11。 现在，让我们用这些素数的适当幂来完全表示 5500 和 450。

5500=2² 5³ 11 = 2² 3⁰ 5³ 11¹

450=2 3² 5² = 2¹ 3² 5² 11⁰

GCD(5500,450) 将采用 2^? 3^? 5^? 11^? 的形式。我们现在要做的就是找到每个素数的幂是多少。

现在我们比较 5500 和 450 中每个素数的幂。让我们考虑第一个素数 2 的幂。在数字 5500 中，素数 2 被提升到第二幂，在数字 4</syntaxhighlight> 50 中，素数 2 被提升到第一幂。由于素数 2 的幂在 2 和 1 之间的最小值为 1，因此我们使用 1 作为素数 2 的幂。

现在让我们考虑素数 3 的幂。在数字 5500 中，素数 3 被提升到零次幂，在数字 450 中，素数 3 被提升到第二幂。由于素数 3 的幂在 0 和 2 之间的最小值为 0，因此我们使用 0 作为素数 3 的幂。

类似地，让我们考虑下一个素数 5 的幂。在数字 5500 中，素数 5 被提升到第三幂，在数字 450 中，素数 5 被提升到第二幂。由于素数 5 的幂在 3 和 2 之间的最小值为 2，因此我们使用 2 作为素数 5 的幂。

最后，让我们考虑素数 11 的幂，它是我们列表中的最后一个素数。在数字 5500 中，素数 11 被提升到第一幂，在数字 450 中，素数 11 被提升到零次幂。由于素数 11 的幂在 1 和 0 之间的最小值为 0，因此我们使用 0 作为最后一个素数 11 的幂。

因此，我们结果的乘积是 GCD(5500,450)=2¹ 3⁰ 5² 11⁰ = 50。

性质

• gcd(a,b)=gcd(b,a)
• gcd(a,b) = gcd(b,q)，其中 q 是 a 除以 b 的余数
• gcd(a/d, b/d)=1，其中 d 是 gcd(a,b)

欧几里得算法

欧几里得算法是一种可以让我们在不进行因式分解^*的情况下找到两个数字的 GCD 的算法。欧几里得算法只包含加法和乘法运算，并且以 GCD 的上述性质为基础。

^* 因式分解是一个“困难”的过程，也就是说，对一个数字进行因式分解需要很长时间，具体取决于数字的长度。这就是为什么以后，当您需要找到一对数字的 GCD 时，您很可能永远不会对数字进行因式分解并使用素数的性质，而是使用欧几里得算法。

一个例子

我们将通过计算 gcd(458,44) 来了解它是如何工作的

首先，用 44 除 458 并得到余数

458 = 44 × 10 + 18

现在假设一个数字是 458 和 44 的公约数。那么它也必须是 18 的约数。要看到这一点，将上面的方程重新排列为

458 - 44×10 =18

当这个方程被 44 和 458 的公约数除时，左侧得到一个整数，因此右侧也必须得到一个整数。根据定义，这意味着该数字也是 18 的约数。通过相同的推理，18 和 44 的任何公约数也是 458 的约数。由于 458 和 44 的所有公约数都等于 44 和 18 的公约数，因此，特别地，最大公约数是相等的。因此，我们有 gcd(458,44)=gcd(44,18)

该算法的下一步是将 44 除以 18 并找到余数。

44 = 18 × k + r

44 = 18 × 2 + 8

重复这个过程；不断用之前的余数除之前的除数

18 = 8 × 2 + 2

8 = 2 × 4 + 0

我们的最大公约数是零之前的最后一个余数，在本例中为 2。这是因为证明了 gcd(458,44)=gcd(44,18) 的推理适用于每一步，所以 gcd(458,44)=gcd(44,18)=gcd(18,8)=gcd(8,2)=gcd(2,0)=2。

矩阵方法

我们可以构造一个矩阵，提供一种计算最大公约数的替代方法。一般形式上，矩阵为

${\begin{bmatrix}1&0&b\\0&1&a\\\end{bmatrix}}$

回想一下，写出两个数的最大公约数的一种方法是作为整数线性组合。例如，如果我们正在寻找最大公约数，我们可以将其表示为as + bt，其中a 和b 是我们正在比较的两个数，而s 和t 是整数。我们也知道b = aq + r，其中r 是b 除以a 后的余数。在我们将第二行从第一行中减去后，我们得到

${\begin{bmatrix}1&-q_{1}&r_{1}\\0&1&a\\\end{bmatrix}}$

如果r_2 不为零，我们必须继续该过程；这次，从第二行中减去第一行。我们继续这个过程，直到其中一个r 被尽可能地减少。现在我们得到了最大公约数。在那行中，1 和 0 所在的位置的数字分别表示t 和s。

现在让我们来看一个计算示例。

${\begin{bmatrix}1&0&99\\0&1&7\\\end{bmatrix}}\rightsquigarrow {\begin{bmatrix}1&0&99\\0&14&98\\\end{bmatrix}}\rightsquigarrow {\begin{bmatrix}1&-14&1\\0&14&98\\\end{bmatrix}}$

我们可以看到，现在进一步操作是微不足道的；我们只会得到第二行，其中a 所在的位置为零。所以我们查看第一行并记住1 代表我们的余数，1(=t) 乘以b，-14(=s) 乘以a，使得

$1=99\times 1+-14\times 7$

这可以通过欧几里得算法进行检查，gcd(7,99)=1。

扩展欧几里得算法

如果我们尝试通过回代来逆转欧几里得算法的过程会发生什么？回代相当繁琐且容易出错，因此这里有一种更快的方法。

绘制一个包含四列的表格，从左到右依次标记为q、r、u、v。为了方便起见，标记一列i，表示我们当前所处的步骤。将a 和b（较大者位于上方）放在r 列中，并相应地放置 1 和 0

${\begin{matrix}i&q&r&u&v\\-1&.&b&0&1\\0&.&a&1&0\\\end{matrix}}$

现在通过取b/a 的商并将其放在q 列的下一个空间中，然后取b-aq 放在r 列中，向下迭代。

要更新u 和v，取

u_i = u_i-2-u_i-1q_i

v_i = v_i-2-v_i-1q_i

事实上，你正在寻找u 和v，使得 au + bv = gcd (a,b)。在某个时刻，gcd (a,b) 实际上是第 i 阶段的余数，所以你也可以计算 u_i 和 v_i，使得 au_i + bv_i = r_i，在每个阶段。

推导出上面发现的递推关系来自以下三个方程（第二个方程是欧几里得算法的基本性质，另外两个方程是我们为实现目标而设置的约束）

au_i-1 + bv_i-1 = r_i-1

r_i-2 = q_ir_i-1 + r_i

au_i + bv_i = r_i

诀窍是适当表示 r_i-2。

当你在r 列中获得 0 时停止写入。

然后找到 gcd(450,44)（这与 gcd(44,450) 相同）

${\begin{matrix}i&q&r&u&v\\-1&.&450&0&1\\0&.&44&1&0\\1&10&10&-10&1\\2&4&4&41&-4\\3&2&\mathbf {2} &-92&9\\4&2&0&-&-\\\end{matrix}}$

加粗的数字是最大公约数。观察 (9)×450+(-92)×44=2，显然这些u 和v 非常特殊。关于一般情况我们能说些什么呢？

贝祖等式

在上面的情况下，我们有 9×450+(-92)×44=gcd(450,44)。所以 450 和 44 的最大公约数可以写成 450 和 44 的线性组合，系数为整数。事实证明，这适用于任何一对整数。这个结果被称为“贝祖等式”，可以表述如下

对于任何一对非零整数a 和b，存在整数u 和v，使得

au+bv=gcd(a,b)

证明

如果 *a* 和 *b* 是任何一对整数，且不全是 0，那么显然存在整数 *u* 和 *v* 使得 *au*+ *bv* 为正数（只需将 *u* 和 *v* 的符号分别与 *a* 和 *b* 的符号匹配即可，例如），并且对于所有整数 *u* 和 *v*，*au*+ *bv* 也是一个整数（因为整数在加法和乘法下是封闭的）。因此，存在一个非空正整数集，其包含形式为 *au*+ *bv* 的数字；我们将其称为 S。由于 S 是一个非空的正整数集，它必须有一个最小元素（这就是所谓的 良序原理）。将此数字称为 *d*。断言是 $d=gcd(a,b)$。由于 *d* 属于 S，因此

(1)$d=ua+vb$

对于合适的 *u* 和 *v*。设 *n* 为 *a* 和 *b* 的任何正公约数。由于 *n* 整除 (1) 的右边，它也整除 d。因此 $d=qn$ 对于某些整数 $q\geq 1$。因此，*a* 和 *b* 的任何公约数都小于或等于 *d*。因此，如果 *d* 是 *a* 和 *b* 的公约数，那么它是最大的公约数。现在只剩下要证明 *d* 实际上是一个公约数。

为了证明这一点，我们将证明 S 中的任何元素都可以被 *d* 整除。这将证明 *d* 是 *a* 和 *b* 的公约数，因为 *a* 和 *b* 都是 S 的元素（因为 *a* = 1×a + 0×b 且 *b* = 0×a + 1×b）。设 *t* 为 S 中的任何元素。然后，根据除法算法

$t=qd+r$

对于某些 $0\leq r<d$。如果 *r* 不为 0，那么它就在 S 中。这是因为 *d* 和 *t* 都在 S 中，所以

$r=t-qd=(u_{1}a+v_{1}b)-q(u_{2}a+v_{2}b)=(u_{1}-qu_{2})a+(v_{1}-qv_{2})b=u'a+v'b$

但是，由于 $r<d$ 且 *d* 是 S 的最小元素，这是不可能的。唯一另一种可能性是 *r=0*。因此，S 中的任何元素 *t* 都可以被 *d* 整除。由于这包括 *a* 和 *b*，因此 *d* 是一个公约数。将此结果与先前的结果结合起来，就建立了贝祖等式。

*u* 和 *v* 的值可以使用表格方法或欧几里得算法中的回代法获得。

算术基本定理的证明

贝祖等式的一个应用是在证明算术基本定理时。在证明这一点之前，还需要另外两个结果：引理 1：如果一个素数 *p* 整除两个整数的乘积 $ab$，那么它必须整除 *a* 或 *b*（或两者）。

证明：如果 *p* 同时整除 *a* 和 *b*，则无需证明。假设 *p* 不整除 *a*。如果可以在该假设下证明 *p* 整除 *b*，则引理将被证明。

由于 *p* 不整除 *a*，因此 *gcd(a,p)*=1（因为 *p* 的唯一约数是 1 和 *p*，但 *p* 不是公约数）。因此，根据贝祖等式，存在整数 *u* 和 *v* 使得

$1=ua+vp$

将此方程乘以 *b* 可得

$b=uab+vbp$

*p* 整除右手边的两项，因此也整除左手边。因此，*p* 整除 *b*，如需证明的那样。

引理 2：如果一个素数 *p* 除以一个整数的乘积，$a_{1}a_{2}...a_{n}$，那么它一定至少除以其中一个因子。

证明：该证明是通过对因子数量 *n* 进行 归纳法。对于 n=2，该陈述根据引理 1 为真。假设该陈述对 *n=k* 为真，并考虑 *k* + 1 个因子的乘积。如果 *p* 除以多个因子，那么就没有什么需要证明的。假设 *p* 不除以任何因子 $a_{1},a_{2},...a_{k}$。将证明 *p* 必须除以 $a_{k+1}$。由于该陈述对 n=k 为真，那么由于 *p* 不除以 $a_{1}a_{2}...a_{k}$ 中的任何因子，它一定不除以该乘积（根据 逆否命题）。令 $a_{1}a_{2}...a_{k}=b$。那么 $a_{1}a_{2}...a_{k}a_{k+1}=ba_{k+1}$。然后，结论根据引理 1 得出。

算术基本定理：任何正整数 *n* 都可以表示为素数的乘积。该乘积除了项的顺序外是唯一的。

证明：该定理第一部分的证明是通过对 *n* 进行归纳法。如果 *n*=1，它是 0 个素数的乘积。假设所有小于 *n* 的正整数都可以表示为素数的乘积。如果 *n* 是素数，那么它是 1 个素数的乘积。假设 *n* 不是素数或 1。那么 $n=ab$，其中 *a* 和 *b* 是两个小于 *n* 的正整数。由于 *a* 和 *b* 都小于 *n*，根据归纳假设，它们可以写成素数的乘积。组合这些乘积可以得到 *n* 作为素数的乘积，如所要求的那样。

现在证明第二部分。假设 *n* 有两个素数分解，

$n=p_{1}p_{2}...p_{k}=q_{1}q_{2}...q_{s}$

$p_{1}$ 除以左侧，因此也必须除以右侧。根据引理 2，这意味着 $p_{1}$ 必须除以其中一个 $q_{i}$。但这些都是素数，所以 $p_{1}$ 能除以 $q_{i}$ 的唯一途径是，如果对于某个 *i*，有 $p_{1}=q_{i}$。在等式两边消去 $p_{1}$ 会形成另一个相同形式的等式。因此，可以同样证明，对于其他一些 *i*，$p_{2}=q_{i}$，以此类推，直到左侧的所有因子都被消去。在此之后，右侧一定没有任何剩余的因子，因为它必须等于 1。这证明了任何两个素数分解都包含相同的素数因子，正如要证明的那样。

划分乘积的除数

算术基本定理也可以从以下引理推导出来

引理： 给定整数 $a$，$b$ 和 $c$，如果 $c$ 整除 $ab$（记为 $c|ab$），则存在整数 $m$ 和 $n$ 使得 $c=mn$ 且 $m|a$ 和 $n|b$。

换句话说，整除一个乘积的整数本身可以分解成一个乘积，其中每个因子都整除来自 $ab$ 的对应因子。这意味着当 $a$ 和 $b$ 相乘时，不会产生新的素数。

该引理由算术基本定理和贝祖等式得出，但这里将给出更直接的证明。

证明：如果 $a$，$b$，或 $c$ 等于 $0$，则该引理是显然的。此外，如果 $a$，$b$，或 $c$ 为负数，则如果该引理对于绝对值 $|a|$，$|b|$，和 $|c|$ 成立，则很容易证明该引理对于 $a$，$b$，和 $c$ 也成立。现在假设 $a$，$b$，和 $c$ 都是严格的正整数。

形成一个包含 $a\times b$ 个元素的整数数组 $S$，它有 $a$ 列和 $b$ 行。 $s_{(x,y)}$ 将表示第 $x$ 列第 $y$ 行的整数。 通过按行扫描数组，从第 1 行开始，每行从第 1 列开始，依次对数组 $S$ 进行“光栅”扫描，使用以下循环模式来分配值给 $s_{(x,y)}$：$1,2,...,c$。实质上，$s_{(x,y)}$ 是来自范围 $\{1,2,\dots ,c\}$ 中唯一的整数，满足 $s_{(x,y)}\equiv x+a(y-1)\;\;({\text{mod}}\;c)$。由于 $c|ab$，因此 $s_{(1,1)}=1$ 且 $s_{(a,b)}=c$。

如前所述，数组 $S$ 的“光栅扫描”是 $S$ 中元素的循环遍历，其中列索引 $x$ 在 $1,2,...,a$ 中循环，每次 $x$ 从 $a$ 转变为 $1$ 时，行索引 $y$ 在循环 $1,2,...,b$ 中前进一步。

在下图中，网格 $S$，其中 $a=14$；$b=15$；和 $c=6$，被明确地和使用砖块图案来描绘。

数组 $S$ 可以无限复制并用来形成无限数组 $S_{\infty }$。对于任意整数 $u$ 和 $v$，$S_{\infty }$ 中由第 $a(u-1)+1$ 列到第 $a(u-1)+a$ 列，第 $(b(v-1)-(u-1))+1$ 行到第 $(b(v-1)-(u-1))+b$ 行的条目块是 $S$ 的副本。对于任意整数 $x$ 和 $y$，$S_{\infty }$ 中的条目 $s_{\infty ,(x,y)}$ 是范围 $\{1,2,\dots ,c\}$ 中唯一的整数，使得 $s_{\infty ,(x,y)}\equiv x+a(y-1)\;\;({\text{mod}}\;c)$。

数组 S 的表示图，其中 a = 14；b = 15；c = 6。(1,1) 条目是左下角。

用砖石图案表示的数组 S，其中 a = 14；b = 15；c = 6。每个“砖石”是序列 1、2、3、4、5、6。

表示 $S$ 的多个砖石图案可以拼接在一起，形成一个连续的墙，表示 $S_{\infty }$。

给定任意列 $x$ 和行 $y$，$S_{\infty }$ 中位于 $(x,y)$ 的元素 $s_{\infty ,(x,y)}$ 是 $\{1,2,...,c\}$ 中唯一的整数，使得 $s_{\infty ,(x,y)}\equiv x+a(y-1)\;\;({\text{mod}}\;c)$。给定任意位移列位移 $\Delta x$ 和行位移 $\Delta y$，差值 $s_{\infty ,(x+\Delta x,y+\Delta y)}-s_{\infty ,(x,y)}$ 与 $\Delta x+a\Delta y$ 之差为 $c$ 的倍数。这使得 $S_{\infty }$ 的元素具有以下对称性

• 给定列位移 $\Delta x$ 和列 $x_{1},x_{2}$，以及行位移 $\Delta y$ 和行 $y_{1},y_{2}$，则 $s_{\infty ,(x_{1}+\Delta x,y_{1}+\Delta y)}-s_{\infty ,(x_{1},y_{1})}\equiv s_{\infty ,(x_{2}+\Delta x,y_{2}+\Delta y)}-s_{\infty ,(x_{2},y_{2})}\;\;({\text{mod}}\;c)$。具体来说，如果 $s_{\infty ,(x_{1}+\Delta x,y_{1}+\Delta y)}-s_{\infty ,(x_{1},y_{1})}=0$，则 $s_{\infty ,(x_{2}+\Delta x,y_{2}+\Delta y)}-s_{\infty ,(x_{2},y_{2})}=0$，因为 $S_{\infty }$ 中任意两个元素之间的差值限制在集合 $\{-(c-1),-(c-2),...,-1,0,1,...,c-1\}$ 中。
• 给定列 $x_{1},x_{2}$，和行 $y_{1},y_{2}$，如果 $s_{\infty ,(x_{1},y_{1})}=s_{\infty ,(x_{2},y_{2})}$，那么将 $S_{\infty }$ 向右平移 $x_{2}-x_{1}$ 列和向下平移 $y_{2}-y_{1}$ 行不会改变 $S_{\infty }$ 的元素。

由于上述对称性，$S_{\infty }$ 中包含 $1$ 的列是等间距的。令 $m$ 表示最小的正整数，使得每隔 $m^{\text{th}}$ 列都包含 $1$。

• 元素 $s_{\infty ,(1,1)}=1$ 和 $s_{\infty ,(a+1,b)}=1$，因此必须有 $a$ 是周期 $m$ 的整数倍：$m|a$。
• 条目 $s_{\infty ,(1,1)}=1$ 和 $s_{\infty ,(c+1,1)}=1$，因此必须是 $c$ 是周期 $m$ 的整数倍数： $m|c$。

的 $S_{\infty }$ 行最终将重复（不允许任何列移动），周期为 $n$。由于 $S_{\infty }$ 的对称性，一行在一个周期内不会出现两次。第 $1$ 行与第 $b+1$ 行相同，因此必须是 $b$ 是周期 $n$ 的整数倍数： $n|b$。

当 a=14; b=15; 且 c=6 时，m=2 且 n=3。任何 2x3 细胞将包含所有 {1, 2, 3, 4, 5, 6}，从而实现所描述的拼贴。

现在将证明 $c=mn$，方法是展示 $S_{\infty }$ 的一个子块，该子块包含 $m$ 列和 $n$ 行，包含从 $\{1,2,...,c\}$ 中的每个整数恰好一次。

为了澄清符号，假设列索引为 $x_{1},x_{2}$，其中 $x_{1}\leq x_{2}$，而行索引为 $y_{1},y_{2}$，其中 $y_{1}\leq y_{2}$，则 $S_{\infty }([x_{1},x_{2}]\times [y_{1},y_{2}])$ 表示 $S_{\infty }$ 的子块，包含从列 $x_{1}$ 到 $x_{2}$ 的所有列，以及从行 $y_{1}$ 到 $y_{2}$ 的所有行。

由于一行可以从单个单元格唯一确定，并且行仅以 $n$ 为周期重复，任何块 $S_{\infty }([x,x]\times [y,y+(n-1)])$ 将包含恰好 $n$ 个唯一条目。

包含 $1$ 的列以周期为 $m$ 出现。由于 $S_{\infty }$ 的对称性，对于任何整数 $s\in \{1,2,...,c\}$，包含 $s$ 的列以周期为 $m$ 出现。任何块 $S_{\infty }([x,x+(m-1)]\times [y,y+(n-1)])$ 将正好包含 $mn$ 个唯一条目。

给定任何整数 $s\in \{1,2,...,c\}$，整数 $s$ 将出现在每一 $m^{\text{th}}$ 列，并在该列中，出现在每一 $n^{\text{th}}$ 个单元格。任何块 $S_{\infty }([x,x+(m-1)]\times [y,y+(n-1)])$ 将包含 $s$。任何块 $S_{\infty }([x,x+(m-1)]\times [y,y+(n-1)])$ 将包含从 $\{1,2,...,c\}$ 中的每个整数正好一次。所以，因此 $c=mn$。 $\Box$.

解线性模方程 - 回到贝祖定理

上面的贝祖恒等式为我们提供了求解以下形式方程的关键

ax ≡ b (mod m)

互质的情况 - gcd(a, m) 为 1

考虑以下情况

ax ≡ b (mod m)

但 gcd(a, m)=1

由于贝祖恒等式

1 = au+mv

当我们计算u时，这个数字很特别。

假设我们有以下方程

4x=11 (mod 21)

4 和 21 互质，因为 gcd(4,21)=1。现在 1=4*16+(-3)*(21)。在这种情况下，我们的u 是 16。现在观察 4*16=64。64 (mod 21) = 1。这个数字u 非常特殊 - 它被称为乘法逆。它是u，在与a 相乘后得到 1 mod m。在计算 gcd(a, m) 时，贝祖恒等式将始终给出a 模m 的乘法逆。a 的乘法逆通常写为a^-1，但请注意，这并不表示 1/a，因为我们在第一节中已经看到，我们不能总是在整数中进行除法。

请注意，在 Z_p 中，有一个数字没有乘法逆 - 0。在考虑模运算时，排除 0 可能很有用，因此，为了避免总是说 Z_p\{0}，我们只需写 Z_p^*。

现在，由于我们有了神奇的乘法逆，我们的问题就变得相对容易解决了。在 Z₂₁ 中，4^-1=16，现在，在整个方程两边乘以 16

x = 11 × 16 (mod 21)

（因为 4×16=1，因为 16 是 4 模 21 的乘法逆）。11×16=176，使用计算器或使用除法定理，我们得到

x = 8 (mod 21)

这就是我们的解！验证 - 8×4 = 32 = 11 (mod 21)。

一般情况

考虑以下一般情况

ax ≡ b (mod m)

对a、b 和m 没有限制。

首先，我们再次计算 gcd(a, m) 以得到d。现在d 是一个除数，因为 gcd 中的d 表示最大公约数。所以我们现在可以除a 和m - 但b 呢？由于我们计算了a 和m 的 gcd，但没有计算b，因此我们不能保证d 能整除b。这就会成为方程没有解的条件。

现在我们已经将问题简化为之前互质的情况，因为 gcd(a/d, m/d)=1，其中d 如上所示。但是我们不再只有一个解了 - 这是因为我们已经将解简化为x = c (mod m/d)，并且我们必须将解还原为 mod m。这在示例中会更加清楚。

让我们来看一些示例。

示例 1. 求解 4x ≡ 3 (mod 20)。首先，gcd(4, 20) = 4。4 不能整除 3，因此没有解。

示例 2. 求解 9x ≡ 6 (mod 15)。gcd(9, 15) = 3，并且 3 能整除 6，因此有 3 个解。

现在，将整个方程除以 3，得到

3x ≡ 2 (mod 5)

gcd(3, 5) = 1 = 3 × 2 + -1 × 5 因此 3 模 5 的逆是 2。现在我们得到解

x ≡ 4 (mod 5)

现在在 Z₁₅ 中，我们必须得到另外两个解 9 和 14 模 15 - 9 模 5 = 4，并且 14 模 5 = 4。

通常，我们可以说，如果我们得到了约简方程的解x，则一般解为x+(m/d)k，其中k={0, 1, .., d-1}。

中国剩余定理

通常需要同时满足多个同余关系。给定正整数底数 $m_{1}$ 和 $m_{2}$ 以及任意整数 $a$ 和 $b$，其中 $0\leq a<m_{1}$ 且 $0\leq b<m_{2}$，一个常见的问题是哪些整数 $x$ 同时满足以下同余关系：

$\left\{{\begin{array}{c}x\equiv a\;\;({\text{mod}}\;m_{1})\\x\equiv b\;\;({\text{mod}}\;m_{2})\end{array}}\right.$

中国剩余定理指出，当 ${\text{gcd}}(m_{1},m_{2})=1$ 时，对于任何 $a\in \mathbb {Z} _{m_{1}}=\{0,1,...,m_{1}-1\}$ 和 $b\in \mathbb {Z} _{m_{2}}=\{0,1,...,m_{2}-1\}$ 的选择，存在唯一的整数 $c\in \mathbb {Z} _{m_{1}m_{2}}=\{0,1,...,m_{1}m_{2}-1\}$ 使得

同时满足 $\left\{{\begin{array}{c}x\equiv a\;\;({\text{mod}}\;m_{1})\\x\equiv b\;\;({\text{mod}}\;m_{2})\end{array}}\right.$ 的所有整数 $x$ 是那些同时满足 $x\equiv c\;\;({\text{mod}}\;m_{1}m_{2})$ 的整数。

实质上，当 $m_{1}$ 和 $m_{2}$ 互质时，$\mathbb {Z} _{m_{1}}\times \mathbb {Z} _{m_{2}}$ 中的有序对与集合 $\mathbb {Z} _{m_{1}m_{2}}$ 之间存在一一对应关系。

证明 1

证明： 首先观察到 $|\mathbb {Z} _{m_{1}m_{2}}|=m_{1}m_{2}$ 且 $|\mathbb {Z} _{m_{1}}\times \mathbb {Z} _{m_{2}}|=|\mathbb {Z} _{m_{1}}||\mathbb {Z} _{m_{2}}|=m_{1}m_{2}$，因此可以将每个 $c\in \mathbb {Z} _{m_{1}m_{2}}$ 与一个唯一的有序对 $\langle a,b\rangle \in \mathbb {Z} _{m_{1}}\times \mathbb {Z} _{m_{2}}$ 配对，反之亦然。

给定任意$c\in \mathbb {Z} _{m_{1}m_{2}}$，整数$c$ 可以被 $m_{1}$ 取模，得到一个整数$a\in \mathbb {Z} _{m_{1}}$，也可以被$b$ 取模，得到一个整数$b\in \mathbb {Z} _{m_{2}}$。整数$a$ 和$b$ 满足：$\forall x\in \mathbb {Z} :(x\equiv c\;\;({\text{mod}}\;m_{1}m_{2}))\implies ((x\equiv a\;\;({\text{mod}}\;m_{1}))\;{\text{and}}\;(x\equiv b\;\;({\text{mod}}\;m_{2})))$

对于任意$\langle a,b\rangle \in \mathbb {Z} _{m_{1}}\times \mathbb {Z} _{m_{2}}$ 的选择，是否存在唯一的$c\in \mathbb {Z} _{m_{1}m_{2}}$ 使得$\forall x\in \mathbb {Z} :((x\equiv a\;\;({\text{mod}}\;m_{1}))\;{\text{and}}\;(x\equiv b\;\;({\text{mod}}\;m_{2})))\iff (x\equiv c\;\;({\text{mod}}\;m_{1}m_{2}))$，这一点并不明显。

令 $S$ 表示一个无限数组，它有两行，由 $y=1,2$ 索引，以及无限列，由 $x\in \mathbb {Z}$ 索引。 $s_{(x,y)}$ 将表示 $S$ 中第 $x$ 列和第 $y$ 行的条目。 $s_{(x,y)}$ 是从 $\mathbb {Z} _{y}=\{0,1,...,m_{y}-1\}$ 中唯一的整数，其中 $s_{(x,y)}\equiv x\;\;({\text{mod}}\;m_{y})$。

数组 $S$ 其中 $m_{1}=6$ 且 $m_{2}=5$。列 $x=0$ 到 $x=29$ 如图所示。

给定列索引 $x_{1},x_{2}$，其中 $x_{1}\leq x_{2}$，则 $S_{1}[x_{1},x_{2}];S_{2}[x_{1},x_{2}];S_{1,2}[x_{1},x_{2}]$ 将分别表示由列 $x_{1}$ 到 $x_{2}$ 和行集 $\{1\};\{2\};\{1,2\}$ 形成的子块。

将 $S$ 分成一系列 $m_{1}\times 2$ 块 $...,S_{1,2}[-2m_{1},-m_{1}-1],S_{1,2}[-m_{1},-1],S_{1,2}[0,m_{1}-1],S_{1,2}[m_{1},2m_{1}-1],S_{1,2}[2m_{1},3m_{1}-1],...$，其中块 $k\in \mathbb {Z}$ 是 $S_{1,2}[km_{1},(k+1)m_{1}-1]$。

块 $k$ 的第 1 行始终为序列 $0,1,...,m_{1}-1$。块 $k$ 的第 2 行可以由其第一个元素 $s_{(km_{1},2)}$ 唯一确定，因为 $s_{(km_{1}+r,2)}\equiv s_{(km_{1},2)}+r\;\;({\text{mod}}\;m_{2})$。这些块仅在第 2 行不同，而每个块的第 2 行由其第一个元素 $s_{(km_{1},2)}$ 唯一确定。

$s_{(km_{1},2)}\equiv km_{1}\;\;({\text{mod}}\;m_{2})$ 且 $s_{((k+1)m_{1},2)}\equiv (k+1)m_{1}\;\;({\text{mod}}\;m_{2})$，因此 $s_{((k+1)m_{1},2)}\equiv s_{(km_{1},2)}+m_{1}\;\;({\text{mod}}\;m_{2})$。这意味着下一个块的第 2 行的第一个元素可以从当前块的第 2 行的第一个元素唯一确定。

Since each block is uniquely determined from the previous block, the row 2 pattern for each block will repeat after a regular period of $p$ blocks: $S_{1,2}[km_{1},(k+1)m_{1}-1]=S_{1,2}[(k+p)m_{1},(k+p+1)m_{1}-1]$. Let set $U\subseteq \mathbb {Z} _{m_{2}}$ denote the total range of values attained by $s_{(km_{1},2)}$. It is the case that $p=|U|$. Let $d$ be the minimum positive difference between any two elements from $U$. The cyclical nature of the elements from $U$ makes it easy to show that any element $t\in U$ is congruent to a multiple of $d$ modulo $m_{2}$. In essence: $U=\{t|t\in \mathbb {Z} _{m_{2}}\;{\text{and}}\;\exists u\in \mathbb {Z} :t\equiv ud\;\;({\text{mod}}\;m_{2})\}$. Since $d$ is the minimum positive difference between any two elements of $U$, both $m_{1}$ and $m_{2}$ are multiples of $d$ (in fact, $m_{2}=pd$). Since ${\text{gcd}}(m_{1},m_{2})=1$, it must be the case that $d=1$. This implies that $U=\mathbb {Z} _{m_{2}}$ and that $p=m_{2}$. A total of $m_{2}$ blocks are encountered before any repetition occurs in array $S$, and therefore all $m_{1}m_{2}$ possible columns occur exactly once in a column period of $m_{1}m_{2}$ in array $S$. This establishes the Chinese Remainder Theorem. $\Box$

证明 2

可以通过构建网格来描述空间 $\mathbb {Z} _{m_{1}}\times \mathbb {Z} _{m_{2}}$，从而得到另一个（更直观的）证明。该网格是一个矩形点阵，有 $m_{1}$ 列和 $m_{2}$ 行。列从左到右按 $0,1,2,...,m_{1}-1$ 索引，行从下到上按 $0,1,2,...,m_{2}-1$ 索引。最重要的是，网格将在水平和垂直方向上“环绕”。这意味着从列 $m_{1}-1$ 向右移动将返回到列 $0$；从列 $0$ 向左移动将把你送到列 $m_{1}-1$；从行 $m_{2}-1$ 向上移动将返回到行 $0$；从行 $0$ 向下移动将把你送到行 $m_{2}-1$。

The mesh has $m_{1}m_{2}$ points, and the horizontal and vertical coordinates of each point are the remainders from dividing an integer $x$ by $m_{1}$ and $m_{2}$ respectively. For convenience, given an arbitrary dividend $x$, $x\;{\text{mod}}\;m_{1}$ and $x\;{\text{mod}}\;m_{2}$ will denote the remainders after $x$ is divided by $m_{1}$ and $m_{2}$ respectively. If the dividend $x$ is incremented by $1$, then the coordinate formed by the remainders moves to the right by one step, and up by one step, wrapping around if necessary. $x=0$ corresponds to the coordinate $(0,0)$. Increasing $x$ in steps of $1$ will trace a ray that originates from $(0,0)$ and moves one step to the right and one step up each interation, wrapping around if necessary. The images below give examples of this ray for $m_{1}=6;m_{2}=5$ and for $m_{1}=6;m_{2}=4$. In the images below, a copy of column 0 and row 0 appears at the right and top of the mesh respectively to illustrate the wrap around property. When $m_{1}=6;m_{2}=4$, $m_{1}$ and $m_{2}$ are not coprime and fail to satisfy the conditions of the Chinese remainder theorem.

展示了一个水平方向每 6 步环绕，垂直方向每 5 步环绕的网格。该网格描述了分别除以 6 和 5 后得到的余数对的集合。网格外部的数字表示水平和垂直坐标，即分别除以 6 和 5 后的余数。从 (0,0) 开始，发出一条射线（用红线表示），它在水平和垂直方向上重复向前移动 1 步。该射线表示随着被除数以 1 步递增，余数对的序列。每个红色条带上的数字索引射线的每次环绕。射线穿过网格上的每个点，表明任何余数对都是可能的，这与中国剩余定理的预测一致。

展示了一个水平方向每 6 步环绕，垂直方向每 4 步环绕的网格。该网格描述了分别除以 6 和 4 后得到的余数对的集合。网格外部的数字表示水平和垂直坐标，即分别除以 6 和 4 后的余数。从 (0,0) 开始，发出一条射线（用红线表示），它在水平和垂直方向上重复向前移动 1 步。该射线表示随着被除数以 1 步递增，余数对的序列。每个红色条带上的数字索引射线的每次环绕。射线未能穿过网格上的每个点，因为 6 和 4 不是互质的。这与中国剩余定理相一致。

射线在网格中形成对角线“条纹”，如果这些条纹都等距地由$1$间隔，那么射线会精确地穿过网格中的每个点一次，证明每对余数都是可能的，因此中国剩余定理成立。当$m_{1}=6;m_{2}=4$时，$m_{1}$ 和 $m_{2}$ 不是互质的，并且不满足中国剩余定理的条件，因此射线不会击中网格上的每个点。网格的环绕性质使得网格在水平和垂直方向上都“对称”，这意味着如果将环绕的“接缝”移动到射线穿过左下角的任何列和行，则射线将完全保持不变。这要求条纹等距。令$d$表示这种等距，并且将证明$d|m_{1}$ 和 $d|m_{2}$。射线每向右移动$d$步就会穿过第$0$行。射线穿过$(0,0)$，并且环绕性质意味着向右移动$m_{1}$步会返回到这个相同的交点。这只能在$d|m_{1}$时发生。用类似的论证可得$d|m_{2}$。如果$m_{1}$ 和 $m_{2}$ 是互质的，那么 $d=1$，条纹等距地由$1$间隔，每对余数都是可能的，因此中国剩余定理成立。 $\Box$