高中数学扩展/素数/模算术/文本

模算术

介绍

模算术与素数以一种有趣的方式联系在一起。

模算术是一个系统，其中所有小于某个正整数（例如，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\!$

$5+6=11=4\!$

$5-6=-1=6\!$

以及

${\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 之间的数字（包括 0 和 6）。

练习

在模 11 中求

1.

-1 × -5

2.

3 × 7

3. 计算 2 的前 10 次方

2¹, 2², 2³, ... , 2¹⁰

你发现了什么？
使用 2 的幂求

6¹, 6², 6³, ... , 6¹⁰

你再次发现了什么？

4.

${\sqrt {4}}$

即，通过试错（或其他方法）找到所有满足 x² = 4 (mod 11) 的数字 x。有两个解，找到它们。

5.

${\sqrt {9}}$

即，找到所有满足 x² = 9 (mod 11) 的数字 x。有两个解，找到它们。

逆元

考虑一个数字 n，n 的逆元是指与 n 相乘得到 1 的数字。例如，如果我们要解以下方程

$5x=3{\pmod {7}}\!$

(mod 7) 用于明确我们进行的是模 7 算术。我们要想办法消除 5。将它乘以某个东西使其变为 1 可以解决问题。请注意，

$3\times 5=15=1{\pmod {7}}\!$

因为 3 乘以 5 等于 1，所以我们说 3 是 5 在模 7 中的逆元。现在我们将等式两边都乘以 3

$3\times 5\!$	$x\!$	$=3\times 3{\pmod {7}}\!$
	$x\!$	$=9{\pmod {7}}\!$
		$=2{\pmod {7}}\!$

因此，x = 2 模 7 是所需的解。

定义（逆）

（一个数）x 的逆是另一个数y，使得xy = 1。我们用x^-1 或 1/x 表示x 的逆。

逆是唯一的

从上面我们知道 5 的逆是 3，但是 5 是否还有其他的逆？答案是否定的。实际上，在任何合理的数字系统中，一个数字只能有一个逆。我们可以从下面的证明中看到这一点

假设n 有两个逆b 和c

$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)² = (-1)² = 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，那么我们有

$3x=1{\pmod {15}}\!$

我们将从模运算跳跃到有理数运算。如果 3x = 1 在模 15 运算中，那么

$3x=15k+1\!$

对于某个整数k。现在我们将两边都除以 3，得到

$x=5k+{\frac {1}{3}}\!$

但这不可能，因为我们知道x 是一个整数，而不是分数。因此，3 在模 15 运算中没有逆。要证明 10 没有逆更难，留作练习。

我们现在将陈述关于模运算中逆存在的定理。

定理

如果n 是素数，则每个数字（除了 0）在模n 运算中都有逆。

类似地

如果n 是合数，则每个与n 没有公因数的数字都有逆。

有趣的是，除法 与逆的概念密切相关。考虑以下表达式

$6\times 3^{-1}{\pmod {7}}\!$

计算上述表达式的常规方法是找到 3 的逆（是 5）。所以

$6\times 3^{-1}=6\times 5=30=2{\pmod {7}}\!$

我们将 3 的逆写成 1/3，所以我们将乘以 3^-1 看作除以 3，得到

$6\times {\frac {1}{3}}={\frac {6}{3}}=2{\pmod {7}}\!$

注意，我们得到了相同的答案！实际上，如果逆存在，除法方法将始终有效。

然而，在不同的模系统中的表达式将产生错误的答案，例如

$6\times 3^{-1}{\pmod {9}}\!$

我们不会得到 2，因为 3^-1 在模 9 运算中不存在，所以我们不能使用除法方法。

练习

1. 8 在模 16 运算中是否有逆元？如果没有，为什么？

2. 如果 x 存在，求 x 模 7。

$x=2^{-1}\!$

$x=3^{-1}\!$

$x=4^{-1}\!$

$x=5^{-1}\!$

$x=6^{-1}\!$

$x=7^{-1}\!$

3. 用两种方法计算 x，分别是 求逆元 和 除法

$x=28\cdot 7^{-1}\ \ {\mbox{(mod 29)}}\!$

4. （技巧）求 x

$x=5^{99}\times (40+3^{-1})\ {\pmod {11}}\!$

5. 求所有模 n 的逆元（n ≤ 19）

互质和最大公约数

如果两个数的最大公约数 (gcd) 为 1，则称这两个数互质。例如，21 和 55 都是合数，但它们互质，因为它们的最大公约数为 1。换句话说，它们除了 1 之外没有其他公约数。

有一个快速巧妙的方法来计算两个数的最大公约数，称为欧几里得算法。让我们用几个例子来说明。

示例 1

求 21 和 49 的最大公约数。

我们建立一个两列表，其中两个数中较大的数在右侧，如下所示。

较小数	较大数
21	49

现在我们计算 49 模 21 的结果，即 7，并将它放在第二行 较小数 列中，并将 21 放入 较大数 列中。

较小数	较大数
21	49
7	21

对第二行执行相同的操作，生成第三行。

较小数	较大数
21	49
7	21
0	7

只要我们看到 较小数 列中出现数字 0，我们就知道相应的 较大数 是我们开始的两个数的最大公约数，即 7 是 21 和 49 的最大公约数。这个 算法 称为欧几里得算法。

示例 2

求 31 和 101 的最大公约数。

较小数	较大数
31	101
8	31
7	8
1	7
0	1

示例 3

求 132 和 200 的最大公约数。

较小数	较大数
132	200
68	132
64	68
4	64
0	4

重要说明

1. 最大公约数不一定是素数。
2. 两个不同素数的最大公约数为 1。换句话说，两个不同的素数总是互质的。

练习

1. 判断以下数字集合是否互质

1. 5050 5051
2. 59 78
3. 111 369
4. 2021 4032

2. 求 15、510 和 375 的最大公约数

信息 -- 算法

算法是对一系列操作的逐步描述，当正确执行时，可以完成一项任务。有用于寻找素数、判断两个数是否互质、求逆元以及许多其他目的的算法。
你将在本章 数学编程 中学习如何在计算机上实现我们已经看到的某些算法。

求逆元

让我们从另一个角度重新审视逆元的概念。事实上，我们将提供一个万无一失的方法来求任何数的逆元。让我们考虑

5x = 1 (mod 7)

我们知道 x 是 5 的逆元，我们可以很快地算出它是 3。但 x = 10 也是一个解，x = 17、24、31、... 7n + 3 也是解。所以有无限多个解；因此，我们说 3 等价于 10、17、24、31 等等。这是一个至关重要的观察结果。

现在让我们考虑

$216x\equiv 1\ \ {\mbox{(mod 811)}}$

这里引入了一个新的符号，它是带有三个而不是两个横线的等号。它是“等价”符号；上面的语句应该读作“216x 等价于 1”，而不是“216x 等于 1”。从现在开始，我们将使用等价符号表示模运算，使用等号表示普通运算。

回到示例，我们知道 x 存在，因为 gcd(811,216) = 1。上面的问题在于，没有快速的方法来确定 x 的值！我们知道最好的方法是将 216 乘以 1、2、3、4... 直到得到答案，最多需要 811 次计算，对于人类来说太繁琐了。但有一个更好的方法，我们已经多次触及它了！

我们注意到我们可以像以前一样“跳跃”到有理数学中

${\begin{matrix}216a&=&1+811b\\0&\equiv &1+163b&{\pmod {216}}\\\end{matrix}}$

我们再次跳跃到有理数学中

${\begin{matrix}216c&=&1+163b\\53c&\equiv &1&{\pmod {163}}\\\end{matrix}}$

我们再跳一次

${\begin{matrix}53c&=&1+163d\\0&\equiv &1+4d&{\pmod {53}}\\\end{matrix}}$

现在模式很清楚了，我们将从头开始，以确保过程不中断

${\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的最小正值

${\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的最小正值

${\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的最小正值

${\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的最小正值

${\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是未知数。

举个例子，我们应该尝试找到216在模811中的逆。设216的逆为x，我们可以写成

$216x\equiv 1{\pmod {811}}\!$

我们可以将上面的公式改写成日常算术形式

$216x+811y=1\!$

这属于丢番图方程的形式。

现在我们将会使用两种方法来解决上面的问题：一种是不优雅的方法，另一种则是优雅的方法（使用神奇表格）。

上面提到的两种方法都使用欧几里得算法来求两个数的最大公约数。事实上，最大公约数与逆元的概念密切相关。让我们将欧几里得算法应用于 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	1	1	4	53	216

我们可以验证

|199×216 - 811×53| = 1

事实上，如果神奇表格构建正确，并且我们正确地交叉相乘并相减了最后两列，那么我们总是会得到 1 或 -1，前提是我们开始使用的两个数字是互质的。神奇表格只是更简洁地进行数学运算的方式。

练习

1. 求出最小的正整数 x

$216x\equiv 1\ \ {\mbox{(mod 816)}}$

2. 求出最小的正整数 x

$42x\equiv 7\ \ {\mbox{(mod 217)}}$

3.

(a) 构建 33a = 1 (mod 101) 的神奇表格

(b) 计算并以 p/q 的形式表示

$3+{1 \over 16+{1 \over 2}}$

你发现了什么？

4.

(a) 构建 17a = 1 (mod 317) 的神奇表格

(b) 计算并以 p/q 的形式表示

$18+{1 \over 1+{1 \over {1+{1 \over 1+{1 \over 5}}}}}$

你发现了什么？

中国剩余定理

中国剩余定理在中国被称为韩信点兵，最直白的翻译是韩信数兵。原问题是这样的

存在一个数 x，被 3 除余 2，被 5 除余 3，被 7 除余 2。求出最小的 x。

我们将问题转换为符号形式

${\begin{matrix}x&\equiv &2{\pmod {3}}\\x&\equiv &3{\pmod {5}}\\x&\equiv &2{\pmod {7}}\\\end{matrix}}$

我们如何找到这样的 x？我们将使用一种熟悉的方法，它最好通过例子来解释

观察 x = 2 (mod 3)，我们将其跳跃到普通的数学中

${\begin{matrix}x&\equiv &2{\pmod {3}}\\x&=&2+3a\qquad (1)\end{matrix}}$

现在我们观察这个方程模 5 的结果

$2+\!$	$3a\!$	$\equiv 3{\pmod {5}}\!$
	$3a\!$	$\equiv 1{\pmod {5}}\!$
	$a\!$	$\equiv 2{\pmod {5}}\!$
	$a\!$	$=2+5b\!$

将(1)代入得到：

$x\!$	$=2+3(2+5b)\!$
	$=8+15b\!$

现在观察上述等式模7的结果

$x=8+15b\equiv 2{\pmod {7}}\!$

我们得到

$b\equiv 1{\pmod {7}}\!$

为了使x最小，我们选择b=1，因此x=23。一个简单的检验（由读者完成）可以证实x=23是解。一个值得思考的问题是：满足三个同余式的下一个最小的x是多少？答案是x=128，下一个是233，再下一个是338，它们相差105，即3、5和7的乘积。

我们将通过以下例子进一步说明求解同余方程组的方法

例1 找出满足以下条件的最小的x

$x\equiv 1{\pmod {3}}\!$

$x\equiv 2{\pmod {5}}\!$

$x\equiv 3{\pmod {7}}\!$

解

$x=\!$	$1+3\!$	$a\!$	$\equiv \!$	$2{\pmod {5}}\!$
		$a\!$	$=\!$	$2+5b\!$

现在将结果代入第一个方程，我们得到

$x\!$	$=1+3(2+5b)\!$
	$=7+15b\!$
	$\equiv 3{\pmod {7}}\!$

我们得到

$b\equiv 3{\pmod {7}}\!$

$b=3+7c\!$

再次代入

$x\!$	$=7+15(3+7c)\!$
	$=52+15\times 7c\!$

因此，52 是满足同余式的最小 *x*。

示例 2

求满足以下同余式的最小 *x*

$x\equiv 5{\pmod {11}}\!$

$x\equiv 3{\pmod {7}}\!$

$x\equiv 8{\pmod {9}}\!$

解

$x\!$	$=5+11\!$	$a\equiv 3{\pmod {7}}\!$
		$a\equiv 3{\pmod {7}}\!$
		$a=3+7b\!$

代入

$x=\!$	$5+11(3+7b)\!$
$=\!$	$38+11\times 7b\!$
$\equiv \!$	$8{\pmod {9}}\!$

现在求解b

$2+2\times 7b\!$	$\equiv 8{\pmod {9}}\!$
$b\!$	$\equiv 3{\pmod {9}}\!$
$b\!$	$=3+9c\!$

再次代入

$x\!$	$=\!$	$38+11\times 7(3+9c)\!$
	$=\!$	$269+11\times 7\times 9c\!$

因此，269 是满足同余式的最小 x。

练习

1. 求解x

${\begin{matrix}3x&\equiv &5{\pmod {14}}\\2x&\equiv &-3{\pmod {17}}\\x&\equiv &6{\pmod {15}}\\\end{matrix}}$

2. 求解x

${\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)

但我们不会考虑这种愚蠢的例子。

回到第一个例子，我们可以尝试通过以下方法求解

${\begin{matrix}x&=&5+15k&\equiv &10&{\pmod {21}}\\&&15k&\equiv &5&\\&&3k&\equiv &1&\\\end{matrix}}$

上面的方程没有解，因为 3 在模 21 下没有逆元！

人们可能会很快得出结论，如果两个模系统有一个公因子，那么就没有解。但事实并非如此！考虑

$x\equiv 4{\pmod {15}}\!$

$x\equiv 7{\pmod {21}}\!$

我们可以找到一个解

$x=\!$	$4+15k\!$	$\equiv 7{\pmod {21}}\!$
	$15k\!$	$\equiv 3{\pmod {21}}\!$
	$5\times 3k\!$	$\equiv 3{\pmod {21}}\!$

现在我们将等式两边都乘以5的逆元（即17），得到

$3k\equiv 9\!$

显然，k = 3 是一个解，并且这两个模系统与第一个示例（即15和21）相同。

那么是什么决定了同余方程组是否有解呢？让我们考虑一般情况

$x\equiv a{\pmod {m}}\!$

$x\equiv b{\pmod {n}}\!$

我们有

$x=a+km\!$

$x=b+ln\!$

本质上，问题要求我们找到k和l，使得上述方程成立。

我们可以用以下方法来解决这个问题

$0=(a-b)+(km-ln)\,\!$

$(ln-km)=(a-b)\,\!$

现在假设m和n的gcd(m,n) = d，并且m = dm_o，n = dn_o。我们有

$dln_{o}-dkm_{o}=(a-b)\,\!$

$ln_{o}-km_{o}=(a-b)/d\,\!$

如果(a - b)/d是一个整数，那么我们可以将该方程模m_o，得到

$ln_{o}\equiv (a-b)/d{\pmod {m_{o}}}\,\!$

同样，上述结果只有在(a - b)/d为整数时才有意义。如果(a - b)/d为整数，那么就存在一个解，因为m_o和n_o是互质的！

总之：对于两个同余方程组

$x\equiv a{\pmod {m}}\,\!$

$x\equiv b{\pmod {n}}\,\!$

只有当

d = gcd(m,n) 整除 (a - b) 时，方程才有解。

以上结论可以推广到多个同余方程的情况。对于一个包含 n 个同余方程的方程组

$x\equiv a_{1}{\pmod {m_{1}}}\,\!$

$x\equiv a_{2}{\pmod {m_{2}}}\,\!$

...

$x\equiv a_{n}{\pmod {m_{n}}}\,\!$

要使方程组有解，要求当 i ≠ j 时

gcd(m_i,m_j) 整除 (a_i - a_j)

练习

判断以下每个同余方程组是否存在解。并解释原因。

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. 已知最大素数——摘要

反馈

你觉得怎么样？ 太简单了还是太难了？信息太多还是不够？我们如何改进？请在讨论栏中留言告诉我们。更重要的是，自己编辑它，让它变得更好。