# 费马小定理与初等数论笔记

**第一版 · 2026-10-10**  
从整除基础、欧拉定理到原根与 RSA

本笔记依据《介绍费马小定理》的 21 轮对话整理，按证明依赖重排，合并重复回答，并补全原根证明中的辅助结论。主线从良序原理、带余除法与归纳法出发。每次使用互质、质数、交换律等条件时，都说明它们发挥的作用。

来源：原始分享对话 · [归档正文](../../../../资料/费马小定理对话-2026-10-10/原对话正文.md) · [读取核对报告](../../../../资料/费马小定理对话-2026-10-10/读取核对报告.json)  
归档保留全部可见文字、公式和原始组件源码；其中一张公式报错截图仅保留附件引用，未直接查看。本文重新排版公式，不依赖原对话的交互组件。

<a id="reading-toc"></a>
## 目录

- [第 1 章：路线、记号与约定](#chapter-1)
- [第 2 章：裴蜀等式、消去律与模逆元](#chapter-2)
- [第 3 章：质因数分解为何存在且唯一](#chapter-3)
- [第 4 章：费马小定理与三个应用](#chapter-4)
- [第 5 章：欧拉函数与容斥乘积](#chapter-5)
- [第 6 章：欧拉定理为何成立](#chapter-6)
- [第 7 章：乘法阶与真正的最小周期](#chapter-7)
- [第 8 章：原根及质数模原根存在性](#chapter-8)
- [第 9 章：中国剩余定理的标准形式](#chapter-9)
- [第 10 章：中国剩余定理的一般形式](#chapter-10)
- [第 11 章：RSA 的指数与解密正确性](#chapter-11)
- [第 12 章：概念辨析、拓展与对话覆盖](#chapter-12)

<a id="chapter-1"></a>
## 第 1 章：路线、记号与约定

[返回目录](#reading-toc)

### 1.1 这篇笔记在回答什么

大指数可以缩小，是因为模幂运算存在周期。但证明周期之前，需要知道何时能够约分；要计算周期长度和互质整数个数，又需要整数分解与计数工具。以下关系是本篇的证明骨架。

| 基础与结论 | 关键依赖 | 用途 |
| --- | --- | --- |
| 裴蜀等式 | 良序原理、带余除法 | 证明互质消去律与模逆元存在 |
| 质因数分解唯一性 | 欧几里得引理 | 识别整数的质数幂结构 |
| 费马小定理 | 非零剩余类的排列、合法约分 | 质数模下缩减指数 |
| 欧拉函数乘积公式 | 唯一分解、容斥 | 计算互质剩余类个数 |
| 欧拉定理与乘法阶 | 互质剩余类的排列、带余除法 | 任意模数下的幂周期 |
| 质数模原根存在性 | 多项式根数上界、阶的两个引理 | 一个元素生成所有非零剩余类 |
| 中国剩余定理 | 裴蜀等式、互质消去律、质数幂分解 | 拆分与合并同余条件 |
| RSA 解密正确性 | 模逆元、费马小定理、互质模数合并 | 证明加密后能够恢复消息 |

**原根是乘法阶的拓展分支。RSA 解密正确性的证明不需要先证明原根存在。** 中国剩余定理的完整存在性构造也比 RSA 所需的“同余合并”结论更强。

### 1.2 整除、同余与剩余类

对整数 $a,b$，$a\mid b$ 表示存在整数 $t$，使 $b=at$。本篇讨论最大公约数时，$a,b$ 不全为零，并取最大公约数为正数。

对正整数模数 $n$，定义

$$
a\equiv b\pmod n\quad\Longleftrightarrow\quad n\mid(a-b).
$$

这表示两者有相同余数，不表示两个整数相等。一个剩余类是所有与某个整数同余的整数所组成的集合。本文常用 $0,1,\ldots,n-1$ 作为代表。

同余可以相加、相减、相乘和取非负整数次幂。以乘法为例，若 $a\equiv b$、$c\equiv d\pmod n$，则

$$
ac-bd=c(a-b)+b(c-d)
$$

能被 $n$ 整除。因此同余运算的规则来自普通整除性质。

**同余不能无条件约分。** 例如 $2\cdot1\equiv2\cdot4\pmod6$，但 $1\not\equiv4\pmod6$。第 2 章证明准确的消去条件。

### 1.3 范围与边界

除中国剩余定理外，讨论欧拉定理、乘法阶与原根时默认 $n\ge2$。指数默认为非负整数；负指数只有在明确使用模逆元时才有意义。模幂中的 $a^0=1$ 表示乘法单位元。

欧拉函数统一定义为

$$
\varphi(n)=\#\{1\le r\le n:\gcd(r,n)=1\}.
$$

因此 $\varphi(1)=1$。当 $n>1$ 时，$n$ 本身不互质，等价于统计 $1,\ldots,n-1$。主线中涉及 $\varphi(p-1)$ 时，这个约定也覆盖 $p=2$。

<a id="chapter-2"></a>
## 第 2 章：裴蜀等式、消去律与模逆元

[返回目录](#reading-toc)

### 2.1 从最小正线性组合证明裴蜀等式

**定理。** 对不全为零的整数 $a,b$，存在整数 $x,y$，使

$$
ax+by=\gcd(a,b).
$$

令

$$
S=\{ax+by:x,y\in\mathbb Z,\ ax+by>0\}.
$$

集合非空：若 $a\ne0$，选择 $x=1$ 或 $-1$、$y=0$ 即得到 $|a|$；否则用 $|b|$。由良序原理，$S$ 有最小元素 $d>0$，写作 $d=ax_0+by_0$。

对 $a$ 作带余除法：$a=qd+r$，$0\le r<d$。于是

$$
r=a-qd=a(1-qx_0)+b(-qy_0).
$$

如果 $r>0$，它也是 $S$ 的元素，却比 $d$ 小，矛盾。故 $r=0$，即 $d\mid a$。同理 $d\mid b$。

另一方面，任意正公约数 $c$ 都整除 $a,b$ 的整数线性组合，所以 $c\mid d$，进而 $c\le d$。因此 $d$ 既是公约数，又不小于任何正公约数，正是 $\gcd(a,b)$。所需的 $x_0,y_0$ 已由构造给出。证毕。

> 关键不是猜出线性组合，而是先取最小正组合，再用带余除法排除更小的正组合。这个证明不依赖质因数分解，后面的论证因而没有循环。

### 2.2 互质消去律与欧几里得引理

若 $\gcd(a,n)=1$ 且 $n\mid ab$，由裴蜀等式取 $ax+ny=1$，乘以 $b$：

$$
b=abx+nby.
$$

右侧两项均被 $n$ 整除，故 $n\mid b$。这就是**互质消去律**，其中 $n$ 不必是质数。

作为特例，若 $p$ 是质数且 $p\mid ab$，则 $p\mid a$ 或 $p\mid b$。因为一旦 $p\nmid a$，质数的因数只有 $1,p$，所以 $\gcd(a,p)=1$，可应用消去律。这称为**欧几里得引理**。

质数条件不可随意删去：$6\mid2\cdot3$，但 $6$ 不整除任何一个因子。反复应用欧几里得引理，可得质数若整除有限乘积，必整除至少一个因子。

### 2.3 模逆元存在的充要条件

$a$ 模 $n$ 的逆元是满足 $au\equiv1\pmod n$ 的整数 $u$。对 $n\ge2$，有

$$
a\text{ 模 }n\text{ 有逆元}\quad\Longleftrightarrow\quad\gcd(a,n)=1.
$$

充分性：由 $ax+ny=1$，取 $u=x$。

必要性：若 $au-nv=1$，$a,n$ 的每个公约数都整除左边，因此整除 $1$，所以只能为 $1$。

逆元在模 $n$ 意义下唯一：若 $au\equiv av\equiv1$，则 $n\mid a(u-v)$；由互质消去律，$n\mid(u-v)$。

因此，当 $\gcd(a,n)=1$ 时，从 $ab\equiv ac\pmod n$ 可以乘以逆元，推出 $b\equiv c\pmod n$。这是后面约去阶乘或剩余类乘积的依据。

### 2.4 两个常用推论

**互质因子的乘积仍与模数互质。** 若 $ax+ny=1$、$bu+nv=1$，相乘得到

$$
abxu+n(axv+buy+nyv)=1.
$$

任意 $ab,n$ 的公约数都整除 $1$，故 $\gcd(ab,n)=1$。有限多个因子可归纳处理。

**互质的两个数都整除一个整数，则其乘积也整除。** 若 $\gcd(m,n)=1$、$m\mid A$、$n\mid A$，写 $A=mt$。由 $n\mid mt$ 与消去律，$n\mid t$，故 $mn\mid A$。

### 2.5 如何实际计算逆元

带余除法给出 $\gcd(a,b)=\gcd(b,r)$，因为 $a=qb+r$ 使两对数的公约数完全相同。反复除法时非零余数严格变小，最终停在最大公约数；再回代即可找到裴蜀系数。这就是扩展欧几里得算法。

例如 $40=13\cdot3+1$，所以 $1=40-13\cdot3$，从而

$$
3^{-1}\equiv-13\equiv27\pmod{40}.
$$

这里逆元符号表示模运算中的整数剩余类，不是普通分数 $1/3$。

<a id="chapter-3"></a>
## 第 3 章：质因数分解为何存在且唯一

[返回目录](#reading-toc)

### 3.1 定理的准确表述

每个整数 $n>1$ 都能写成有限个质数的乘积。除排列顺序外，质因子及其重数唯一。将相同质因子合并，可以写成

$$
n=p_1^{\alpha_1}\cdots p_k^{\alpha_k},
$$

其中 $p_i$ 两两不同，$\alpha_i\ge1$。例如 $60=2^2\cdot3\cdot5$。

“存在”和“唯一”是两个不同问题，不能只证明能拆分，就认为不可能有另一种拆分。

### 3.2 存在性：强归纳法

$n=2$ 自身是质数。假设所有满足 $2\le m<n$ 的整数均可分解。

若 $n$ 是质数，结论立即成立。若 $n$ 是合数，可写 $n=ab$，其中 $1<a,b<n$。由归纳假设，$a,b$ 都是质数的有限乘积，合在一起给出 $n$ 的分解。因此对所有 $n>1$ 成立。

### 3.3 唯一性：配对和终止分别证明

假设

$$
p_1\cdots p_r=q_1\cdots q_s
$$

是两种分解。$p_1$ 整除右侧，由欧几里得引理，它整除某个 $q_j$。两个数都是质数，所以 $p_1=q_j$。重排右边，将它放到第一位，再在普通整数等式中约去相同质数。

重复此步骤，每次都会找到并约去一对相同质因子。

**为什么两边一定同时约完？** 假设 $r<s$。约去左侧全部 $r$ 个因子后，得到

$$
1=q_{r+1}\cdots q_s.
$$

右侧至少剩一个质数，每个质数都不小于 $2$，故乘积大于 $1$，矛盾。$r>s$ 同样矛盾。所以 $r=s$，每一步配对后所有质因子一一相等，重数也相同。证毕。

> 能够配对来自欧几里得引理；必然同时结束来自非空质数乘积大于 $1$。这是原对话“为什么最终同时约完”的完整回答。

### 3.4 最大公约数与最小公倍数的质数幂描述

给定有限多个正整数，把出现的质数统一记为 $p_j$，缺少某个质因子时指数记为 $0$。两个数的最大公约数取每个指数的最小值，最小公倍数取最大值：

$$
\gcd(m,n)=\prod_jp_j^{\min(\alpha_j,\beta_j)},\qquad
\operatorname{lcm}(m,n)=\prod_jp_j^{\max(\alpha_j,\beta_j)}.
$$

理由是：由唯一分解，一个正整数整除另一个，当且仅当每个质数指数都不超过对方。公约数和公倍数的条件遂逐个指数决定。

于是 $\gcd(m,n)\operatorname{lcm}(m,n)=mn$。一个整数同时被所有 $m_i$ 整除，当且仅当被 $\operatorname{lcm}(m_1,\ldots,m_k)$ 整除；整数为 $0$ 的情况也显然成立。这将说明中国剩余定理的解周期。

<a id="chapter-4"></a>
## 第 4 章：费马小定理与三个应用

[返回目录](#reading-toc)

### 4.1 两种形式与各自条件

若 $p$ 是质数，则对任意整数 $a$，

$$
a^p\equiv a\pmod p.
$$

若再要求 $p\nmid a$，等价于 $\gcd(a,p)=1$，则

$$
a^{p-1}\equiv1\pmod p.
$$

不能把第二式应用于 $p\mid a$：这时正整数次幂全部模 $p$ 为 $0$。

### 4.2 完整证明：乘法使非零剩余类重新排列

设 $p\nmid a$。考察 $a,2a,\ldots,(p-1)a$ 的余数。

任何一个余数都不为 $0$：否则 $p\mid ai$，欧几里得引理推出 $p\mid i$，与 $1\le i\le p-1$ 矛盾。

任何两个余数都不同：若 $ai\equiv aj\pmod p$，互质消去律给出 $p\mid(i-j)$。但 $|i-j|<p$，故 $i=j$。

因此这 $p-1$ 个余数恰好是 $1,2,\ldots,p-1$ 的一个排列。将全部同余相乘，得到

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

阶乘中的每个因子都与 $p$ 互质，所以其乘积也与 $p$ 互质，可以合法约去，得到第二种形式。

若 $p\nmid a$，将它乘以 $a$，即得第一种形式；若 $p\mid a$，$a^p$ 与 $a$ 均模 $p$ 为 $0$。所以第一式覆盖任意整数。反过来，在 $p\nmid a$ 条件下，从第一式约去 $a$ 可回到第二式。证毕。

### 4.3 应用一：大指数取余

对 $k\ge0$ 作带余除法 $k=q(p-1)+r$，$0\le r<p-1$。若 $p\nmid a$，则

$$
a^k=(a^{p-1})^qa^r\equiv a^r\pmod p.
$$

例如 $100=16\cdot6+4$，所以 $2^{100}\equiv2^4=16\equiv2\pmod7$。

**为什么需要互质？** 每消去一个长度为 $p-1$ 的幂块，依赖该幂块等于 $1$。例如 $7^{12}\equiv0\pmod7$，不能将指数对 $6$ 取余而改成 $7^0=1$。缩减后指数非零时偶然仍得 $0$，并不能证明这个规则普遍合法。

若底数是 $p$ 的倍数且指数为正，直接取余 $0$ 即可；指数为 $0$ 时按单位元解释，余数为 $1$。

### 4.4 应用二：整除证明

第一种形式直接等价于

$$
p\mid(a^p-a).
$$

例如对每个整数 $a$，$5\mid(a^5-a)$，无需再假设 $a$ 与 $5$ 互质。若要合并多个不同质数的整除结论，可用第 2 章的互质乘积整除推论。

### 4.5 应用三：模逆元与线性同余

若 $p\nmid a$，由 $a\cdot a^{p-2}\equiv1$，得到

$$
a^{-1}\equiv a^{p-2}\pmod p.
$$

$p=2$ 时指数为 $0$，非零剩余类只有 $1$，公式仍成立。

解 $3x\equiv2\pmod7$：$3^5\equiv5\pmod7$，所以 $x\equiv5\cdot2\equiv3\pmod7$。检验 $3\cdot3=9\equiv2$。

费马小定理提供质数模下的一种求逆方法；裴蜀等式及扩展欧几里得算法还能处理一般互质的合数模数。

### 4.6 两个反例防止过度使用

模数为合数时，不能直接使用指数 $n-1$：$3^7\equiv3\pmod8$，不是 $1$。

费马同余成立也不能反推模数是质数。$341=11\cdot31$，而 $2^{10}=1024\equiv1\pmod{341}$，所以 $2^{340}=(2^{10})^{34}\equiv1$。这只是合数通过某个底数的检验。费马小定理是必要性质，不是这一检验的充分判据。

<a id="chapter-5"></a>
## 第 5 章：欧拉函数与容斥乘积

[返回目录](#reading-toc)

### 5.1 统计的是互质整数，不是素数

$\varphi(n)$ 统计 $1\le r\le n$ 中与 $n$ 互质的整数个数。例如 $n=12$ 时为 $1,5,7,11$，故 $\varphi(12)=4$。这些数不必都是质数。

若 $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}>1$，由唯一分解，$r$ 与 $n$ 互质，当且仅当没有任何 $p_i$ 整除 $r$。

证明后一等价关系：如果某个 $p_i\mid r$，它就是公共因子；如果最大公约数大于 $1$，由存在性它有某个质因子，该质数同时整除 $r,n$，由唯一分解它必为某个 $p_i$。

### 5.2 两个、三个质因子的容斥

在 $1,\ldots,n$ 中，$p$ 的倍数有 $n/p$ 个；当 $p,q$ 是 $n$ 的不同质因子时，同时为两者倍数，等价于为 $pq$ 倍数，共 $n/(pq)$ 个。这些商都是整数。

若 $n=p^\alpha q^\beta$，先减掉两类倍数，再加回被减掉两次的交集：

$$
\varphi(n)=n-\frac np-\frac nq+\frac n{pq}
=n\left(1-\frac1p\right)\left(1-\frac1q\right).
$$

对于三个不同质因子 $p,q,r$，

$$
\begin{aligned}
\varphi(n)={}&n-\left(\frac np+\frac nq+\frac nr\right)\\
&+\left(\frac n{pq}+\frac n{pr}+\frac n{qr}\right)-\frac n{pqr}.
\end{aligned}
$$

例如 $30=2\cdot3\cdot5$：$30-15-10-6+5+3+2-1=8$，留下 $1,7,11,13,17,19,23,29$。

中间结果 $30-15-10-6=-1$、再加回两重交集得到 $9$，都是带符号的中间计数，不是某个最终“剩余集合”的元素个数。三重交集最后减去，才得正确值 $8$。

### 5.3 一般容斥为何成立

令 $A_i$ 是能被 $p_i$ 整除的整数集合。统计其补集时，按所选集合个数交替加减，并把空交集解释为全部 $n$ 个整数。

对一个落入恰好 $j$ 个 $A_i$ 的整数，它在展开中的总权重为

$$
\sum_{t=0}^{j}(-1)^t\binom jt=(1-1)^j.
$$

若 $j=0$，权重为 $1$；若 $j\ge1$，权重为 $0$。所以恰好只计入互质整数，每个计入一次。这证明了容斥，而非仅把它作为未证明的工具使用。

记 $I=\{1,\ldots,k\}$。不同质数互质，每个交集对应其乘积的倍数，故

$$
\varphi(n)=n\sum_{J\subseteq I}(-1)^{|J|}\prod_{i\in J}\frac1{p_i}.
$$

空乘积取 $1$。展开 $\prod_i(1-1/p_i)$ 时，从每个括号选 $1$ 或 $-1/p_i$。选择负项的下标恰好形成子集 $J$，贡献 $(-1)^{|J|}\prod_{i\in J}1/p_i$；每个子集出现一次。因此

$$
\boxed{\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)}.
$$

**乘积公式是容斥展开的因式分解表达。** 质因子指数虽影响 $n$，排除的倍数类别却只由不同质因子决定，所以每个质数只出现一个括号。

### 5.4 常用值与乘法性

$$
\varphi(p)=p-1,\qquad\varphi(p^\alpha)=p^\alpha-p^{\alpha-1}.
$$

若 $\gcd(m,n)=1$，两者的质因子集合不交，由乘积公式立即得到 $\varphi(mn)=\varphi(m)\varphi(n)$。这是**互质条件下的乘法性**，不能对任意两数使用；例如 $\varphi(4)=2$，而 $\varphi(2)^2=1$。

不同质数 $p,q$ 的乘积满足 $\varphi(pq)=(p-1)(q-1)$。一般公式例如

$$
\varphi(360)=360\left(1-\frac12\right)\left(1-\frac13\right)\left(1-\frac15\right)=96.
$$

<a id="chapter-6"></a>
## 第 6 章：欧拉定理为何成立

[返回目录](#reading-toc)

### 6.1 定理与具体排列

若 $n\ge2$ 且 $\gcd(a,n)=1$，则

$$
\boxed{a^{\varphi(n)}\equiv1\pmod n}.
$$

模 $10$ 的互质代表为 $1,3,7,9$。乘以 $3$ 后余数是 $3,9,1,7$，仍是同一组数。这里模数可以是合数，但底数仍然必须互质。

### 6.2 完整证明

取 $1,\ldots,n-1$ 中全部互质代表 $r_1,\ldots,r_k$，其中 $k=\varphi(n)$。考察 $ar_i$ 的余数。

第一，$ar_i$ 与 $n$ 互质，因为两个互质于 $n$ 的数，其乘积也与 $n$ 互质；取余并不改变最大公约数，因为 $ar_i=qn+s$ 的两边给出同一组公约数。

第二，余数互不相同。若 $ar_i\equiv ar_j$，由 $a$ 的逆元可消去 $a$，得到 $r_i\equiv r_j$。它们位于同一个代表范围，故 $r_i=r_j$。

于是这 $k$ 个余数就是原互质代表的一个排列。设 $R=r_1\cdots r_k$，相乘得到

$$
a^kR\equiv R\pmod n.
$$

每个 $r_i$ 都与 $n$ 互质，所以 $R$ 也与 $n$ 互质，可约去，得 $a^k\equiv1$。证毕。

欧拉函数出现在指数上，是因为相乘时共有 $k=\varphi(n)$ 个因子，每个因子都贡献一个 $a$。

### 6.3 与费马小定理的联系及使用范围

当 $n=p$ 为质数时，$\varphi(p)=p-1$，欧拉定理变成费马小定理的互质形式。若需要对任意底数得到 $a^p\equiv a$，再补 $p\mid a$ 的情形。

若 $k=q\varphi(n)+r$，$0\le r<\varphi(n)$，则在互质条件下 $a^k\equiv a^r\pmod n$。例如 $\varphi(10)=4$，所以 $3^{100}\equiv1\pmod{10}$。

非互质时不能套用：$\varphi(8)=4$，但 $2^4\equiv0\pmod8$；指数取余后改成 $2^0$ 会得 $1$。第 11 章处理 RSA 非互质消息时必须改用逐个质数的证明。

欧拉定理给出一个可用指数，未承诺最小。例如 $2^3\equiv1\pmod7$，而 $\varphi(7)=6$。这引出乘法阶。

<a id="chapter-7"></a>
## 第 7 章：乘法阶与真正的最小周期

[返回目录](#reading-toc)

### 7.1 定义与存在性

对 $\gcd(a,n)=1$，满足 $a^d\equiv1\pmod n$ 的最小正整数 $d$，记为 $\operatorname{ord}_n(a)$。

欧拉定理保证这样的正指数集合非空，良序原理保证最小值存在。若 $a^d\equiv1$，则任何 $a,n$ 的公约数都整除 $a^d$ 与 $a^d-1$，进而整除 $1$；所以不互质的底数不可能存在这种乘法阶。

例如 $2$ 模 $7$ 的幂余数是 $2,4,1,2,4,1,\ldots$，故 $\operatorname{ord}_7(2)=3$。

### 7.2 阶整除所有使幂等于一的指数

设 $d=\operatorname{ord}_n(a)$。对于 $k\ge0$，

$$
a^k\equiv1\pmod n\quad\Longleftrightarrow\quad d\mid k.
$$

若 $d\mid k$，写 $k=qd$，直接得 $a^k\equiv1$。

反过来，作带余除法 $k=qd+r$，$0\le r<d$。因为 $a^k\equiv(a^d)^qa^r\equiv a^r$，得到 $a^r\equiv1$。若 $r>0$，违背 $d$ 的最小性，所以 $r=0$。证毕。这也包括 $k=0$。

将 $k=\varphi(n)$ 代入，得到

$$
\operatorname{ord}_n(a)\mid\varphi(n).
$$

对非负整数 $u,v$，还有 $a^u\equiv a^v$ 当且仅当 $u\equiv v\pmod d$。不妨 $u\ge v$，用 $a^v$ 的逆元约分，再使用刚才结论即可。因此 $d$ 是余数序列的真正最小正周期。

### 7.3 如何求阶与缩减指数

阶只能是 $\varphi(n)$ 的正因数。按从小到大检验这些因数，第一个使幂余数为 $1$ 的就是阶。

例如 $\varphi(17)=16$，候选为 $1,2,4,8,16$。$4\not\equiv1$，$4^2\equiv-1$，$4^4\equiv1\pmod{17}$，所以阶为 $4$。

利用阶缩减可能更短：$1000\equiv1\pmod3$，所以 $2^{1000}\equiv2\pmod7$；费马小定理按 $6$ 取余则需再算 $2^4$。

若已知 $D=\varphi(n)$ 的素因子分解，可从 $D$ 开始：对质因子 $q$，当 $a^{D/q}\equiv1$ 时令 $D\leftarrow D/q$ 并继续。始终有 $d\mid D$；最后若 $D>d$，$D/d$ 有一个质因子 $q$，就仍可除去 $q$，矛盾，所以最后为 $d$。这里只说明数学算法，不声称分解大数很容易。

### 7.4 辅助引理一：一个幂的阶

若 $a$ 的阶为 $d$，$m\ge1$，则

$$
\boxed{\operatorname{ord}_n(a^m)=\frac d{\gcd(d,m)}}.
$$

令 $h=\gcd(d,m)$，写 $d=hd'$、$m=hm'$，其中 $\gcd(d',m')=1$。对正整数 $k$，

$$
(a^m)^k\equiv1
\ \Longleftrightarrow\ d\mid mk
\ \Longleftrightarrow\ d'\mid m'k
\ \Longleftrightarrow\ d'\mid k.
$$

最后一步用互质消去律。所以最小正 $k$ 是 $d'$。这补全了原对话原根证明中直接使用的公式。

### 7.5 辅助引理二：阶互质时乘积的阶

设 $\operatorname{ord}_n(a)=r$、$\operatorname{ord}_n(b)=s$，且 $\gcd(r,s)=1$。模整数的乘法可交换，因此

$$
\boxed{\operatorname{ord}_n(ab)=rs}.
$$

先有 $(ab)^{rs}=(a^r)^s(b^s)^r\equiv1$，故 $t=\operatorname{ord}_n(ab)$ 整除 $rs$。

又 $(ab)^t\equiv1$。取 $r$ 次幂，得到 $a^{rt}b^{rt}\equiv1$。$a^{rt}\equiv1$，所以 $b^{rt}\equiv1$，进而 $s\mid rt$。由 $r,s$ 互质，推出 $s\mid t$。同理 $r\mid t$，再由互质乘积整除推论，$rs\mid t$。结合 $t\mid rs$，得 $t=rs$。

这样无需使用负指数也能完成证明。在一般群中还必须要求两个元素可交换，否则幂不一定可拆开。

若阶不互质，结论未必成立：模 $7$ 时 $2,4$ 的阶均为 $3$，但 $2\cdot4\equiv1$，乘积的阶为 $1$。

对任意互质于模数的 $a,b$，令 $L=\operatorname{lcm}(r,s)$，则 $(ab)^L\equiv1$，故乘积的阶总整除 $L$。互质阶条件保证这个整除进一步达到等号。

<a id="chapter-8"></a>
## 第 8 章：原根及质数模原根存在性

[返回目录](#reading-toc)

### 8.1 原根生成什么

对 $n\ge2$，若 $g$ 与 $n$ 互质且 $\operatorname{ord}_n(g)=\varphi(n)$，称其为模 $n$ 的原根。对质数 $p$，目标阶为 $p-1$。

若阶为 $d$，$g^0,\ldots,g^{d-1}$ 两两不同，否则约分将产生更短周期。因此阶等于 $\varphi(n)$ 时，这些幂恰好穷尽所有互质剩余类。

模 $7$ 时 $3$ 的幂余数为 $3,2,6,4,5,1$，所以 $3$ 是原根；$2$ 的余数循环只有 $2,4,1$，不是原根。

### 8.2 为什么非零多项式的根数不超过次数

在模质数 $p$ 的系数运算中，设 $f$ 的次数为 $m$，最高次系数模 $p$ 不为 $0$。它最多有 $m$ 个不同剩余类的根。

先证明因式分解的依据。对每个 $j\ge1$，

$$
x^j-r^j=(x-r)(x^{j-1}+x^{j-2}r+\cdots+r^{j-1}).
$$

逐项相加给出 $f(x)-f(r)=(x-r)h(x)$。若 $f(r)\equiv0$，便在模 $p$ 的多项式环里得到 $f(x)=(x-r)h(x)$，$h$ 次数为 $m-1$。

$m=0$ 时非零常数没有根。归纳地，若没有根结论显然；若有根 $r$，对另一个不同根 $s$，有 $(s-r)h(s)\equiv0$。因为 $p$ 质数且 $s-r\not\equiv0$，可消去 $s-r$，故 $h(s)\equiv0$。归纳假设使其他根最多 $m-1$ 个，加上 $r$ 至多 $m$ 个。证毕。

质数条件在此保证非零元素可逆。模 $8$ 的多项式 $x^2-1$ 有 $1,3,5,7$ 四个根，已超过次数，说明合数模数不能照搬。

### 8.3 每个质数都有原根：完整构造证明

$p=2$ 时，非零剩余类只有 $1$，其阶为 $1=p-1$，已经是原根。以下设 $p>2$，令

$$
N=p-1=\prod_{i=1}^{k}q_i^{e_i},
$$

其中 $q_i$ 为不同质数。先为每个最大质数幂构造一个对应阶的元素。

**第一步：找到不被较短指数消掉的元素。** 多项式 $x^{N/q_i}-1$ 次数为 $N/q_i<N$，故最多有 $N/q_i$ 个根，而非零剩余类有 $N$ 个。因此可选择非零 $a_i$，使

$$
a_i^{N/q_i}\not\equiv1\pmod p.
$$

**第二步：识别阶中的完整质数幂。** 令 $t_i=\operatorname{ord}_p(a_i)$。由第 7 章，$t_i\mid N$，但 $t_i\nmid N/q_i$；否则幂必等于 $1$。

$N/q_i$ 与 $N$ 只在 $q_i$ 的指数上差 $1$。$t_i$ 的其他质数指数已由 $t_i\mid N$ 限制，若 $q_i$ 的指数也至多 $e_i-1$，便会整除 $N/q_i$，矛盾。因此

$$
t_i=q_i^{e_i}s_i,\qquad\gcd(q_i,s_i)=1.
$$

**第三步：除去阶中的其他因子。** 取 $b_i=a_i^{s_i}$。因为 $s_i\mid t_i$，由幂的阶公式，

$$
\operatorname{ord}_p(b_i)
=\frac{t_i}{\gcd(t_i,s_i)}
=\frac{t_i}{s_i}=q_i^{e_i}.
$$

**第四步：合并各个互质阶。** 取 $g=b_1\cdots b_k$。各阶为不同质数的幂，两两互质；模乘法可交换。反复使用第 7.5 节，每次累积阶仍与下一个阶互质，得到

$$
\operatorname{ord}_p(g)=\prod_iq_i^{e_i}=N=p-1.
$$

所以 $g$ 是原根。证毕。

> “每个元素的阶都整除 $p-1$”本身不足以证明有人达到 $p-1$。多项式根数上界负责提供元素，幂的阶公式负责提取质数幂，互质阶乘积引理负责拼成完整阶。

### 8.4 原根有多少个

取一个模 $p$ 的原根 $g$，$N=p-1$。全部非零剩余类可唯一表示为 $g^m$，$1\le m\le N$。由幂的阶公式，

$$
\operatorname{ord}_p(g^m)=\frac{N}{\gcd(N,m)}.
$$

因此 $g^m$ 是原根，当且仅当 $\gcd(N,m)=1$，共有 $\varphi(N)$ 个。所以模 $p$ 的原根数为 $\varphi(p-1)$。$p=2$ 时用 $\varphi(1)=1$，结论仍成立。

| 模数 | 原根个数 | 全部原根代表 |
| --- | --- | --- |
| 5 | 2 | 2、3 |
| 7 | 2 | 3、5 |
| 11 | 4 | 2、6、7、8 |
| 13 | 4 | 2、6、7、11 |
| 17 | 8 | 3、5、6、7、10、11、12、14 |

### 8.5 原根判定与合数反例

设 $p\nmid g$，$N=p-1$ 的不同质因子为 $q_i$。则

$$
g\text{ 是原根}\quad\Longleftrightarrow\quad
g^{N/q_i}\not\equiv1\pmod p\ \text{对全部 }q_i.
$$

必要性：阶为 $N$ 时不整除任何 $N/q_i$。

充分性：令阶为 $d\mid N$。若 $d<N$，商 $N/d>1$ 有某个质因子 $q_i$，于是 $d\mid N/q_i$，推出相应幂等于 $1$，矛盾。$p=2$ 时没有需检验的质因子，非零条件已唯一确定原根。

例：模 $17$ 时 $N=16=2^4$。$3^4\equiv13$，$3^8\equiv13^2\equiv16\not\equiv1$，所以 $3$ 为原根。

模 $8$ 的互质代表 $1,3,5,7$ 全部平方为 $1$，因此阶最多为 $2$，而 $\varphi(8)=4$；故没有原根。

一般分类是：在 $n\ge2$ 的约定下，有原根的模数恰好为 $2,4,q^k,2q^k$，其中 $q$ 为奇质数，$k\ge1$。**此分类是拓展结论，本篇没有给出其完整证明**；可参看 [Yale 数论与密码学课程讲义](https://zoo.cs.yale.edu/classes/cs467/2006f/attach/ln11.html)。

<a id="chapter-9"></a>
## 第 9 章：中国剩余定理的标准形式

[返回目录](#reading-toc)

### 9.1 两两互质模数的定理

设正整数 $m_1,\ldots,m_k$ 两两互质，余数 $a_i$ 为任意整数，令 $M=m_1\cdots m_k$。则

$$
x\equiv a_i\pmod{m_i}\quad(i=1,\ldots,k)
$$

一定有解，所有解恰为 $x=x_0+tM$，$t\in\mathbb Z$。

“唯一”指模 $M$ 的唯一剩余类，而非只有一个整数解。模数为 $1$ 的条件不限制任何整数，可以删除；若全部为 $1$，全部整数就是模 $1$ 的一个剩余类。以下构造处理剩余的模数。

### 9.2 存在性：构造对自己的模数余一、对其他余零的项

令 $M_i=M/m_i$。因为其他每个 $m_j$ 都与 $m_i$ 互质，第 2.4 节的乘积互质性质给出 $\gcd(M_i,m_i)=1$。

由裴蜀等式，取 $M_iu_i+m_iv_i=1$，令 $E_i=M_iu_i$。于是

$$
E_i\equiv1\pmod{m_i},\qquad E_i\equiv0\pmod{m_j}\ (j\ne i).
$$

第二式来自 $m_j\mid M_i$。再取

$$
x_0=\sum_{i=1}^ka_iE_i=\sum_{i=1}^ka_iM_iu_i.
$$

对任意固定 $m_j$ 取模，其余项全为 $0$，只有 $a_jE_j\equiv a_j$，所以满足全部方程。存在性得证。

### 9.3 唯一性与全部解

若 $x,y$ 都是解，则每个 $m_i$ 都整除 $x-y$。由于模数两两互质，任意部分乘积仍与下一个模数互质，可反复用互质乘积整除推论，得 $M\mid(x-y)$。

反过来，$x_0+tM$ 对各模数都与 $x_0$ 同余，所以仍是解。因此全部解恰为该形式。

### 9.4 手算构造公式

求 $x\equiv2\pmod3$、$x\equiv3\pmod5$、$x\equiv2\pmod7$。

$M=105$，$M_1=35$、$M_2=21$、$M_3=15$；各自逆元可取 $2,1,1$，因为对应乘积模自身模数均为 $1$。于是

$$
x_0=2\cdot35\cdot2+3\cdot21+2\cdot15=233\equiv23\pmod{105}.
$$

全部解 $x=23+105t$。直接检验 $23$ 分别余 $2,3,2$。

### 9.5 合并同余与环结构的联系

若两个整数模各个互质 $m_i$ 分别同余，它们模 $M$ 也同余。这个结论只用唯一性，在 RSA 中不需要重新构造解。

从结构上说，映射

$$
\mathbb Z/M\mathbb Z\longrightarrow\prod_i\mathbb Z/m_i\mathbb Z,
\qquad[x]_M\longmapsto([x]_{m_1},\ldots,[x]_{m_k})
$$

是双射：存在性给出满射，唯一性给出单射。它也保持加法和乘法，因为每个坐标的取余运算保持这些运算。这给出了环同构的一种具体例子；前面的数论证明不需要预先掌握环论。

<a id="chapter-10"></a>
## 第 10 章：中国剩余定理的一般形式

[返回目录](#reading-toc)

### 10.1 相容性条件与正确周期

对任意正整数模数 $m_1,\ldots,m_k$，方程组 $x\equiv a_i\pmod{m_i}$ 有解，当且仅当

$$
\boxed{\gcd(m_i,m_j)\mid(a_i-a_j)\quad\text{对全部 }i,j}.
$$

若有解，令 $L=\operatorname{lcm}(m_1,\ldots,m_k)$，全部解恰为 $x=x_0+tL$。

模数不互质时，相容性有实际限制。例如 $x\equiv2\pmod6$ 与 $x\equiv4\pmod9$ 无解，因为公约数 $3$ 不整除余数差 $2$。互质时公约数为 $1$，条件自动满足，且 $L$ 等于乘积，所以标准形式是特殊情形。

### 10.2 两个模数：必要性

考虑 $x\equiv a\pmod m$、$x\equiv b\pmod n$，记 $g=\gcd(m,n)$。

若存在 $x$，$g$ 整除 $x-a$ 与 $x-b$，也就整除两者之差 $b-a$。因此 $g\mid(b-a)$ 必要。

### 10.3 两个模数：充分性与构造

假设 $g\mid(b-a)$，写 $m=gm'$、$n=gn'$、$b-a=gc$，其中 $m',n'$ 互质。

先令 $x=a+mt$，保证第一个方程。第二个方程要求 $mt\equiv b-a\pmod n$，等价于存在整数 $s$ 使

$$
mt-ns=b-a\quad\Longleftrightarrow\quad m't-n's=c.
$$

用裴蜀等式取 $m'u+n'v=1$，令 $t=cu$、$s=-cv$，便满足要求，因此可取 $x_0=a+mcu$。充分性得证。

若 $x,y$ 均为解，则 $m,n$ 都整除 $x-y$，由第 3.4 节，$\operatorname{lcm}(m,n)\mid(x-y)$。反过来加上该最小公倍数的任意整数倍仍是解，因而全部解及周期成立。

### 10.4 非互质的手算例子

求 $x\equiv2\pmod6$、$x\equiv5\pmod9$。公约数 $3$ 整除余数差 $3$，所以有解。

写 $x=2+6t$，代入得到 $6t\equiv3\pmod9$。这一同余等价于 $2t\equiv1\pmod3$：是同时将整除等式的两边及模数除以 $3$，并非保持原模数的无条件约分。

所以 $t\equiv2\pmod3$，取 $t=2+3s$，得

$$
x=14+18s,\qquad x\equiv14\pmod{18}.
$$

周期是 $\operatorname{lcm}(6,9)=18$，不是乘积 $54$。

### 10.5 多个模数：为何两两相容足以给出共同解

必要性仍来自任意两个方程的差。充分性必须另证，不能只说“每一对有解，所以整体有解”。以下使用质数幂分解。

写

$$
L=\operatorname{lcm}(m_1,\ldots,m_k)=\prod_{j=1}^{r}p_j^{e_j}.
$$

每个 $e_j$ 是所有模数中该质数指数的最大值，所以可选一个下标 $h(j)$，使 $p_j^{e_j}\mid m_{h(j)}$。提取约束

$$
x\equiv a_{h(j)}\pmod{p_j^{e_j}}\quad(j=1,\ldots,r).
$$

这些模数是不同质数的幂，两两互质，由标准形式得到公共解 $x_0$。

现在证明它满足原方程。固定 $i$，设 $p_j$ 在 $m_i$ 中的指数为 $f_{ij}\le e_j$。若 $f_{ij}>0$，该质数幂同时整除 $m_i$ 与 $m_{h(j)}$，故

$$
p_j^{f_{ij}}\mid\gcd(m_i,m_{h(j)})\mid(a_i-a_{h(j)}).
$$

而构造保证 $x_0\equiv a_{h(j)}\pmod{p_j^{e_j}}$，所以降到 $p_j^{f_{ij}}$ 后仍成立，结合相容性得 $x_0\equiv a_i$ 模该质数幂。对 $m_i$ 的所有不同质数幂都成立，互质乘积整除推论给出 $m_i\mid(x_0-a_i)$。

由于 $i$ 任意，满足全部原方程。若 $L=1$，则全部模数为 $1$，直接取任意整数即可。

若选择最大指数的模数有多个，相容性使它们的余数模该质数幂相同，因此提取约束没有歧义。

### 10.6 唯一性与一个多模数例子

任意两个解之差被所有 $m_i$ 整除，因此被 $L$ 整除；$x_0+tL$ 又总是解。所以解模 $L$ 唯一。$L$ 也是解集合的最小正平移周期：任何保持解的正平移量都必须被全部模数整除，因此被 $L$ 整除。

例如取 $m_1=12,m_2=18,m_3=20$，余数分别为 $5,11,17$。三个公约数为 $6,4,2$，都整除对应余数差。$L=180=4\cdot9\cdot5$，可提取

$$
x\equiv1\pmod4,\quad x\equiv2\pmod9,\quad x\equiv2\pmod5.
$$

取 $x_0=137$，逐项检验模 $12,18,20$ 分别余 $5,11,17$，故全部解为 $137+180t$。

<a id="chapter-11"></a>
## 第 11 章：RSA 的指数与解密正确性

[返回目录](#reading-toc)

### 11.1 数学设置与选择顺序

本章讨论两个不同质数的教学模型。取 $n=pq$，$F=\varphi(n)=(p-1)(q-1)$。消息取代表 $0\le m<n$。

先选择正整数 $e$，使 $\gcd(e,F)=1$；再由裴蜀等式求正整数代表 $d$，满足

$$
ed\equiv1\pmod F.
$$

公钥为 $(n,e)$，私钥指数为 $d$。加密取 $c$ 为 $m^e$ 模 $n$ 的标准余数，解密取 $c^d$ 模 $n$ 的标准余数。

$$
c\equiv m^e\pmod n,\qquad c^d\equiv m^{ed}\pmod n.
$$

因此目标是证明任意消息都满足 $m^{ed}\equiv m\pmod n$；再由两者都处于 $0,\ldots,n-1$，同余保证真正恢复同一代表。

### 11.2 指数不是随意假设出来的

固定 $e$，存在 $d$ 的充要条件为 $\gcd(e,F)=1$，这正是第 2.3 节的逆元定理。

例如 $p=5,q=11$ 时 $n=55,F=40$。若取 $e=6$，方程 $6d-40k=1$ 左侧为偶数，不可能等于 $1$。若取 $e=3$，$1=40-13\cdot3$ 给出 $d\equiv27\pmod{40}$，可取 $d=27$，因为 $3\cdot27=81=1+2\cdot40$。

至少存在互质 $e$：数学上可取 $1$；若 $F>2$，也可取 $F-1$，与 $F$ 相邻所以互质。但这些只证明存在性，**不作为安全参数建议**。例如取 $e=F-1$、$d=F-1$ 时公私指数相同，无法据此获得所期待的保密性。

### 11.3 互质消息：欧拉定理直接证明

$e,d$ 均正，故写 $ed=1+kF$ 时 $k\ge0$。若 $\gcd(m,n)=1$，欧拉定理给出 $m^F\equiv1$，于是

$$
m^{ed}=m^{1+kF}=m(m^F)^k\equiv m\pmod n.
$$

这段证明仅覆盖互质消息。RSA 的消息范围还包含 $0$ 和 $p,q$ 的倍数，需要下面的完整证明。

### 11.4 任意消息：逐个质数证明，再合并

先在模 $p$ 下讨论。

若 $p\mid m$，由于 $ed\ge1$，$m^{ed}$ 与 $m$ 的余数均为 $0$，结论成立。

若 $p\nmid m$，费马小定理给出 $m^{p-1}\equiv1$。所以

$$
\begin{aligned}
m^{ed}&=m^{1+k(p-1)(q-1)}\\
&=m\left(m^{p-1}\right)^{k(q-1)}\equiv m\pmod p.
\end{aligned}
$$

模 $q$ 完全相同：若 $q\mid m$，两边为 $0$；否则将指数写为 $1+(q-1)k(p-1)$，由费马小定理得到 $m^{ed}\equiv m\pmod q$。

因 $p,q$ 不同而互质，$p,q$ 都整除 $m^{ed}-m$，便有 $pq\mid(m^{ed}-m)$，即

$$
\boxed{(m^e)^d\equiv m\pmod{pq}}.
$$

这一步是中国剩余定理的唯一性结论；也可以直接由第 2.4 节的互质乘积整除推论完成。**没有要求消息与 $n$ 互质。**

### 11.5 两个具体消息与快速幂

继续取 $n=55,e=3,d=27$。

互质消息 $m=7$：$c\equiv7^3=343\equiv13$。反复平方得

$$
13^2\equiv4,\quad13^4\equiv16,\quad13^8\equiv36,\quad13^{16}\equiv31\pmod{55}.
$$

$27=16+8+2+1$，因此 $13^{27}\equiv31\cdot36\cdot4\cdot13\equiv7\pmod{55}$。

非互质消息 $m=5$：$c\equiv5^3\equiv15\pmod{55}$。模 $5$ 的解密结果为 $0$；模 $11$ 下 $15\equiv4$，$4^2\equiv5$、$4^5\equiv1$，所以 $4^{27}\equiv4^2\equiv5$。两条件共同确定模 $55$ 的结果为 $5$。

快速幂不必先寻找最小周期：将指数写成二进制，反复平方并乘上所需的幂，每步取余即可。它计算的是同一同余类，正确性直接来自幂运算与同余乘法。

### 11.6 更弱的指数条件与实际方案的范围

完整证明真正使用的是 $p-1\mid(ed-1)$ 与 $q-1\mid(ed-1)$，所以只需

$$
ed\equiv1\pmod{\operatorname{lcm}(p-1,q-1)}.
$$

这比模 $(p-1)(q-1)$ 的条件更弱。例如 $p=5,q=11$ 时最小公倍数为 $20$。原对话使用 $40$ 是方便的充分条件。第 12.3 节解释它与卡迈克尔函数的关系。

知道 $p,q$ 可计算 $F$ 并求逆元 $d$。反过来，对两个不同质数，若知道 $n$ 与 $F$，则 $p+q=n+1-F$，$p,q$ 是方程

$$
t^2-(n+1-F)t+n=0
$$

的两根。这个关系说明为什么 $F$ 的信息与分解密切相关，但**不构成“破解 RSA 必须先分解”的证明**。

本章给出幂运算的数学正确性；安全加密还需要消息编码、参数与实现要求。标准 [RFC 8017 第 3、5、7 节](https://www.rfc-editor.org/rfc/rfc8017.html) 区分 RSA 幂运算原语和带编码的加密方案，并以最小公倍数定义密钥条件；RSAES-OAEP 在原语外加入 OAEP 编码。小参数手算例子只供理解，不是安全实现指南。

<a id="chapter-12"></a>
## 第 12 章：概念辨析、拓展与对话覆盖

[返回目录](#reading-toc)

### 12.1 三种“个数”不要混淆

| 问题 | 记号 | 例子 |
| --- | --- | --- |
| 不超过 $x$ 的素数有多少个 | $\pi(x)$ | $\pi(12)=5$：2、3、5、7、11 |
| $n$ 有多少种不同质因子 | $\omega(n)$ | $\omega(360)=3$ |
| $n$ 的质因子算重数后有多少个 | $\Omega(n)$ | $\Omega(360)=3+2+1=6$ |
| 代表范围内与 $n$ 互质的整数有多少个 | $\varphi(n)$ | $\varphi(360)=96$ |

如果 $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$，则 $\omega(n)=k$、$\Omega(n)=\sum_i\alpha_i$，并约定 $\omega(1)=\Omega(1)=0$。因每个质因子至少为 $2$，$n\ge2^{\Omega(n)}$，所以

$$
\omega(n)\le\Omega(n)\le\lfloor\log_2n\rfloor.
$$

若有 $k$ 个不同质因子，把它们排序后第 $i$ 个不小于第 $i$ 个质数，所以 $n$ 至少是前 $k$ 个质数的乘积。因此 $n<6$ 时最多一种，$n<30$ 时最多两种，$n<210$ 时最多三种。这个上界讨论的是最大可能数量，不能当成给定整数的实际数量。

### 12.2 素数计数与渐近公式：只介绍拓展结论

素数定理为

$$
\pi(x)\sim\frac{x}{\ln x}\quad(x\to\infty).
$$

$\sim$ 表示两者比值趋于 $1$，不是精确相等；相对误差趋于 $0$，也不意味着绝对误差趋于 $0$。对整数 $n$，“小于 $n$”的计数是 $\pi(n-1)$，不是 $\pi(n)$。参看 [Carl Pomerance 的数论讲义](https://math.dartmouth.edu/~carlp/ordertalk4.pdf)。

| 上限 $n$ | 不超过 $n$ 的素数实际个数 | $n/\ln n$（约） |
| --- | --- | --- |
| 10 | 4 | 4.3 |
| 100 | 25 | 21.7 |
| 1000 | 168 | 144.8 |
| 10000 | 1229 | 1085.7 |
| 100000 | 9592 | 8685.9 |
| 1000000 | 78498 | 72382.4 |

接近大数 $x$ 的整数“成为素数的密度约为 $1/\ln x$”是一种启发式解释，不是证明。对数积分是更精细的经典近似；采用从 $2$ 起积分的记号时，可写 $\operatorname{Li}_2(x)=\int_2^xdt/\ln t$。它与采用主值积分定义的 $\operatorname{li}(x)$ 相差常数，记号应说明约定。

原对话还提到不同质因子数的最大值与平均值，其渐近量级分别是 $\ln x/\ln\ln x$ 与 $\ln\ln x$。它们是关于一批整数的统计结论，不是计算 $\omega(n)$ 的精确公式。为把平均与正常数量分开，准确写成

$$
\max_{1\le m\le x}\omega(m)\sim\frac{\ln x}{\ln\ln x},\qquad
\frac1{\lfloor x\rfloor}\sum_{m\le x}\omega(m)\sim\ln\ln x.
$$

Hardy–Ramanujan 定理的核心是“正常数量”：对每个固定 $\varepsilon>0$，除占比趋于 $0$ 的例外整数外，$\omega(m)$ 接近 $\ln\ln m$，相对偏差小于 $\varepsilon$。平均值结论与正常数量结论相关，但不是同一个陈述；这一区别可参看 [Carl Pomerance 关于数量阶的讲义](https://math.dartmouth.edu/~carlp/ordertalkmsri.pdf)。

以上解析数论结论**不在本篇的证明范围内，也不参与 RSA 正确性证明**。拓展资料可参看 [数论笔记中的算术函数阶](https://math.mit.edu/~hao_peng/skyscraper.pdf)。

### 12.3 卡迈克尔函数：统一周期与单个元素周期

对 $n\ge2$，令 $U_n$ 为互质剩余类。定义 $\lambda(n)$ 为所有 $a\in U_n$ 都满足 $a^L\equiv1$ 的最小正整数 $L$。

由第 7.2 节，一个 $L$ 对全部元素可用，当且仅当它被每个元素的阶整除。因此

$$
\lambda(n)=\operatorname{lcm}\{\operatorname{ord}_n(a):a\in U_n\},\qquad
\operatorname{ord}_n(a)\mid\lambda(n)\mid\varphi(n).
$$

最右边整除来自每个阶均整除 $\varphi(n)$，所以其最小公倍数也整除。模 $8$ 时阶分别为 $1,2,2,2$，故 $\lambda(8)=2<4=\varphi(8)$。

对质数 $p$，原根的存在保证 $\lambda(p)=p-1$。对两个不同质数 $p,q$，中国剩余定理把 $U_{pq}$ 对应到 $U_p\times U_q$，并且一个幂等于 $1$ 当且仅当两个坐标都等于 $1$，所以

$$
\lambda(pq)=\operatorname{lcm}(p-1,q-1).
$$

充分性：该最小公倍数使两个坐标的幂都为 $1$。必要性：由标准中国剩余定理可选互质元素，其模 $p$ 坐标为原根、模 $q$ 坐标为 $1$，所以任意统一指数必须被 $p-1$ 整除；交换坐标又得 $q-1$ 整除它，因而被两者最小公倍数整除。

三种指数的区别是：阶针对一个底数，$\lambda(n)$ 针对全部互质底数的最小统一指数，$\varphi(n)$ 是互质底数个数，同时提供一个统一指数。一般 $\lambda$ 的质数幂公式及全部结构不在本篇展开。

### 12.4 练习与解答

**题 1。** 求 $3^{100}$ 模 $7$ 的余数。  
解：$100\equiv4\pmod6$，$3^{100}\equiv3^4=81\equiv4$。

**题 2。** 对任意整数 $a$，$a^6\equiv1\pmod7$ 与 $a^7\equiv a\pmod7$ 哪个必成立？  
解：第二个。第一个还需 $7\nmid a$，取 $a=7$ 即得反例。

**题 3。** 解 $2x\equiv3\pmod5$。  
解：$2$ 的逆元为 $3$，所以 $x\equiv9\equiv4\pmod5$。

**题 4。** 已知 $\operatorname{ord}_{17}(3)=16$，求 $3^4$ 的阶。  
解：$16/\gcd(16,4)=4$。直接检验 $3^4\equiv13$，$13^2\equiv-1$，$13^4\equiv1$。

**题 5。** 解 $x\equiv1\pmod4$、$x\equiv3\pmod6$。  
解：公约数 $2$ 整除余数差 $2$，有解。写 $x=1+4t$，得到 $2t\equiv1\pmod3$，所以 $t\equiv2$，$x\equiv9\pmod{12}$。

**题 6。** 对 $n=55,e=3,d=27$，消息 $m=0,11,54$ 是否都能恢复？  
解：是。第 11.4 节已覆盖任意消息，包括 $0$ 与质因子倍数。加密余数分别为 $0,11,54$，相应解密余数也是它们本身。

### 12.5 原对话覆盖索引与整理校正

原始顺序共有 21 轮；下表每一行对应一个用户问题及其助手回答。重复回答的内容合并，关键追问保留到相应证明中。

| 轮次 | 用户的问题或关注点 | 对应章节 |
| --- | --- | --- |
| 1 | 介绍费马小定理与简单应用 | [第 4 章](#chapter-4)、[第 12 章练习](#chapter-12) |
| 2 | 为什么缩减指数需要互质 | [第 2 章](#chapter-2)、[第 4 章](#chapter-4) |
| 3 | 质因数分解为什么唯一 | [第 3 章](#chapter-3) |
| 4 | 使用的几个基础结论还没有证明 | [第 2 章](#chapter-2)、[第 3 章](#chapter-3) |
| 5 | 为什么两边必然同时约完 | [第 3 章](#chapter-3) |
| 6 | 小于某数的素数个数公式 | [第 12 章](#chapter-12) |
| 7 | 素因子个数与上界 | [第 12 章](#chapter-12) |
| 8 | 想找欧拉相关的计数公式 | [第 5 章](#chapter-5) |
| 9 | 展开说明欧拉函数公式 | [第 5 章](#chapter-5) |
| 10 | 为什么乘积展开对应容斥 | [第 5 章](#chapter-5) |
| 11 | 欧拉函数与小定理结合的结论 | [第 6 章](#chapter-6) |
| 12 | 继续：乘法阶 | [第 7 章](#chapter-7) |
| 13 | 继续：原根及存在性 | [第 8 章](#chapter-8)、[第 12 章](#chapter-12) |
| 14 | 原根回答公式显示异常 | [第 7 章](#chapter-7)、[第 8 章](#chapter-8)重新排版 |
| 15 | 上传截图，再指出公式损坏 | [第 8 章](#chapter-8)补“阶不整除”及质数幂解释 |
| 16 | 为什么阶互质时乘积阶相乘 | [第 7 章](#chapter-7) |
| 17 | 欧拉定理如何联系密码学 | [第 11 章](#chapter-11) |
| 18 | 不一定存在所需的两个指数吧 | [第 2 章](#chapter-2)、[第 11 章](#chapter-11) |
| 19 | 非互质消息的 RSA 怎么证明 | [第 11 章](#chapter-11) |
| 20 | 中国剩余定理的一般表述 | [第 9 章](#chapter-9)、[第 10 章](#chapter-10) |
| 21 | 两种形式的详细证明 | [第 9 章](#chapter-9)、[第 10 章](#chapter-10) |

本版补全了互质消去律、幂的阶公式、因式定理的直接恒等式、容斥的权重证明、$p=2$ 与 $\varphi(1)$ 的边界；区分了素因子数的平均与正常数量，并将安全参数的存在性例子与安全建议分开。原根分类与解析数论拓展明确标注未证明。

“欧拉函数”“欧拉定理”也与复数中的欧拉公式 $e^{i\theta}=\cos\theta+i\sin\theta$ 不同；后者可在[代数基本定理笔记](../../../代数基本定理笔记/代数基本定理笔记-v2-2026-10-07.html)中阅读。模质数的多项式与乘法结构，可以接到[多项式与分圆域笔记](../../../多项式与分圆域笔记/多项式与分圆域笔记-v1-2026-10-06.html)以及[伽罗瓦理论笔记](../../../伽罗瓦理论笔记/伽罗瓦理论笔记-v4-2026-10-05.html)。

HTML 的正文、公式与公式源码查看工具嵌入单文件，可离线阅读；PDF 提供静态正文、目录页码及分层书签。跨笔记、Markdown 与来源归档链接需要对应文件，分享整套时请保留目录层级。