点击任一公式，可查看并复制 LaTeX 源码。正文、公式及此工具均可单文件离线使用；剪贴板受限时可选中源码手动复制。

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

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

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

来源：原始分享对话 · 归档正文 · 读取核对报告
归档保留全部可见文字、公式和原始组件源码；其中一张公式报错截图仅保留附件引用，未直接查看。本文重新排版公式，不依赖原对话的交互组件。

目录

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

第 1 章：路线、记号与约定

返回目录

1.1 这篇笔记在回答什么

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

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

1.2 整除、同余与剩余类

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

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

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

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

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

同余不能无条件约分。 例如 $2\cdot 1\equiv 2\cdot 4(\mathrm{mod}6)$，但 $1\not\equiv 4(\mathrm{mod}6)$。第 2 章证明准确的消去条件。

1.3 范围与边界

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

欧拉函数统一定义为

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

第 2 章：裴蜀等式、消去律与模逆元

返回目录

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

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

令

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

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

如果 $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$：

右侧两项均被 $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\mid 2\cdot 3$，但 $6$ 不整除任何一个因子。反复应用欧几里得引理，可得质数若整除有限乘积，必整除至少一个因子。

2.3 模逆元存在的充要条件

$a$ 模 $n$ 的逆元是满足 $au\equiv 1(\mathrm{mod}n)$ 的整数 $u$。对 $n\ge 2$，有

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

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

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

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

2.4 两个常用推论

互质因子的乘积仍与模数互质。 若 $ax+ny=1$、$bu+nv=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\cdot 3+1$，所以 $1=40-13\cdot 3$，从而

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

第 3 章：质因数分解为何存在且唯一

返回目录

3.1 定理的准确表述

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

其中 $p_i$ 两两不同，${\alpha }_i\ge 1$。例如 $60=2^2\cdot 3\cdot 5$。

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

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

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

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

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

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

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

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

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

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

第 4 章：费马小定理与三个应用

返回目录

4.1 两种形式与各自条件

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

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

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

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

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

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

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

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

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

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

4.3 应用一：大指数取余

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

例如 $100=16\cdot 6+4$，所以 $2^{100}\equiv 2^4=16\equiv 2(\mathrm{mod}7)$。

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

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

4.4 应用二：整除证明

第一种形式直接等价于

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

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

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

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

解 $3x\equiv 2(\mathrm{mod}7)$：$3^5\equiv 5(\mathrm{mod}7)$，所以 $x\equiv 5\cdot 2\equiv 3(\mathrm{mod}7)$。检验 $3\cdot 3=9\equiv 2$。

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

4.6 两个反例防止过度使用

模数为合数时，不能直接使用指数 $n-1$：$3^7\equiv 3(\mathrm{mod}8)$，不是 $1$。

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

第 5 章：欧拉函数与容斥乘积

返回目录

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

$\phi (n)$ 统计 $1\le r\le n$ 中与 $n$ 互质的整数个数。例如 $n=12$ 时为 $1,5,7,11$，故 $\phi (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,\dots ,n$ 中，$p$ 的倍数有 $n/p$ 个；当 $p,q$ 是 $n$ 的不同质因子时，同时为两者倍数，等价于为 $pq$ 倍数，共 $n/(pq)$ 个。这些商都是整数。

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

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

例如 $30=2\cdot 3\cdot 5$：$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$ 的整数，它在展开中的总权重为

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

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

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

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

5.4 常用值与乘法性

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

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

第 6 章：欧拉定理为何成立

返回目录

6.1 定理与具体排列

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

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

6.2 完整证明

取 $1,\dots ,n-1$ 中全部互质代表 $r_1,\dots ,r_k$，其中 $k=\phi (n)$。考察 $a{r}_i$ 的余数。

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

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

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

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

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

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

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

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

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

欧拉定理给出一个可用指数，未承诺最小。例如 $2^3\equiv 1(\mathrm{mod}7)$，而 $\phi (7)=6$。这引出乘法阶。

第 7 章：乘法阶与真正的最小周期

返回目录

7.1 定义与存在性

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

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

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

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

设 $d={\mathrm{ord}}_n(a)$。对于 $k\ge 0$，

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

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

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

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

7.3 如何求阶与缩减指数

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

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

利用阶缩减可能更短：$1000\equiv 1(\mathrm{mod}3)$，所以 $2^{1000}\equiv 2(\mathrm{mod}7)$；费马小定理按 $6$ 取余则需再算 $2^4$。

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

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

若 $a$ 的阶为 $d$，$m\ge 1$，则

令 $h=gcd(d,m)$，写 $d=h{d}^{\prime }$、$m=h{m}^{\prime }$，其中 $gcd(d^{\prime },m^{\prime })=1$。对正整数 $k$，

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

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

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

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

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

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

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

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

第 8 章：原根及质数模原根存在性

返回目录

8.1 原根生成什么

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

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

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

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

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

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

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

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

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

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

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

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

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

第二步：识别阶中的完整质数幂。 令 $t_i={\mathrm{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$，矛盾。因此

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

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

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

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

8.4 原根有多少个

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

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

8.5 原根判定与合数反例

设 $p\nmid g$，$N=p-1$ 的不同质因子为 $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\equiv 13$，$3^8\equiv {13}^2\equiv 16\not\equiv 1$，所以 $3$ 为原根。

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

一般分类是：在 $n\ge 2$ 的约定下，有原根的模数恰好为 $2,4,q^k,2q^k$，其中 $q$ 为奇质数，$k\ge 1$。此分类是拓展结论，本篇没有给出其完整证明；可参看 Yale 数论与密码学课程讲义。

第 9 章：中国剩余定理的标准形式

返回目录

9.1 两两互质模数的定理

设正整数 $m_1,\dots ,m_k$ 两两互质，余数 $a_i$ 为任意整数，令 $M=m_1\cdots m_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_i{u}_i+m_i{v}_i=1$，令 $E_i=M_i{u}_i$。于是

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

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

9.3 唯一性与全部解

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

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

9.4 手算构造公式

求 $x\equiv 2(\mathrm{mod}3)$、$x\equiv 3(\mathrm{mod}5)$、$x\equiv 2(\mathrm{mod}7)$。

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

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

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

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

从结构上说，映射

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

第 10 章：中国剩余定理的一般形式

返回目录

10.1 相容性条件与正确周期

对任意正整数模数 $m_1,\dots ,m_k$，方程组 $x\equiv a_i(\mathrm{mod}{m}_i)$ 有解，当且仅当

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

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

10.2 两个模数：必要性

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

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

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

假设 $g\mid (b-a)$，写 $m=g{m}^{\prime }$、$n=g{n}^{\prime }$、$b-a=gc$，其中 $m^{\prime },n^{\prime }$ 互质。

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

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

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

10.4 非互质的手算例子

求 $x\equiv 2(\mathrm{mod}6)$、$x\equiv 5(\mathrm{mod}9)$。公约数 $3$ 整除余数差 $3$，所以有解。

写 $x=2+6t$，代入得到 $6t\equiv 3(\mathrm{mod}9)$。这一同余等价于 $2t\equiv 1(\mathrm{mod}3)$：是同时将整除等式的两边及模数除以 $3$，并非保持原模数的无条件约分。

所以 $t\equiv 2(\mathrm{mod}3)$，取 $t=2+3s$，得

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

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

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

写

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

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

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

而构造保证 $x_0\equiv a_{h(j)}(\mathrm{mod}{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\cdot 9\cdot 5$，可提取

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

第 11 章：RSA 的指数与解密正确性

返回目录

11.1 数学设置与选择顺序

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

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

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

因此目标是证明任意消息都满足 $m^{ed}\equiv m(\mathrm{mod}n)$；再由两者都处于 $0,\dots ,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\cdot 3$ 给出 $d\equiv 27(\mathrm{mod}40)$，可取 $d=27$，因为 $3\cdot 27=81=1+2\cdot 40$。

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

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

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

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

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

先在模 $p$ 下讨论。

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

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

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

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

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

11.5 两个具体消息与快速幂

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

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

$27=16+8+2+1$，因此 ${13}^{27}\equiv 31\cdot 36\cdot 4\cdot 13\equiv 7(\mathrm{mod}55)$。

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

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

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

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