高中数学扩展
补充章节 — 质数与模算术 — 逻辑
数学证明 — 集合论与无限过程 — 计数与生成函数 — 离散概率
矩阵 — 模算术扩展 — 数学规划 — 马尔可夫链
HSME
内容
质数
模算术
问题与项目
习题集
项目
解答
习题解答
问题集解答
其他
定义表
完整版本
PDF 版本
引言
质数（简称质数）是一个自然数，它只有两个因数：它本身和数字 1。由于 1 只有一个因数——它本身——我们不认为它是一个质数，而是一个单位。因此，2 是第一个质数，3 是下一个质数，但 4 不是质数，因为 4 除以 2 等于 2 且没有余数。我们已经证明了 4 有三个因数：1、2 和 4。具有两个以上因数的数字称为合数。
前 20 个质数是 2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67 和 71。
质数是数学家们永远无法抗拒的魅力源泉。一些关于质数的问题非常困难，即使一些最杰出的数学家们花费数十年的时间也无法解决。其中一个问题是哥德巴赫猜想，它指出所有大于 3 的偶数都可以表示为两个质数的和。没有人能够证明它是真还是假。
本章将介绍质数的一些基本性质及其与称为模运算的数学领域之间的联系。
质数的几何意义
最上面的前三个图形展示了将 12 块方形地砖组装成矩形的不同方法。最下面的三个图形表明 7 不能被 2（左图）或 3（右图）完全整除。
如果给定 12 块方形地砖，我们是否可以以不止一种方式将它们组装成矩形形状？当然可以，这是因为
12 = 12 × 1 = 6 × 2 = 4 × 3 {\displaystyle {\begin{matrix}12&=&12\times 1\\&=&6\times 2\\&=&4\times 3\\\end{matrix}}}
我们不区分 2×6 和 6×2，因为它们本质上是等效的排列。
但是数字 7 呢？你能以不止一种方式将 7 块方形地砖排列成矩形形状吗？答案是否定的，因为 7 是一个质数。
算术基本定理
定理 是一个非凡的数学事实。定理必须经过证明；一个普遍认为是正确的命题，但没有证明，被称为猜想 或假设。
有了这些定义，算术基本定理 只是指出
任何自然数（除 1 外）都可以用一种且只有一种方式表示为质数的乘积。
例如
12 = 2 × 2 × 3 {\displaystyle 12=2\times 2\times 3\,\!}
重新排列乘法顺序不视为数字的不同表示，因此没有其他方式将 12 表示为质数的乘积。
再举几个例子
99 = 3 × 3 × 11 52 = 2 × 2 × 13 17 = 17 {\displaystyle {\begin{matrix}99&=&3&\times &3&\times &11\\52&=&2&\times &2&\times &13\\17&=&17&\end{matrix}}}
可以很容易地看出，合数具有多个质因数（多次计算重复的质因数）。
为什么？
记住算术基本定理的定义，为什么数字 1 不被认为是质数？
因式分解
我们从算术基本定理中知道，任何整数都可以表示为质数的乘积。一百万美金的问题是：给定一个数字 *x*，是否有 *简单* 的方法找到 *x* 的所有质因数？
如果 *x* 是一个小的数字，那么很简单。例如，90 = 2 × 3 × 3 × 5。但是如果 *x* 很大呢？例如 *x = 4539*？大多数人无法在脑中将 4539 分解成质数。但是计算机可以做到吗？可以，计算机可以相当快地将 4539 分解成质数。我们有 4539 = 3 × 17 × 89。
由于计算机非常擅长算术运算，我们可以通过简单地指示计算机依次将 *x* 除以 2、然后 3、然后 5、然后 7...等等来计算出 *x* 的所有因数。
因此，存在一种 *简单* 的方法将数字分解成质因数。只需应用上面描述的方法即可。但是，这种方法对于大数来说太慢了：尝试将一个拥有数千位数字的数字分解成质因数将花费比当前宇宙年龄更长的时间。但是，有没有一种 *快速* 的方法？或者更确切地说，有没有一种 *高效* 的方法？可能存在，但还没有人找到。当今一些最广泛使用的加密方案（如 RSA）利用了我们无法快速将大数分解成质因数的事实。如果找到了这样的方法，许多互联网交易将变得不安全。
考虑以下三个正在进行的除法方法的示例。
示例 1
x = 21 {\displaystyle x=21}
x 2 = 10.5 {\displaystyle {\frac {x}{2}}=10.5} 不是整数，因此 2 不是 21 的因数
x 3 = 7 {\displaystyle {\frac {x}{3}}=7} 因此 3 和 7 是 21 的因数。
示例 2
x = 153 {\displaystyle x=153}
x 2 = 76.5 {\displaystyle {\frac {x}{2}}=76.5} 因此 2 不是 153 的因数
x 3 = 51 {\displaystyle {\frac {x}{3}}=51} 因此 3 和 51 是 153 的因数。
51 3 = 17 {\displaystyle {\frac {51}{3}}=17} 因此 3 和 17 是 153 的因数。
很明显，3、9、17 和 51 是 153 的因数。153 的质因数是 3、3 和 17 (3×3×17 = 153)
示例 3
2057 2 = 1028.5 {\displaystyle {\frac {2057}{2}}=1028.5}
⋯ {\displaystyle \cdots }
2057 11 = 187 {\displaystyle {\frac {2057}{11}}=187}
187 11 = 17 {\displaystyle {\frac {187}{11}}=17}
因此 11、11 和 17 是 2057 的质因数。
练习
对下面给定的数字进行因式分解
1
13=
2
26=
3
59=
4
82=
5
101=
6
121=
7 如果时间太长，就放弃。有一个快速的方法。
2187=
有趣的事实 - 这是质数吗？
有趣的是，借助计算机，有一种有效的方法可以以 100% 的准确性确定一个数字是否是质数。
2、5 和 3
质数 2、5 和 3 在因式分解中占有特殊的地位。首先，所有偶数都有 2 作为它们的质因数之一。其次，所有最后一位数字是 0 或 5 的数字都可以被 5 整除。
第三种情况，3 是质因数，是本节的重点。根本问题是：是否有简单的方法来判断一个数字是否具有 3 作为其质因数之一？
定理 - 可被 3 整除
一个数字可被 3 整除当且仅当其各位数字之和可被 3 整除。
例如，272 不可被 3 整除，因为 2 + 7 + 2 = 11，不可被 3 整除。
945 可被 3 整除，因为 9 + 4 + 5 = 18。而 18 可被 3 整除。实际上，945 / 3 = 315
123456789 可被 3 整除吗？
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = (1 + 9) × 9 / 2 = 45
4 + 5 = 9
九可被 3 整除，因此 45 可被 3 整除，因此 123456789 可被 3 整除！
该定理的妙处在于其递归性。一个数字可被 3 整除当且仅当其各位数字之和可被 3 整除。我们怎么知道其各位数字之和是否可被 3 整除？再次应用该定理！
信息 - 递归
一位著名的计算机科学家曾经说过“迭代是人的行为，递归是神来之笔”。但这递归是什么意思？在此之前，迭代是什么？“迭代”仅仅意味着一遍又一遍地做同样的事情，而计算机非常擅长这一点。数学中的迭代示例是指数运算，例如 xn 意味着 x 乘以 x 乘以 x 乘以 x...n 次。这是一个迭代的示例。
经济地（就心理资源而言）思考迭代，通过用自身来定义一个问题，就是“递归”。为了递归地表示 xn，我们写
x n = 1 {\displaystyle x^{n}=1} 如果n 等于 0。
x n = x × x n − 1 {\displaystyle x^{n}=x\times x^{n-1}} 如果n > 0
99 是多少？它是 9 乘以 9 8。但是，98 是 9 乘以 97。以这种方式重复是递归的示例。
练习
对于问题 1-3，进行因式分解
1
45=
2
4050=
3
2187=
4 证明可被 3 整除定理适用于任何三位数。
（在纸上做）
5 一个数字可被 9 整除当且仅当其各位数字之和可被 9 整除。
对
错
确定问题 6-9 中的数字是否可被 9 整除。
6
89
是
否
7
558
是
否
8
51858
是
否
9
41857
是
否
寻找质数
质数筛是一种相对有效的方法，用于寻找所有小于或等于指定数字的质数。要找到所有小于或等于 50 的质数，我们执行以下操作
首先，我们将数字 1 到 50 写在一个表中，如下所示
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 {\displaystyle {\begin{matrix}1&2&3&4&5&6&7&8&9&10\\11&12&13&14&15&16&17&18&19&20\\21&22&23&24&25&26&27&28&29&30\\31&32&33&34&35&36&37&38&39&40\\41&42&43&44&45&46&47&48&49&50\\\end{matrix}}}
划掉 1，因为它不是质数。
X 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 {\displaystyle {\begin{matrix}X&2&3&4&5&6&7&8&9&10\\11&12&13&14&15&16&17&18&19&20\\21&22&23&24&25&26&27&28&29&30\\31&32&33&34&35&36&37&38&39&40\\41&42&43&44&45&46&47&48&49&50\\\end{matrix}}}
现在 2 是表格中未划去的最小数字。我们标记 2 为素数，并划去所有 2 的倍数，即 4、6、8、10 ...
X 2 p 3 X 5 X 7 X 9 X 11 X 13 X 15 X 17 X 19 X 21 X 23 X 25 X 27 X 29 X 31 X 33 X 35 X 37 X 39 X 41 X 43 X 45 X 47 X 49 X {\displaystyle {\begin{matrix}X&2_{p}&3&X&5&X&7&X&9&X\\11&X&13&X&15&X&17&X&19&X\\21&X&23&X&25&X&27&X&29&X\\31&X&33&X&35&X&37&X&39&X\\41&X&43&X&45&X&47&X&49&X\\\end{matrix}}}
现在 3 是表格中未标记的最小数字。我们标记 3 为素数，并划去所有 3 的倍数，即 6、9、12、15 ...
X 2 p 3 p X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X 25 X X X 29 X 31 X X X 35 X 37 X X X 41 X 43 X X X 47 X 49 X {\displaystyle {\begin{matrix}X&2_{p}&3_{p}&X&5&X&7&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&25&X&X&X&29&X\\31&X&X&X&35&X&37&X&X&X\\41&X&43&X&X&X&47&X&49&X\\\end{matrix}}}
继续以这种方式找出所有素数。你什么时候知道已经找到了 50 以下的所有素数？请注意，此算法称为埃拉托斯特尼筛法
练习
X 2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X X X X X 29 X 31 X X X X X 37 X X X 41 X 43 X X X 47 X X X {\displaystyle {\begin{matrix}X&2&3&X&5&X&7&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&X&X&X&X&29&X\\31&X&X&X&X&X&37&X&X&X\\41&X&43&X&X&X&47&X&X&X\\\end{matrix}}} 素数筛法已应用于上面的表格。请注意，2 和 5 下方所有数字都被划掉了。构造一个从 1 到 60 的数字矩形网格，以便在对其执行素数筛法后，2 和 5 下方所有数字都被划掉。网格的宽度是多少？
找出 200 以下的所有素数。
找出 200 以下能被 3 整除的数字。你改变了网格的宽度了吗？
无限多个素数
要回答什么是最大的质数？这个问题，让我们先回答什么是最大的自然数？如果有人告诉你 10 10 {\displaystyle 10^{10}} 是最大的自然数，你可以立即反驳他们，告诉他们 10 10 + 1 {\displaystyle 10^{10}+1} 是一个更大的自然数。你可以用任何其他自然数 n {\displaystyle n} 替换 10 10 {\displaystyle 10^{10}} ，你的论据仍然有效。这意味着不存在所谓的最大的自然数。（你们中的一些人可能会想说无穷大是最大的自然数。但是，无穷大不是自然数，而只是一个数学概念。）
古希腊数学家欧几里得对质数的无限性进行了以下证明。
质数无限性的证明
让我们先假设
质数的数量是有限的
因此
一定存在一个比所有其他质数都大的质数，
让我们将这个质数称为n。现在，我们将证明上面提到的两个假设会导致矛盾，因此存在无限多个质数。
将所有质数相乘，得到一个数x。因此
x = 2 × 3 × 5 × … × n {\displaystyle x=2\times 3\times 5\times \ldots \times n\!}
然后，令y等于x加1
y = x + 1 {\displaystyle y=x+1\!}
现在我们可以得出结论，y不能被任何小于等于n的质数整除，因为y比每个这样的质数的倍数正好大1。由于y不能被任何质数整除，因此y要么是质数，要么它的质因数都大于n，这与最初假设n是最大质数相矛盾！因此，我们必须宣布最初的假设是错误的，并且存在无限多个质数。
有趣的事实——已知最大的质数
已知的最大质数是282,589,933-1。它有高达24,862,048位数！形如2n-1的质数被称为梅森素数，以法国僧侣/业余数学家命名。
有用的外部资源
"The Prime Pages. Prime Number Research, Records, and Resources"
模运算
引言
模运算与质数之间存在有趣的联系。
模运算是一种系统，其中使用所有小于某个正整数n的数字。因此，如果你要开始计数，你会从0、1、2、3、...、n-1开始，但不是计数n，而是从0重新开始。而本来是n+1的数字现在是1，本来是n+2的数字现在是2。当到达2n时，数字将重置为0，以此类推。模运算也被称为时钟运算，因为我们只使用12个数字来表示标准时间。在时钟上，我们从1而不是0开始，一直到12，然后从1重新开始。因此得名时钟运算。
该序列还延伸到本来应该是负数的部分。本来应该是-1的数字现在是n-1。例如，考虑模7运算，它与普通算术非常相似，只是我们使用的数字只有0、1、2、3、4、5和6。如果我们看到一个不在这个范围内的数字，我们会加7（或减7），直到它落在那个范围内。
如上所述，模运算与普通算术并没有太大区别。例如，在模7运算中，我们有
3 + 2 = 5 {\displaystyle 3+2=5\!}
5 + 6 = 11 = 4 {\displaystyle 5+6=11=4\!}
5 − 6 = − 1 = 6 {\displaystyle 5-6=-1=6\!}
以及
3 × 5 = 15 = 1 5 × − 6 = − 30 = 5 {\displaystyle {\begin{matrix}3\times 5=15=1\\5\times -6=-30=5\\\end{matrix}}}
我们进行了一些负数的运算。考虑5 × -6。由于-6不在0到6的范围内，我们需要向它加7，直到它落在范围内。而-6 + 7 = 1。因此，在模7运算中，-6 = 1。在上面的例子中，我们证明了5 × -6 = -30 = 5，但是5 × 1 = 5。因此，我们使用-6而不是1并没有造成任何损失。为什么？
注意——负数：-3的首选表示形式是4，因为-3 + 7 = 4，但是在计算中使用-3和4都会得到相同的答案，只要我们将最终的答案转换为0到6（含）之间的数字即可。
练习
在模11运算中找到
1.
-1 × -5
2.
3 × 7
3. 计算2的前10次方
21, 22, 23, ... , 210
你注意到什么了？使用2的幂找到
61, 62, 63, ... , 610
你又注意到什么了？
4.
4 {\displaystyle {\sqrt {4}}}
即通过试错法（或其他方法）找到所有满足x2 = 4 (mod 11)的数字x。有两个解，找到它们。
5.
9 {\displaystyle {\sqrt {9}}}
即找到所有满足x2 = 9 (mod 11)的数字x。有两个解，找到它们。
逆元
考虑一个数字n，n的逆元是与n相乘得到1的数字。例如，如果我们要解以下方程
5 x = 3 ( mod 7 ) {\displaystyle 5x=3{\pmod {7}}\!}
使用 (mod 7) 是为了明确我们正在进行模7运算。我们希望以某种方式消除5。用一个数乘它，把它变成1，就可以完成这个任务。请注意
3 × 5 = 15 = 1 ( mod 7 ) {\displaystyle 3\times 5=15=1{\pmod {7}}\!}
因为 3 乘以 5 等于 1，我们说 3 是 5 在模 7 运算中的逆元。现在我们将两边都乘以 3
3 × 5 {\displaystyle 3\times 5\!}
x {\displaystyle x\!}
= 3 × 3 ( mod 7 ) {\displaystyle =3\times 3{\pmod {7}}\!}
x {\displaystyle x\!}
= 9 ( mod 7 ) {\displaystyle =9{\pmod {7}}\!}
= 2 ( mod 7 ) {\displaystyle =2{\pmod {7}}\!}
所以，x = 2 模 7 是要求的解。
定义 (逆元)
(一个数) x 的逆元是一个数 y，使得 xy = 1。我们用 x-1 或 1/x 表示 x 的逆元。
逆元是唯一的
从上面我们可以知道 5 的逆元是 3，但 5 是否还有其他逆元呢？答案是否定的。事实上，在任何合理的数字系统中，一个数只能有一个逆元。我们可以从以下证明中看出这一点
假设 n 有两个逆元 b 和 c
b = b × 1 = b ( n c ) = ( b n ) c = 1 × c = c {\displaystyle b=b\times 1=b(nc)=(bn)c=1\times c=c\!}
从上面的论证可以看出，n 的所有逆元都必须相等。因此，如果数字 n 有逆元，则该逆元一定是唯一的。
任何模 n 运算的一个有趣的性质是数字 n - 1 具有其自身作为逆元。也就是说，(n - 1) × (n - 1) = 1 (mod n)，或者我们可以写成 (n - 1)2 = (-1)2 = 1 (mod n)。证明留作本节末尾的习题。
逆元的存
并非所有数字在所有模运算中都有逆元。例如，3 在模 6 运算中没有逆元，即我们找不到一个数字 x，使得 3x = 1 模 6（读者可以很容易地验证这一点）。
考虑模 15 运算，并注意 15 是合数。我们知道 1 的逆元是 1，14 的逆元是 14。但 3、6、9、12、5 和 10 呢？他们都没有逆元！注意，他们中的每一个都与 15 有公因数！
例如，我们证明 3 在模 15 运算中没有逆元。假设 3 有逆元 x，那么我们有
3 x = 1 ( mod 15 ) {\displaystyle 3x=1{\pmod {15}}\!}
我们将从模运算跳到有理数运算。如果 3x = 1 在模 15 运算中成立，那么
3 x = 15 k + 1 {\displaystyle 3x=15k+1\!}
对于某个整数 k。现在我们将两边都除以 3，得到
x = 5 k + 1 3 {\displaystyle x=5k+{\frac {1}{3}}\!}
但这不可能成立，因为我们知道 x 是一个整数，而不是分数。因此，3 在模 15 运算中没有逆元。要证明 10 没有逆元更难，留作习题。
我们现在将说明关于模运算中逆元存在的定理。
定理
如果 n 是素数，那么每个数字（除 0 之外）在模 n 运算中都有逆元。
类似地
如果 n 是合数，那么每个与 n 没有公因数的数字都有逆元。
有趣的是，除法 与逆元的概念密切相关。考虑以下表达式
6 × 3 − 1 ( mod 7 ) {\displaystyle 6\times 3^{-1}{\pmod {7}}\!}
计算上述表达式的传统方法是找到 3 的逆元（即 5）。所以
6 × 3 − 1 = 6 × 5 = 30 = 2 ( mod 7 ) {\displaystyle 6\times 3^{-1}=6\times 5=30=2{\pmod {7}}\!}
我们将 3 的逆元写成 1/3，所以我们将乘以 3-1 视为除以 3，得到
6 × 1 3 = 6 3 = 2 ( mod 7 ) {\displaystyle 6\times {\frac {1}{3}}={\frac {6}{3}}=2{\pmod {7}}\!}
注意，我们得到了相同的答案！事实上，如果存在逆，除法方法总是有效的。
然而，在不同的模系统中，表达式会产生错误的答案，例如
6 × 3 − 1 ( mod 9 ) {\displaystyle 6\times 3^{-1}{\pmod {9}}\!}
我们没有得到 2，因为 3-1 在模 9 中不存在，所以我们不能使用除法方法。
练习
1. 8 在模 16 运算中是否有逆？如果没有，为什么？
2. 如果存在 x，求 x 模 7
x = 2 − 1 {\displaystyle x=2^{-1}\!}
x = 3 − 1 {\displaystyle x=3^{-1}\!}
x = 4 − 1 {\displaystyle x=4^{-1}\!}
x = 5 − 1 {\displaystyle x=5^{-1}\!}
x = 6 − 1 {\displaystyle x=6^{-1}\!}
x = 7 − 1 {\displaystyle x=7^{-1}\!}
3. 用两种方法计算 x，求逆 和 除法
x = 28 ⋅ 7 − 1 (mod 29) {\displaystyle x=28\cdot 7^{-1}\ \ {\mbox{(mod 29)}}\!}
4. (技巧) 求 x
x = 5 99 × ( 40 + 3 − 1 ) ( mod 11 ) {\displaystyle x=5^{99}\times (40+3^{-1})\ {\pmod {11}}\!}
5. 求所有模 n 的逆 (n ≤ 19)
互质和最大公约数
如果两个数的最大公约数 (gcd) 为 1，则称这两个数互质。例如，21 和 55 都是合数，但它们互质，因为它们的最大公约数是 1。换句话说，它们除了 1 之外没有其他共同的约数。
有一个快速而优雅的方法可以计算两个数的 gcd，称为欧几里得算法。让我们通过几个例子来说明
示例 1
求 21 和 49 的 gcd。
我们建立一个两列的表格，其中较大的数字放在右边，如下所示
较小 较大
21 49
现在我们计算 49 (mod 21)，即 7，并将它放在第二行的 较小 列中，并将 21 放入 较大 列中。
较小 较大
21 49
7 21
对第二行执行相同的操作以生成第三行。
较小 较大
21 49
7 21
0 7
每当我们在 较小 列中看到数字 0 时，我们就知道对应的 较大 数字是我们开始使用的两个数字的 gcd，即 7 是 21 和 49 的 gcd。这个 算法 称为欧几里得算法。
示例 2
求 31 和 101 的 gcd
较小 较大
31 101
8 31
7 8
1 7
0 1
示例 3
求 132 和 200 的 gcd
较小 较大
132 200
68 132
64 68
4 64
0 4
重要提示
gcd 不一定是质数。
两个不同质数的 gcd 为 1。换句话说，两个不同质数总是互质。
练习
1. 判断以下数字集是否互质
5050 5051
59 78
111 369
2021 4032
2. 求数字 15、510 和 375 的 gcd
info -- 算法
算法是对一系列动作的逐步描述，当正确执行时，可以完成一项任务。存在用于查找质数、判断两个数字是否互质、查找逆以及许多其他目的的算法。您将在 [[../../../Mathematical Programming/]] 章中学习如何使用计算机实现我们已经见过的某些算法。
查找逆
让我们从另一个角度来看逆的概念。事实上，我们将提供一种万无一失的方法来找到任何数字的逆。让我们考虑
5x = 1 (mod 7)
我们知道 x 是 5 的逆，我们可以很快地算出它是 3。但 x = 10 也是一个解，x = 17 也是，还有 x = 24、31、... 7n + 3。因此有无穷多个解；因此我们说 3 等价于 10、17、24、31 等。这是一个至关重要的观察结果。
现在让我们考虑
216 x ≡ 1 (mod 811) {\displaystyle 216x\equiv 1\ \ {\mbox{(mod 811)}}}
这里引入了一种新的符号，它是带三个划线的等号而不是两个。它是“等价”符号；上面的语句应该读作“216x 等价于 1”而不是“216x 等于 1”。从现在开始，我们将使用等价符号来表示模运算，而使用等号来表示普通运算。
回到这个例子，我们知道x 存在，因为 gcd(811,216) = 1。上面问题的问题在于没有快速的方法来确定x的值！我们知道最好的方法是将 216 乘以 1、2、3、4…… 直到我们得到答案，最多需要 811 次计算，对于人类来说太繁琐了。但是有一个更好的方法，我们已经讨论过很多次了！
我们注意到，我们可以像以前一样“跳跃”到有理数学中。
216 a = 1 + 811 b 0 ≡ 1 + 163 b ( mod 216 ) {\displaystyle {\begin{matrix}216a&=&1+811b\\0&\equiv &1+163b&{\pmod {216}}\\\end{matrix}}}
我们再次跳入有理数学。
216 c = 1 + 163 b 53 c ≡ 1 ( mod 163 ) {\displaystyle {\begin{matrix}216c&=&1+163b\\53c&\equiv &1&{\pmod {163}}\\\end{matrix}}}
我们再跳一次。
53 c = 1 + 163 d 0 ≡ 1 + 4 d ( mod 53 ) {\displaystyle {\begin{matrix}53c&=&1+163d\\0&\equiv &1+4d&{\pmod {53}}\\\end{matrix}}}
现在模式很明显，我们应该从头开始，这样过程就不会被打断。
216 a = 1 + 811 b 216 c = 1 + 163 b 53 c = 1 + 163 d 53 e = 1 + 4 d e = 1 + 4 f {\displaystyle {\begin{matrix}216a&=&1+811b\\216c&=&1+163b\\53c&=&1+163d\\53e&=&1+4d\\e&=&1+4f\\\end{matrix}}}
现在我们所要做的就是选择f的值，然后代入回去找到a！记住，a 是 216 模 811 的逆。我们选择 f = 0，因此 e = 1，d = 13，c = 40，b = 53，最后 a = 199！如果选择f为 1，我们将得到a的不同值。
非常敏锐的读者应该已经注意到，这只是欧几里得算法的逆运算。
以下是一些关于这种巧妙方法应用的例子。
示例 1
求a的最小正值。
33 a ≡ 1 (mod 101) 33 a = 1 + 101 b 33 c = 1 + 2 b c = 1 + 2 d {\displaystyle {\begin{matrix}33a&\equiv &1\ \ {\mbox{(mod 101)}}\\33a&=&1+101b\\33c&=&1+2b\\c&=&1+2d\\\end{matrix}}}
选择 d = 0，因此 a = 49。
示例 2 求a的最小正值。
27 a ≡ 1 (mod 821) 27 a = 1 + 821 b 27 c = 1 + 11 b 5 c = 1 + 11 d 5 e = 1 + d {\displaystyle {\begin{matrix}27a&\equiv &1\ \ {\mbox{(mod 821)}}\\27a&=&1+821b\\27c&=&1+11b\\5c&=&1+11d\\5e&=&1+d\\\end{matrix}}}
选择 e = 0，因此 a = -152 = 669。
示例 3 求a的最小正值。
34 a ≡ 1 (mod 55) 34 a = 1 + 55 b 34 c = 1 + 21 b 13 c = 1 + 21 d 13 e = 1 + 8 d 5 e = 1 + 8 f 5 g = 1 + 3 f 2 g = 1 + 3 h 2 i = 1 + h {\displaystyle {\begin{matrix}34a&\equiv &1\ \ {\mbox{(mod 55)}}\\34a&=&1+55b\\34c&=&1+21b\\13c&=&1+21d\\13e&=&1+8d\\5e&=&1+8f\\5g&=&1+3f\\2g&=&1+3h\\2i&=&1+h\\\end{matrix}}}
设置 i = 0，然后 a = -21 = 34。为什么对于两个如此小的数字，它会如此缓慢？ 你对系数有什么看法？
示例 4 求a的最小正值。
21 a ≡ 1 (mod 102) 21 a = 1 + 102 b 21 c = 1 + 18 b 3 c = 1 + 18 d 3 d = 1 {\displaystyle {\begin{matrix}21a&\equiv &1\ \ {\mbox{(mod 102)}}\\21a&=&1+102b\\21c&=&1+18b\\3c&=&1+18d\\3d&=&1\\\end{matrix}}}
现在 *d* 不是整数，因此 21 在模 102 下没有逆元。
我们到目前为止讨论的是如何求解以下形式的方程的整数解
ax + by = 1
其中 *x* 和 *y* 是未知数，*a* 和 *b* 是两个给定的常数，这些方程称为线性 *丢番图方程*。值得注意的是，有时没有解，但如果存在解，则意味着存在无穷多解。
丢番图方程
在 模运算 部分，我们陈述了一个定理，该定理指出，如果 gcd( *a*, *m* ) = 1，则 *a*-1（*a* 的逆元）存在于模 *m* 中。不难看出，如果 *p* 是素数，则对于所有小于 *p* 的 *b*，gcd( *b*, *p* ) = 1，因此我们可以说在模 *p* 中，除了 0 之外的每个数字都有逆元。
我们还展示了一种找到任何元素模 *p* 的逆元的方法。事实上，在模运算中找到一个数字的逆元等同于求解一种称为丢番图方程的方程。丢番图方程是以下形式的方程
*ax* + *by* = *d*
其中 *x* 和 *y* 是未知数。
例如，我们应该尝试在模 811 下找到 216 的逆元。设 216 的逆元为 *x*，我们可以写成
216 x ≡ 1 ( mod 811 ) {\displaystyle 216x\equiv 1{\pmod {811}}\!}
我们可以用日常算术重新写上面的内容
216 x + 811 y = 1 {\displaystyle 216x+811y=1\!}
它是一个丢番图方程的形式。
现在我们要用不优雅的方法来解决以上问题，然后用优雅的方法（使用神奇表）。
以上两种方法都使用欧几里德算法来求解两个数的 gcd。事实上，gcd 与逆元的概念密切相关。让我们对 216 和 811 两个数字应用欧几里德算法。然而，这次，我们应该存储更多细节；更具体地说，我们想设置一个名为 PQ 的附加列，它代表偏商。偏商只是一个专业术语，表示“多少个 *n* 可以除以 *m*”例如，3 和 19 的偏商是 6，4 和 21 的偏商是 5，最后一个例子是 7 和 49 的偏商是 7。
较小 较大 PQ
216 811 3
163
表格表示三个 216 可以除以 811，余数为 163，或者用符号表示
811 = 3×216 + 163。
让我们继续
较小 较大 PQ
216 811 3
163 216 1
53 163 3
4 53 13
1 4 4
0 1
从表格中读出，我们可以形成以下表达式
811 = 3× 216 + 163
216 = 1× 163 + 53
163 = 3× 53 + 4
53 =13× 4 + 1
现在我们可以通过反向操作结果来计算出 216 的逆元
1 = 53 - 13×4
1 = 53 - 13×(163 - 3×53)
1 = 40×53 - 13×163
1 = 40×(216 - 163) - 13×163
1 = 40×216 - 53×163
1 = 40×216 - 53×(811 - 3×216)
1 = 199×216 - 53×811
现在看看模 811 的方程，我们会看到 216 的逆元是 199。
神奇表
神奇表是一种更优雅的方式来完成上述计算，让我们使用从欧几里德算法中得到的表格
较小 较大 PQ
216 811 3
163 216 1
53 163 3
4 53 13
1 4 4
0 1
现在我们建立所谓的“神奇表”，它最初看起来像这样
0 1
1 0
现在我们在第一行写下偏商
3 1 3 13 4
0 1
1 0
我们根据以下规则生成表格
将一个偏商乘以它左边一个空格的另一行的数字，将乘积加到同一行左边两个空格的数字上，并将总和放在相应的行中。
听起来比实际操作要复杂。让我们通过生成一列来进行说明
3 1 3 13 4
0 1 3
1 0 1
我们在第二行放一个 3，因为 3 = 3×1 + 0。我们在第三行放一个 1，因为 1 = 3×0 + 1。
现在我们将不间断地生成整个表格
3 1 3 13 4
0 1 3 4 15 199 811
1 0 11453216
我们可以检查
|199×216 - 811×53| = 1
事实上，如果神奇表构建得正确，并且我们对最后两列进行了 *交叉相乘和相减*，那么我们总能得到 1 或 -1，前提是我们开始的两个数字是互质的。神奇表只是更简洁地进行数学运算的一种方式。
练习
1. 找到最小的正 *x*
216 x ≡ 1 (mod 816) {\displaystyle 216x\equiv 1\ \ {\mbox{(mod 816)}}}
2. 找到最小的正 *x*
42 x ≡ 7 (mod 217) {\displaystyle 42x\equiv 7\ \ {\mbox{(mod 217)}}}
3.
(a) 生成 33 *a* = 1 (mod 101) 的神奇表
(b) 计算并用 p/q 的形式表示
3 + 1 16 + 1 2 {\displaystyle 3+{1 \over 16+{1 \over 2}}}
你注意到什么了？
4.
(a) 生成 17a = 1 (mod 317) 的神奇表
(b) 计算并用 p/q 的形式表示
18 + 1 1 + 1 1 + 1 1 + 1 5 {\displaystyle 18+{1 \over 1+{1 \over {1+{1 \over 1+{1 \over 5}}}}}}
你注意到什么了？
中国剩余定理
中国剩余定理在中国被称为 *韩信点兵*，最直白的翻译是 *韩信数兵*。最初的问题是这样的
存在一个数字 *x*，被 3 除余 2，被 5 除余 3，被 7 除余 2。求最小的 *x*。
我们将问题转换成符号形式
x ≡ 2 ( mod 3 ) x ≡ 3 ( mod 5 ) x ≡ 2 ( mod 7 ) {\displaystyle {\begin{matrix}x&\equiv &2{\pmod {3}}\\x&\equiv &3{\pmod {5}}\\x&\equiv &2{\pmod {7}}\\\end{matrix}}}
如何找到这样的x？ 我们将使用一种熟悉的方法，最好用例子说明
看x = 2 (mod 3)，我们进入普通数学的“跳跃”
x ≡ 2 ( mod 3 ) x = 2 + 3 a ( 1 ) {\displaystyle {\begin{matrix}x&\equiv &2{\pmod {3}}\\x&=&2+3a\qquad (1)\end{matrix}}}
现在我们看看模 5 的方程
2 + {\displaystyle 2+\!}
3 a {\displaystyle 3a\!}
≡ 3 ( mod 5 ) {\displaystyle \equiv 3{\pmod {5}}\!}
3 a {\displaystyle 3a\!}
≡ 1 ( mod 5 ) {\displaystyle \equiv 1{\pmod {5}}\!}
a {\displaystyle a\!}
≡ 2 ( mod 5 ) {\displaystyle \equiv 2{\pmod {5}}\!}
a {\displaystyle a\!}
= 2 + 5 b {\displaystyle =2+5b\!}
代入 (1) 得到以下结果
x {\displaystyle x\!}
= 2 + 3 ( 2 + 5 b ) {\displaystyle =2+3(2+5b)\!}
= 8 + 15 b {\displaystyle =8+15b\!}
现在看看上面模 7
x = 8 + 15 b ≡ 2 ( mod 7 ) {\displaystyle x=8+15b\equiv 2{\pmod {7}}\!}
我们得到
b ≡ 1 ( mod 7 ) {\displaystyle b\equiv 1{\pmod {7}}\!}
我们选择b = 1 以最小化x，因此x = 23。 简单的检查（由读者执行）应确认x = 23 是一个解。 一个值得问的问题是，满足这三个同余式的下一个最小的x是什么？ 答案是x = 128，下一个是233，再下一个是338，它们相差105，即3、5和7的乘积。
我们将通过以下示例进一步说明求解同余方程组的方法
示例 1 找到满足以下条件的最小的x
x ≡ 1 ( mod 3 ) {\displaystyle x\equiv 1{\pmod {3}}\!}
x ≡ 2 ( mod 5 ) {\displaystyle x\equiv 2{\pmod {5}}\!}
x ≡ 3 ( mod 7 ) {\displaystyle x\equiv 3{\pmod {7}}\!}
解法
x = {\displaystyle x=\!}
1 + 3 {\displaystyle 1+3\!}
a {\displaystyle a\!}
≡ {\displaystyle \equiv \!}
2 ( mod 5 ) {\displaystyle 2{\pmod {5}}\!}
a {\displaystyle a\!}
= {\displaystyle =\!}
2 + 5 b {\displaystyle 2+5b\!}
现在将结果代回第一个方程，我们得到
x {\displaystyle x\!}
= 1 + 3 ( 2 + 5 b ) {\displaystyle =1+3(2+5b)\!}
= 7 + 15 b {\displaystyle =7+15b\!}
≡ 3 ( mod 7 ) {\displaystyle \equiv 3{\pmod {7}}\!}
我们得到
b ≡ 3 ( mod 7 ) {\displaystyle b\equiv 3{\pmod {7}}\!}
b = 3 + 7 c {\displaystyle b=3+7c\!}
再次代回
x {\displaystyle x\!}
= 7 + 15 ( 3 + 7 c ) {\displaystyle =7+15(3+7c)\!}
= 52 + 15 × 7 c {\displaystyle =52+15\times 7c\!}
因此 52 是满足同余式的最小 x。
示例 2
找出满足以下同余式的最小 x
x ≡ 5 ( mod 11 ) {\displaystyle x\equiv 5{\pmod {11}}\!}
x ≡ 3 ( mod 7 ) {\displaystyle x\equiv 3{\pmod {7}}\!}
x ≡ 8 ( mod 9 ) {\displaystyle x\equiv 8{\pmod {9}}\!}
解法
x {\displaystyle x\!}
= 5 + 11 {\displaystyle =5+11\!}
a ≡ 3 ( mod 7 ) {\displaystyle a\equiv 3{\pmod {7}}\!}
a ≡ 3 ( mod 7 ) {\displaystyle a\equiv 3{\pmod {7}}\!}
a = 3 + 7 b {\displaystyle a=3+7b\!}
代回
x = {\displaystyle x=\!}
5 + 11 ( 3 + 7 b ) {\displaystyle 5+11(3+7b)\!}
= {\displaystyle =\!}
38 + 11 × 7 b {\displaystyle 38+11\times 7b\!}
≡ {\displaystyle \equiv \!}
8 ( mod 9 ) {\displaystyle 8{\pmod {9}}\!}
现在求解b
2 + 2 × 7 b {\displaystyle 2+2\times 7b\!}
≡ 8 ( mod 9 ) {\displaystyle \equiv 8{\pmod {9}}\!}
b {\displaystyle b\!}
≡ 3 ( mod 9 ) {\displaystyle \equiv 3{\pmod {9}}\!}
b {\displaystyle b\!}
= 3 + 9 c {\displaystyle =3+9c\!}
再次代入
x {\displaystyle x\!}
= {\displaystyle =\!}
38 + 11 × 7 ( 3 + 9 c ) {\displaystyle 38+11\times 7(3+9c)\!}
= {\displaystyle =\!}
269 + 11 × 7 × 9 c {\displaystyle 269+11\times 7\times 9c\!}
因此 269 是满足同余式的最小 x。
练习
1. 求解 x
3 x ≡ 5 ( mod 14 ) 2 x ≡ − 3 ( mod 17 ) x ≡ 6 ( mod 15 ) {\displaystyle {\begin{matrix}3x&\equiv &5{\pmod {14}}\\2x&\equiv &-3{\pmod {17}}\\x&\equiv &6{\pmod {15}}\\\end{matrix}}}
2. 求解 x
3 x ≡ 5 ( mod 19 ) 7 x ≡ − 3 ( mod 17 ) x ≡ 6 ( mod 11 ) {\displaystyle {\begin{matrix}3x&\equiv &5{\pmod {19}}\\7x&\equiv &-3{\pmod {17}}\\x&\equiv &6{\pmod {11}}\\\end{matrix}}}
*解的存在性*
上面的练习都有解。那么是否存在一个同余方程组，使得找不到解？当然有可能，考虑
x ≡ 5 (mod 15)
x ≡ 10 (mod 21)
一个更巧妙的例子是
x ≡ 1 (mod 2)
x ≡ 0 (mod 2)
但我们不会考虑这种愚蠢的例子。
回到第一个例子，我们可以尝试通过以下方法求解
x = 5 + 15 k ≡ 10 ( mod 21 ) 15 k ≡ 5 3 k ≡ 1 {\displaystyle {\begin{matrix}x&=&5+15k&\equiv &10&{\pmod {21}}\\&&15k&\equiv &5&\\&&3k&\equiv &1&\\\end{matrix}}}
上述方程无解，因为 3 在模 21 下没有逆元！
人们可能很快得出结论，如果两个模系统有公因子，则没有解。但这并不正确！考虑
x ≡ 4 ( mod 15 ) {\displaystyle x\equiv 4{\pmod {15}}\!}
x ≡ 7 ( mod 21 ) {\displaystyle x\equiv 7{\pmod {21}}\!}
我们可以找到一个解
x = {\displaystyle x=\!}
4 + 15 k {\displaystyle 4+15k\!}
≡ 7 ( mod 21 ) {\displaystyle \equiv 7{\pmod {21}}\!}
15 k {\displaystyle 15k\!}
≡ 3 ( mod 21 ) {\displaystyle \equiv 3{\pmod {21}}\!}
5 × 3 k {\displaystyle 5\times 3k\!}
≡ 3 ( mod 21 ) {\displaystyle \equiv 3{\pmod {21}}\!}
现在我们将两边乘以 5 的逆元（即 17），得到
3 k ≡ 9 {\displaystyle 3k\equiv 9\!}
显然，k = 3 是一个解，这两个模系统与第一个例子相同（即 15 和 21）。
那么，是什么决定了同余方程组是否有解呢？让我们考虑一般情况
x ≡ a ( mod m ) {\displaystyle x\equiv a{\pmod {m}}\!}
x ≡ b ( mod n ) {\displaystyle x\equiv b{\pmod {n}}\!}
我们有
x = a + k m {\displaystyle x=a+km\!}
x = b + l n {\displaystyle x=b+ln\!}
本质上，问题要求我们找到k 和 l，使得上述方程成立。
我们可以如下解决这个问题
0 = ( a − b ) + ( k m − l n ) {\displaystyle 0=(a-b)+(km-ln)\,\!}
( l n − k m ) = ( a − b ) {\displaystyle (ln-km)=(a-b)\,\!}
现在假设 m 和 n 有 gcd(m,n) = d，并且 m = dmo, n = dno。我们有
d l n o − d k m o = ( a − b ) {\displaystyle dln_{o}-dkm_{o}=(a-b)\,\!}
l n o − k m o = ( a − b ) / d {\displaystyle ln_{o}-km_{o}=(a-b)/d\,\!}
如果 (a - b)/d 是一个整数，那么我们可以读出模 mo 下的方程，得到
l n o ≡ ( a − b ) / d ( mod m o ) {\displaystyle ln_{o}\equiv (a-b)/d{\pmod {m_{o}}}\,\!}
再次强调，上述公式只有在 (a - b)/d 为整数时才有意义。此外，如果 (a - b)/d 是一个整数，那么就存在一个解，因为 mo 和 no 是互质的！
概括来说，对于一个包含两个同余方程的系统
x ≡ a ( mod m ) {\displaystyle x\equiv a{\pmod {m}}\,\!}
x ≡ b ( mod n ) {\displaystyle x\equiv b{\pmod {n}}\,\!}
存在解当且仅当
d = gcd(m,n) 能整除 (a - b)
上述结论可以很好地推广到多个同余方程。对于一个包含 n 个同余方程的系统
x ≡ a 1 ( mod m 1 ) {\displaystyle x\equiv a_{1}{\pmod {m_{1}}}\,\!}
x ≡ a 2 ( mod m 2 ) {\displaystyle x\equiv a_{2}{\pmod {m_{2}}}\,\!}
...
x ≡ a n ( mod m n ) {\displaystyle x\equiv a_{n}{\pmod {m_{n}}}\,\!}
要使存在解，我们需要满足当 i ≠ j 时
gcd(mi,mj) 能整除 (ai - aj)
练习
判断以下每个同余方程组是否存在解。解释原因。
1.
x ≡ 7 (mod 25)
x ≡ 22 (mod 45)
2.
x ≡ 7 (mod 23)
x ≡ 3 (mod 11)
x ≡ 3 (mod 13)
3.
x ≡ 7 (mod 25)
x ≡ 22 (mod 45)
x ≡ 7 (mod 11)
4.
x ≡ 4 (mod 28)
x ≡ 28 (mod 52)
x ≡ 24 (mod 32)
进一步学习
本章是对 数论 的一个简要介绍，数论是数学中一个非常美丽的分支。这里只是轻微地介绍了数论，数学方面比较浅显，总体上比较容易理解。如果你喜欢本章的内容，你也会喜欢 进一步的模运算，这是一个更难更严谨的主题处理方式。
此外，如果你想挑战自己，可以试试我们为你准备的 习题集。另一方面，项目 要求你采用更具探索性的方法来研究中国剩余定理的一些更深层的含义。
致谢
致谢：本教材的这一章在很大程度上借鉴了悉尼大学数学系名誉副教授 Terry Gagen 的灵感和他在“数论与代数”方面的讲义。Terry 是学生们非常喜欢的一位人物，以他风趣的教学风格而闻名。
参考资料
1. 已知最大素数总结
反馈
你觉得怎么样？ 太简单还是太难？ 信息太多还是不够？ 我们如何改进？ 请在讨论标签中留言告诉我们。更好的方法是自己编辑它，把它做得更好。
高中数学扩展
补充章节 — 质数与模算术 — 逻辑
数学证明 — 集合论与无限过程 — 计数与生成函数 — 离散概率
矩阵 — 模算术扩展 — 数学规划 — 马尔可夫链