高中数学拓展/进阶模算术

高中数学拓展

---

补充章节 — 素数与模算术 — 逻辑

数学证明 — 集合论与无限过程 — 计数与生成函数 — 离散概率

矩阵 — 进阶模算术 — 数学规划 — 马尔可夫链

HSME
内容
进阶模算术
乘法群与离散对数
问题与项目
习题集
项目
解答
练习解答
习题集解答
其他
定义表
完整版
PDF版本

介绍

数学是科学的皇后，数论是数学的皇后。 -- 卡尔·弗里德里希·高斯 1777 - 1855

在素数与模算术部分，我们讨论了素数的基本性质及其与模算术的联系。在大多数情况下，我们的注意力都集中在模p算术，其中p是素数。

在本章中，我们首先讨论一些模素数p算术中更基本的结果，然后继续讨论模m算术的结果，其中m是合数。特别是，我们将仔细研究中国剩余定理（CRT），以及它如何允许我们将模m算术分解为分量。从这个角度来看，CRT是一个极其强大的工具，可以帮助我们相对轻松地解开模算术的许多秘密。

最后，我们将介绍阿贝尔群的概念，通过模算术中的乘法来讨论离散对数问题，该问题是当今已知最重要的密码系统之一的基础。

假设知识 在本章中，我们假设读者能够找到逆元，并能够解决同余方程组（中国剩余定理）（参见：素数与模算术）。

威尔逊定理

威尔逊定理是一个简单的结果，它导致了初等数论中许多有趣的观察。它指出，如果p是素数，则

$1\cdot 2\cdot 3\cdots (p-1)\equiv p-1{\pmod {p}}$

我们知道 *p* - 1 的逆元是 *p* - 1，所以其他每个数字都可以与其逆元配对并 *消除*。例如，设 *p* = 7，我们考虑

1 × 2 × .. × 6 ≡ (2 × 4) × (3 × 5) × 1 × 6 = 6

我们所做的就是将互为逆元的数字配对，然后剩下的数字就是其逆元为自身的数字。在这种情况下，它们是 1 和 6。

但是，存在一个技术上的难点。对于一个一般的质数 *p*，我们如何知道 1 和 *p* - 1 是模 *p* 中唯一两个平方后等于 1 的数字？对于非质数的 *m*，*x*² ≡ 1 (mod *m*) 有超过 2 个解，例如，设 *m* = 15，则 x = 1、14、4、11 都是 *x*² ≡ 1 (mod *m*) 的解。

然而，我们可以证明，当 *p* 为质数时，*x*² ≡ 1 (mod *p*) 最多只有两个解。我们通过一个简单的 *反证法* 论证来实现这一点。您可能想跳过以下证明，并想出自己对威尔逊定理为真的原因的解释。

设 *p* 为质数，且 *x*² ≡ 1 (mod *p*)。我们的目标是证明最多只有 2 个解，即 *x* = 1、-1

$x^{2}-1\!$	$\equiv 0\!$
$(x-1)(x+1)\!$	$\equiv 0\!$

从上面可以明显看出，*x* = 1、-1 (≡ *p* - 1) 是解。假设还有另一个解 *x* = *d*，且 *d* 不等于 1 或 -1。由于 *p* 是质数，我们知道 *d* - 1 必须有逆元。我们将 *x* 替换为 *d*，并将两边乘以逆元，即

$(d-1)(d+1)\!$	$=0\!$
$d+1\!$	$=0\!$
$d\!$	$=-1\!$

但我们最初的假设是 *d* ≠ -1。这是一个矛盾。因此，*x*² ≡ 1 (mod *p*) 最多只有 2 个解。

费马小定理

有一个以业余数学家之王 费马 命名的非凡小定理。它指出，如果 *p* 为质数，且给定 *a* ≠ 0，则

$a^{p-1}\equiv 1{\pmod {p}}\!$

这个定理取决于 *p* 是质数的事实。回想一下，如果 *p* 是质数，则 *a* ≠ 0 有逆元。因此，对于任何 *b* 和 *c*，我们必须有

$ab\equiv ac{\pmod {p}}\!$ 当且仅当 $b\equiv c{\pmod {p}}\!$

上述结果的一个简单推论是，以下数字在模 *p* 下必须互不相同

*a*，2*a*，3*a*，4*a*，...，(*p*-1)*a*

并且这些数字共有 *p* - 1 个！因此，上面的列表只是 1、2、... *p* - 1 按不同顺序排列的数字。让我们看一个例子，取 *p* = 5，*a* = 2

1, 2, 3, 4

在模 5 的情况下，将上述所有数乘以 2，我们得到

2, 4, 1, 3

它们只是原数字的顺序不同。

因此，对于任何 *p* 并使用威尔逊定理（回顾：1 × 2 × ... × (p-1) ≡ -1），我们得到

${\displaystyle a\cdot 2a\cdots (p-1)a\!$	$\equiv \!$	$1\cdot 2\cdots (p-1)$
	$\equiv \!$	$-1\!$

另一方面，我们也得到

${\displaystyle a\cdot 2a\cdots (p-1)a\!$	$\equiv \!$	$a^{p-1}(1\cdot 2\cdots (p-1))$
	$\equiv \!$	$-a^{p-1}\!$

将这两个结果相等，我们得到

$-a^{p-1}\!$

$\equiv \!$

$-1\!$

这实际上是费马小定理。

一般模 m 的模运算

*中国剩余定理再探*

本节内容比较理论化，旨在证明下一节中我们将要讨论的运算。因此，不必完全理解这里的内容，读者可以跳过以下内容。

回顾我们在模运算部分介绍的中国剩余定理（CRT）。它表明，如果以下同余式

$x\equiv b{\pmod {n_{1}}}\!$

$x\equiv c{\pmod {n_{2}}}\!$

有解当且仅当 gcd(n₁,n₂) 整除 (b - c)。

这个看似简单的定理是模 *m*（非素数）运算的关键！我们将考虑 *m* 只有两个素数因子的情况，然后可以推导出一般情况。

假设 *m* = *p*ⁱ*q*^j，其中 *p* 和 *q* 是不同的素数，那么 *m* 以下的每个自然数（0，1，2，...，m - 1）都唯一对应于模 *p*ⁱ 和模 *q*^j 的一个同余系统。这是因为 gcd(pⁱ,q^j) = 1，所以它能整除所有数字。

考虑一个数字 *n*，它对应于

$n\equiv x_{n}{\pmod {p^{i}}}\!$

$n\equiv y_{n}{\pmod {q^{j}}}\!$

对于一些 x_n 和 y_n。如果 *r* ≠ *n*，那么 *r* 对应于

$r\equiv x_{r}{\pmod {p^{i}}}\!$

$r\equiv y_{r}{\pmod {q^{j}}}\!$

现在，由于 *r* 和 *n* 不同，我们必须有 *x*_r ≠ *x*_n 或者 *y*_r ≠ *y*_n

例如，取$m=12=2^{2}\times 3$，那么我们可以构建以下表格，显示$x_{n}$，$y_{n}$ 对于每个 n (0, 1, 2 ... 11)

n	n (mod 22)	n (mod 3)
0	0	0
1	1	1
2	2	2
3	3	0
4	0	1
5	1	2
6	2	0
7	3	1
8	0	2
9	1	0
10	2	1
11	3	2

注意，正如预测的那样，每个数字都唯一对应于两个不同的同余系统：模 2² 和模 3。

练习

1. 考虑 m = 45 = 3² × 5. 完成下面的表格，并验证任何两个数字在第二列和第三列中至少有一个位置不同。

n	n (mod 32)	n (mod 5)
0	0	0
1	1	1
2	2	2
...
44	?	?

2. 假设 m = pⁱq^j，n 对应于

$n\equiv x_{n}{\pmod {p^{i}}}\!$

$n\equiv y_{n}{\pmod {q^{j}}}\!$

且 r 对应于

$r\equiv x_{r}{\pmod {p^{i}}}\!$

$r\equiv y_{r}{\pmod {q^{j}}}\!$

是否真的

$n+r\equiv x_{n}+x_{r}{\pmod {p^{i}}}\!$

$n+r\equiv y_{n}+y_{r}{\pmod {q^{j}}}\!$

以及

$nr\equiv x_{n}x_{r}{\pmod {p^{i}}}\!$

$nr\equiv y_{n}y_{r}{\pmod {q^{j}}}\!$

使用 CRT 进行算术

上面的练习 2 为 CRT 如何帮助模 m 算术提供了最明显的指示。读者在现阶段不必完全理解上面的内容。我们将继续描述 CRT 如何帮助模 m 算术。简单来说，CRT 帮助将模 m 运算分解为模 m 的质因子的更小的运算。

像往常一样，让我们先考虑一个简单的例子。设 $m=63=3^{2}\ \times \ 7$，我们看到 m 有两个不同的质因子。我们应该用两种方法演示 51 和 13 模 63 的乘法。首先，是标准方法

$51\times 13\!$	$=\!$	$663\!$
	$=\!$	$10\times 63+33\!$
	$\equiv \!$	$33{\pmod {63}}\!$

或者，我们注意到

$51\equiv 6{\pmod {9}}\!$

和

$51\equiv 2{\pmod {7}}\!$

我们可以将上述两个表达式表示为一个二元组 (6,2)。我们略微滥用符号，写 51 = (6,2)。类似地，我们写 13 = (4,6)。当我们对二元组进行乘法运算时，我们按分量相乘，即 (a,b) × (c,d) = (ac,bd)，

$51\times 13\!$	$=\!$	$(6,2)\times (4,6)\!$
	$=\!$	$(24,12)\!$
	$=\!$	$(2\times 9+6,7+5)\!$
	$\equiv \!$	$(6,5)\!$

现在让我们解决

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

和

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

我们写 x = 6 + 9a，这是第一个同余方程，然后

$6+9a\!$	$\equiv \!$	$5{\pmod {7}}\!$
$2a\!$	$\equiv \!$	$6\!$
$a\!$	$\equiv \!$	$3\!$

因此，我们有 a = 3 + 7b，代入回去得到

$x=6+9(3+7b)=33+63b\equiv 33{\pmod {63}}\!$

这与我们用标准方法将 51 和 13 相乘 (mod 63) 得到的结果相同！

让我们总结一下我们做了什么。通过将两个数字（51 和 13）表示为两个二元组，并按分量相乘，我们最终得到了另一个二元组。根据中国剩余定理，这个二元组对应着这两个数字的乘积 (mod m)。

我们将再举两个例子。令 $m=88=2^{3}\times 11$，让我们用两种方法将 66 和 40 相乘。首先，用标准方法

$66\times 40\!$	$=\!$	$2640\!$
	$=\!$	$30\times 88\!$
	$\equiv \!$	$0{\pmod {88}}\!$

现在用第二种方法，40 = (0,7) 和 66 = (4,0) 以及

$66\times 40\!$	$=\!$	$(0,7)\times (4,0)\!$
	$=\!$	$(0,0)\!$
	$\equiv \!$	$0{\pmod {88}}\!$

对于第二个例子，我们注意到没有必要只停留在两个不同的质因数上。我们令 $m=975=3\times 5^{2}\times 13$，并将 900 和 647 (mod 975) 相乘，

$900\times 647\!$	$=\!$	$582300\!$
	$\equiv \!$	$225{\pmod {975}}\!$

对于另一种方法，我们注意到 900 ≡ 0 (mod 3) ≡ 0 (mod 25) ≡ 3 (mod 13)，而 647 ≡ 2 (mod 3) ≡ 22 (mod 25) ≡ 10 (mod 13)，

$900\times 647\!$	$=\!$	$(0,0,3)\times (2,22,10)\!$
	$\equiv \!$	$(0,0,30)\!$
	$\equiv \!$	$(0,0,4)\!$

现在如果我们解以下同余方程

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

$x\equiv 0{\pmod {25}}\!$

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

那么我们会得到 x ≡ 225!

为什么？ 如果说有什么，将 mod m 中的模运算分解成更小的部分似乎需要不少工作。以乘法为例，首先，我们需要将每个数表示成一个 n 元组（n 是 m 的不同质因数的个数），然后按分量相乘，最后解出得到的 n 个同余方程。当然，这肯定比直接将两个数相乘然后将结果模 m 更复杂。那么为什么要费心研究它呢？

通过将一个数 m 分解成质因数，我们对模运算的实际工作原理有了更深刻的理解。更重要的是，mod m 中的许多问题可能很难解决，但当分解成更小的部分后，突然变得很容易，例如，对一般 m 的威尔逊定理（下面将讨论）。

练习

1. 证明加法也可以按分量进行。

2. 按分量相乘 32 和 84 (mod 134)。

...

欧拉函数

为了讨论更一般的形式的威尔逊定理和费马小定理在 mod m (非素数) 中的应用，了解一位著名数学家欧拉的简单结果会很有帮助。更具体地说，我们想讨论一个函数，称为欧拉函数 (或欧拉 φ)，记作 φ。

φ 函数做的事情非常简单。对于任何自然数 m，φ(m) 给出 n < m 的个数，使得 gcd(n,m) = 1。换句话说，它计算在 mod m 中有多少个数有逆。我们将首先讨论 φ(m) 在简单情况下的值，然后从基本结果推导出一般 m 的公式。

例如，令m = 5，则 φ(m) = 4。由于 5 是质数，5 以下的所有非零自然数（1、2、3 和 4）都与其互质。所以，在模 5 中有 4 个数具有逆元。实际上，如果m 是质数，则 φ(m) = m - 1。

我们可以将上述情况推广到m = p^r，其中p 是质数。在这种情况下，我们尝试使用计数论证来计算 φ(m)。注意，m 以下有p^r 个自然数（0、1、2 ... p^r - 1），因此 φ(m) = p^r -（n < m 且 gcd(n,m) ≠ 1 的个数）。我们这样做是因为计算没有模m 逆元的n 的个数更容易。

模m 中的一个元素n 没有逆元当且仅当它与m 共有公因子。但m 的所有因子（不等于 1）都是p 的倍数。那么，在模m 中有多少个p 的倍数呢？我们可以列出它们，它们是

$0,p,2p,\cdots ,p^{r}-p\!$

其中最后一个元素可以写成 (p^r-1 - 1)p，因此有 $p^{r-1}\!$ 个p 的倍数。因此，我们可以得出结论

$\phi (p^{r})=p^{r}-p^{r-1}\!$

现在我们拥有了推导出任意m 的 φ(m) 公式所需的所有工具。

根据算术基本定理，任何自然数m 都可以唯一地表示为质数的乘积，即

$m=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\!$

其中 p_i 对于 i = 1, 2 ... r 是不同的质数，而 k_i 是正整数。例如，1225275 = 3×5²×17×31²。从这里开始，读者应该尝试推导出以下结果（CRT 可能会有所帮助）。

欧拉函数 φ

Suppose m can be uniquely expressed as below
  $m=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\!$
then
  $\phi (m)=(p_{1}^{k_{1}}-p_{1}^{k_{1}-1})(p_{2}^{k_{2}}-p_{2}^{k_{2}-1})\cdots (p_{r}^{k_{r}}-p_{r}^{k_{r}-1})\!$

利用欧拉函数，我们可以推导出费马小定理的更一般情况，即

$a^{\phi (m)}\equiv 1{\pmod {m}}\$

威尔逊定理

一般m 的威尔逊定理指出，模m 中所有可逆元素的乘积

等于 -1，如果m 只有一个质因子，或者m = 2p^k 对于某个质数p

等于 1，对于所有其他情况

模m 的可逆元素是指一个自然数n < m，使得 gcd(n, m) = 1。自逆元素是指其逆元与其自身相同的元素。

在质数p 的威尔逊定理的证明中，1 到p - 1 的所有数都有逆元。对于一般的m 来说，情况并非如此。实际上，可以肯定的是 (m - 1)! ≡ 0 (mod m)，出于这个原因，我们改为考虑模m 中所有可逆元素的乘积。

对于m = p 是质数的情况，我们还利用了 1 和p - 1 是唯一平方后等于 1 的元素这一事实。实际上，对于m = p^k，1 和m - 1（≡ -1）是唯一的自逆元素（见练习）。但对于一般的m 来说，情况并非如此。例如，我们取m = 21。在模 21 算术中，以下每个数都有其自身作为逆元

1, 20, 8, 13

那么，我们如何说所有可逆元素的乘积等于 1 呢？

我们使用上面描述的 CRT。让我们考虑m = 2p^k 的情况。根据 CRT，模m 中的每个元素都可以表示为一个二元组 (a,b)，其中a 可以取值为 0 或 1，而b 可以取值为 0、1、... 或p^k - 1。每个二元组都唯一地对应于一对同余方程，并且可以对乘法进行分量式操作。

利用上述信息，我们可以轻松列出所有自逆元素，因为 (a,b)² ≡ 1 意味着 (a²,b²) = (1,1)，所以a 是模 2 中的可逆元素，而b 是模p^k 中的可逆元素，所以a ≡ 1 或 -1，b ≡ 1 或 -1。但在模 2 中 1 ≡ -1，所以a = 1。因此，在模m = 2p^k 中有 2 个元素是自逆的，它们是 (1,1) = 1 和 (1, -1) = m - 1。所以，在这种情况下，结果与m 只有一个质因子时相同。

对于m 有多个质因子且m≠ 2p^k 的情况。假设m 有n 个质因子，那么m 可以表示为一个n 元组。假设m 有 3 个不同的质因子，那么m 的所有自逆元素是

1. (1,1,1)
2. (1,1,-1)
3. (1,-1,1)
4. (1,-1,-1)
5. (-1,1,1)
6. (-1,1,-1)
7. (-1,-1,1)
8. (-1,-1,-1)

它们的乘积是 (1,1,1)，它对应于模m 中的 1。

练习

1. 令p 为质数。证明在模p^k 算术中，1 和p^k - 1 是唯一的自逆元素。

...待续

费马小定理

如前一节所述，并非每个元素都可逆（即具有逆元）模m。费马最后定理的广义版本使用了欧拉函数，它指出

$a^{\phi (m)}\equiv 1{\pmod {m}}\!$

对于所有满足 gcd(a,m) = 1 的a ≠ 0。这很容易从威尔逊定理的广义版本中看出。我们使用类似于费马小定理证明的技术。我们有

$(ab_{1})(ab_{2})\cdots (ab_{\phi (m)})\equiv b_{1}b_{2}\cdots b_{\phi (m)}{\pmod {m}}$

其中 b_i 是模 m 的所有可逆元素。根据威尔逊定理，所有可逆元素的乘积等于，例如，d (= 1 或 -1)。因此我们得到

$a^{\phi (m)}d\equiv d{\pmod {m}}\!$

这实际上是费马小定理的陈述。

虽然费马小定理非常简洁，但在某种程度上它是不精确的。例如，取 m = 15 = 3 × 5，我们知道如果 a 模 15 有逆，则 a^φ(15) = a⁸ ≡ 1 (mod 15)。但 8 太大了，我们只需要 4，这意味着 a⁴ ≡ 1 (mod 15)，对于所有具有逆元的 a（读者可以验证）。

卡迈克尔函数 λ(m) 是最小的数字，使得对于可逆的 a，a^λ(m) ≡ 1 (mod m) 。习题集 中的一个问题涉及到这个函数。

练习

...待续

二阶扭转分解

很明显，分解一个大数可能非常困难。例如，给定 76372591715434667 是两个素数的乘积，读者可以分解它吗？如果没有好的计算机代数软件的帮助，这项任务几乎是不可能的。截至今天，还没有已知的有效的通用算法可以将一个数分解成素数因子。

然而，在某些特殊情况下，分解可能很容易。我们将考虑二阶扭转分解方法。模 m 算术中的二阶扭转元素是一个数 a，使得 a² ≡ 1 (mod m)。

让我们考虑模 21 算术中的一个例子。注意，使用中国剩余定理，我们可以将模 21 中的任何数表示为一个二元组。我们注意到二阶扭转元素是 1 = (1,1)，13 = (1,-1)，8 = (-1,1) 和 20 = (-1,-1)。我们感兴趣的是数字 13 和 8，因为 1 和 20 (≡ - 1) 显然是二阶扭转的，我们称这些数字为平凡的二阶扭转。

现在，13 + 1 = (1,-1) + (1,1) = (2,0)。因此 13 + 1 = 14 是一个与 21 有公因子的元素，因为 14 的二元组表示中的第二个分量为零。因此 GCD(14,21) = 7 是 21 的一个因子。

上面的例子非常愚蠢，因为任何人都可以分解 21。但是 24131 怎么办呢？分解它并不容易。但是，如果我们知道 12271 是一个非平凡的（即 ≠ 1 或 -1）二阶扭转元素，那么我们可以得出结论，gcd(12271 + 1,24131) 和 gcd(12271 - 1,24131) 都是 24131 的因子。事实上，gcd(12272,24131) = 59 和 gcd(12270,24131) = 409 都是 24131 的因子。

更一般地，设 m 为一个合数，t 为模 m 的一个非平凡的二阶扭转元素，即 t ≠ 1，-1。那么

gcd(t + 1,m) 整除 m，并且

gdc(t - 1,m) 整除 m

这可以用中国剩余定理来解释。

我们将解释 m = pq 且 p 和 q 为素数的情况。给定 t 是一个非平凡的二阶扭转元素，则 t 有表示 (1,-1) 或 (-1,1)。假设 t = (-1,1)，则 t + 1 = (-1,1) + (1,1) = (0,2)，因此 t + 1 必须是 p 的倍数，因此 gcd(t,m) = p。在另一种情况下，t - 1 = (-1,1) - (1,1) = (-2,0)，所以 gcd(t - 1,m) = q。

因此，如果我们得到一个非平凡的二阶扭转元素，那么我们实际上已经找到了一个（甚至可能多个）素数因子，这在分解这个数方面大有帮助。在大多数现代公钥密码学应用中，要破解系统，我们只需要分解一个有两个素数因子的数。在这方面，二阶扭转分解方法非常有效。

当然，找到一个非平凡的二阶扭转元素也不是一件容易的事。所以，互联网银行暂时还是安全的。顺便说一下，76372591715434667 = 224364191 × 340395637。

练习

1. 给定 18815 是模 26176 的一个二阶扭转元素。分解 26176。

…待续

下一节

下一节： 乘法群

习题集 习题集