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

HSME
内容
素数
模算术
问题和项目
问题集
项目
解答
练习解答
问题集解答
杂项
定义表
完整版本
PDF 版本

模算术

简介

模算术与素数有着有趣的联系。

模算术是一个系统，其中所有数字都小于某个正整数n，例如，如果从0开始计数，则会得到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），直到它落在该范围内。

如上所述，模算术与普通算术并没有太大区别。例如，在模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（含）之间的数字。

练习

在模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 之外没有其他公约数。

存在一种快速且优雅的方法来计算两个数的 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

需要注意的是

1. gcd 不一定是质数。
2. 两个不同质数的 gcd 为 1。换句话说，两个不同质数总是互质的。

练习

1. 确定以下数字集是否互质

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

2. 求数字 15、510 和 375 的 gcd

信息 -- 算法

算法是描述一系列动作的逐步说明，当正确执行时可以完成一项任务。存在用于查找质数、判断两个数是否互质、查找逆元以及许多其他用途的算法。
您将在 [[../../../Mathematical Programming/]] 章节中学习如何使用计算机实现我们已经看到的某些算法。

查找逆元

让我们从不同的角度再次审视逆元的概念。事实上，我们将提供一种万无一失的方法来找到任何数的逆元。让我们考虑

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的不同值。

细心的读者应该已经注意到，这只是欧几里得的gcd算法反过来。

以下是一些这种巧妙方法应用的例子

示例 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 在 mod 102 中没有逆元。

到目前为止，我们讨论了如何找到以下形式方程的整数解

ax + by = 1

其中x 和y 是未知数，a 和b 是两个给定的常数，这些方程称为线性丢番图方程。有趣的是，有时没有解，但如果存在解，则意味着存在无限多个解。

丢番图方程

在模算术 部分，我们陈述了一个定理，该定理指出如果 gcd(a,m) = 1，则a^-1（a 的逆元）存在于 mod m 中。不难看出，如果p 是素数，则对所有小于p 的b，gcd(b,p) = 1，因此我们可以说在 mod p 中，除了 0 之外的每个数都有逆元。

我们还展示了一种在 mod p 中找到任何元素的逆元的方法。事实上，在模算术中找到一个数的逆元相当于解一种称为丢番图方程的方程。丢番图方程是以下形式的方程

ax + by = d

其中x 和y 是未知数。

例如，我们应该尝试找到 216 在 mod 811 中的逆元。设 216 的逆元为x，我们可以写

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

我们可以用日常算术重新写上述表达式

$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

现在观察 mod 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}}\!$

我们选择b = 1 来最小化x，因此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. 已知最大素数 - 摘要

反馈

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