离散数学/数论

介绍

'数论'本身就是一个庞大而全面的学科。在这里，我们将考察数论的关键概念。

与处理实数稠密集的实分析和微积分不同，数论考察了离散集中的数学，例如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 的元素。

我们可以通过使用除数定理找到 a 模 n（或者说 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)$.

进制

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

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

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

也有大于 10 的进制。对于这些进制，通常使用字母来表示大于 10 的数字。例如，十六进制 (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 是素数，因为唯一能被 17 整除的正整数是 1 和 17。数字 6 不是素数，因为除了 1、2、3、6 以外，还有其他除数能被 6 整除。另外，请注意，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 中的任何一个数字整除。考虑一下如果你尝试用 p₁、p₂、...、p_n 列表中的任何素数来除 M 会发生什么。从 M 的定义中，你可以知道你会得到余数 1。这意味着 p——能够整除 M 的素数——必须大于 p₁、...、p_n 中的任何一个。

因此，我们已经证明 M 可以被一个素数 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 的幂是 1，而在数字 450 中，质因数 11 的幂是 0。由于质因数 11 的幂 1 和 0 中的最大值为 1，我们使用 1 作为最后一个质因数 11 的幂。

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

GCD

两个数字 a 和 b 的最大公约数是能同时整除数字 a 和数字 b 的最大数字，用 GCD(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)

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

44 = 18 × k + r

44 = 18 × 2 + 8

重复此过程；不断用前一个余数除以前一个除数

18 = 8 × 2 + 2

8 = 2 × 4 + 0

我们的 gcd 是最后一个余数，在零之前，在本例中为 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}$中的任何因子，因此p不能整除该乘积（根据逆否命题）。令$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$，对于一些小于n的正整数a和b。由于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}$ 的唯一方法是当 $p_{1}=q_{i}$ 对于某些 i 成立。将方程两边的 $p_{1}$ 消去，得到另一个相同形式的方程。因此，同样可以证明 $p_{2}=q_{i}$ 对于其他 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 非常特殊 - 它被称为乘法逆元。它是乘以a 后得到模m 为 1 的数字u。计算 gcd(a, m) 的贝祖恒等式总是会给你a 模m 的乘法逆元。a 的乘法逆元通常写成a^-1，但请注意这不代表 1/a，因为我们在第一部分已经看到，我们不能总是在整数中进行除法。

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

现在，由于我们有了神奇的乘法逆元，我们的问题就变得相对容易解决了。4^-1=16 在Z₂₁ 中，现在，在整个等式两边乘以 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)，我们必须将解还原为模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$ 的第一行始终是序列 $0,1,...,m_{1}-1$。块 $k$ 的第二行可以通过其第一个元素 $s_{(km_{1},2)}$ 唯一确定，因为 $s_{(km_{1}+r,2)}\equiv s_{(km_{1},2)}+r\;\;({\text{mod}}\;m_{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})$。这意味着下一个块的第二行的第一个元素可以由当前块的第二行的第一个元素唯一确定。

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$