阶 & 原根

前置知识：费马小定理、欧拉定理、拉格朗日定理

阶和原根，是理解模 $m$ 既约剩余系 ${\mathbf{Z}}_m^{\ast }$ 乘法结构的重要工具．基于此，可以定义 离散对数 等概念．更为一般的讨论可以参见抽象代数部分 群论 和 环论 等页面相关章节．

阶

本节中，总是假设模数 $m\in {\mathbf{N}}_{+}$ 和底数 $a\in \mathbf{Z}$ 互素，即 $(a,m)=1$，也记作 $a⟂m$．

对于 $n\in \mathbf{Z}$，幂次 呈现一种循环结构．这个循环节的最小长度，就是 $a$ 模 $m$ 的阶．阶就定义为幂 第一次回到起点 时的指数：

幂的循环结构

利用阶，可以刻画幂的循环结构．对于幂 ，可以将指数 $n$ 对阶 ${\delta }_m(a)$ 做带余除法：

进而，利用幂的运算律，就得到

$$a^n=a^{{\delta }_m(a)q+r}=(a^{{\delta }_m(a)}{)}^q\cdot a^r\equiv a^r(\mathrm{mod}m).$$

这说明，对于任意指数的幂，可以将它平移到第一个非负的循环节．由此，可以得到一系列关于阶的性质．

欧拉定理 中，同余关系 $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$ 对于所有 $a⟂m$ 都成立．结合 性质 2，这说明对于所有 $a⟂m$，都有 ${\delta }_m(a)\mid \phi (m)$．换句话说，$\phi (m)$ 是所有 $a⟂m$ 的阶的一个公倍数．对于一个正整数 $m$，所有 $a⟂m$ 的阶 ${\delta }_m(a)$ 的最小公倍数，记作 $\lambda (m)$，就是 $m$ 的 Carmichael 函数．后文会详细讨论它的性质．

和其他的循环结构类似，可以根据 $a$ 的阶计算 $a^k$ 的阶．

性质 3

对于 $k,a\in \mathbf{Z},m\in {\mathbf{N}}_{+}$ 且 $a⟂m$，有

$${\delta }_m(a^k)=\frac{{\delta }_m(a)}{({\delta }_m(a),k)}.$$

证明

由 性质 2，同余关系 $(a^k{)}^n=a^{kn}\equiv 1(\mathrm{mod}m)$ 成立，当且仅当 ${\delta }_m(a)\mid kn$．这一条件就等价于

$$\frac{{\delta }_m(a)}{({\delta }_m(a),k)}\mid n.$$

使得这一条件成立的最小正整数就是

$${\delta }_m(a^k)=\frac{{\delta }_m(a)}{({\delta }_m(a),k)}.$$

乘积的阶

设 $a,b$ 是与 $m$ 互素的不同整数．如果已知阶 ${\delta }_m(a)$ 和 ${\delta }_m(b)$，那么，同样可以获得一些关于它们乘积 $ab$ 的阶 ${\delta }_m(ab)$ 的信息．

性质 4

对于 $a,b\in \mathbf{Z},m\in {\mathbf{N}}_{+}$ 且 $a,b⟂m$，那么，有

$$\frac{[{\delta }_m(a),{\delta }_m(b)]}{({\delta }_m(a),{\delta }_m(b))}\mid {\delta }_m(ab)\mid [{\delta }_m(a),{\delta }_m(b)].$$

证明

因为 $[{\delta }_m(a),{\delta }_m(b)]$ 是 ${\delta }_m(a)$ 和 ${\delta }_m(b)$ 的倍数，所以，由 性质 2 可知

$$(ab{)}^{[{\delta }_m(a),{\delta }_m(b)]}=a^{[{\delta }_m(a),{\delta }_m(b)]}{b}^{[{\delta }_m(a),{\delta }_m(b)]}\equiv 1(\mathrm{mod}m).$$

再次应用性质 2，就得到

$${\delta }_m(ab)\mid [{\delta }_m(a),{\delta }_m(b)].$$

这就得到右侧的整除关系．

反过来，由于

$$1\equiv (ab{)}^{{\delta }_m(ab){\delta }_m(b)}\equiv a^{{\delta }_m(ab){\delta }_m(b)}(\mathrm{mod}m),$$

所以，应用性质 2，就得到 ${\delta }_m(a)\mid {\delta }_m(ab){\delta }_m(b)$．两侧消去 $({\delta }_m(a),{\delta }_m(b))$，就得到

$$\frac{{\delta }_m(a)}{({\delta }_m(a),{\delta }_m(b))}\mid {\delta }_m(ab)\frac{{\delta }_m(b)}{({\delta }_m(a),{\delta }_m(b))}.$$

消去公因子后，两个分式互素，这就得到

$$\frac{{\delta }_m(a)}{({\delta }_m(a),{\delta }_m(b))}\mid {\delta }_m(ab).$$

同理，也有

$$\frac{{\delta }_m(b)}{({\delta }_m(a),{\delta }_m(b))}\mid {\delta }_m(ab).$$

由于两个整除关系的左侧互素，有

$$\frac{[{\delta }_m(a),{\delta }_m(b)]}{({\delta }_m(a),{\delta }_m(b))}=\frac{{\delta }_m(a){\delta }_m(b)}{({\delta }_m(a),{\delta }_m(b){)}^2}\mid {\delta }_m(ab).$$

这就得到左侧的整除关系．

对于 $a$ 和 $b$ 的阶互素的情形，这一结论有着更为简单的形式．

性质 4'

对于 $a,b\in \mathbf{Z},m\in {\mathbf{N}}_{+}$ 且 $a,b⟂m$，那么，有

$${\delta }_m(ab)={\delta }_m(a){\delta }_m(b)⟺{\delta }_m(a)⟂{\delta }_m(b).$$

证明

如果 ${\delta }_m(a)⟂{\delta }_m(b)$，那么 性质 4 中所有整除关系都是等式，所以有

$${\delta }_m(ab)=[{\delta }_m(a),{\delta }_m(b)]={\delta }_m(a){\delta }_m(b).$$

反过来，如果 ${\delta }_m(ab)={\delta }_m(a){\delta }_m(b)$，那么根据性质 4，就有

$${\delta }_m(a){\delta }_m(b)={\delta }_m(ab)\mid [{\delta }_m(a),{\delta }_m(b)].$$

这立马说明 $({\delta }_m(a),{\delta }_m(b))=1$，即 ${\delta }_m(a)⟂{\delta }_m(b)$．

一般情形中，性质 4 得到的界已经是紧的．乘积的阶取得下界的情形很容易构造：例如 $(a,b,m)=(3,5,7)$ 时，${\delta }_m(a)={\delta }_m(b)=6$，但是它们的乘积的阶 ${\delta }_m(ab)=1$．

尽管一般情形中，乘积 $ab$ 的阶未必是它们的阶的最小公倍数，但是总能找到一个元素使得它的阶等于这个最小公倍数．

性质 5

对于 $a,b\in \mathbf{Z},m\in {\mathbf{N}}_{+}$ 且 $a,b⟂m$，总是存在 $c\in \mathbf{Z}$ 且 $c⟂m$ 使得

$${\delta }_m(c)=[{\delta }_m(a),{\delta }_m(b)].$$

证明

考虑素因数分解：

$${\delta }_m(a)=\prod _p{p}^{{\alpha }_p},{\delta }_m(b)=\prod _p{p}^{{\beta }_p}.$$

利用 ${\alpha }_p$ 和 ${\beta }_p$ 的大小关系，可以将所有素因子分为两类：

由此，分别设

$${\gamma }_A=\prod _{p\in A}{p}^{{\alpha }_p},{\gamma }_B=\prod _{p\in B}{p}^{{\alpha }_p},{\eta }_A=\prod _{p\in A}{p}^{{\beta }_p},{\eta }_B=\prod _{p\in B}{p}^{{\beta }_p},$$

就有 ${\delta }_m(a)={\gamma }_A{\gamma }_B$ 和 ${\delta }_m(b)={\eta }_A{\eta }_B$．根据 性质 3，可知

因为 ${\gamma }_A⟂{\eta }_B$，由 性质 4'，就有

$${\delta }_m(a^{{\gamma }_B}{b}^{{\eta }_A})={\gamma }_A{\eta }_B=\prod _p{p}^{max\{{\alpha }_p,{\beta }_p\}}=[{\delta }_m(a),{\delta }_m(b)].$$

因此，$c=a^{{\gamma }_B}{b}^{{\eta }_A}$ 就是阶为 $[{\delta }_m(a),{\delta }_m(b)]$ 的元素．

这一结论常用于构造出指定阶的元素．

原根

原根是一些特殊元素——它的阶就等于所有模 $m$ 既约剩余系的个数．

并非所有正整数 $m$ 都存在模 $m$ 的原根．由上文的 性质 1，如果模 $m$ 的原根 $g$ 存在，那么，$g,g^2,\cdots ,g^{\phi (m)}$ 所在的同余类互不相同，构成模 $m$ 既约剩余系．特别地，对于素数 $p$，余数 对于 $i=1,2,\cdots ,p-1$ 两两不同．

模为 $1$ 时，模 $1$ 整数乘法群就是 $\{0\}$．这显然是循环群，所以原根就是 $0$．

原根判定定理

如果已知模数 $\phi (m)$ 的全体素因子，那么很容易判断模 $m$ 的原根是否存在．

定理

对于整数 $m\ge 3$ 和 $g⟂m$，那么，$g$ 是模 $m$ 的原根，当且仅当对于 $\phi (m)$ 的每个素因数 $p$，都有

$$g^{\frac{\phi (m)}{p}}\not\equiv 1(\mathrm{mod}m).$$

证明

必要性显然．为证明充分性，考虑使用反证法．如果 $g$ 不是模 $m$ 的原根，那么一定有 ．由 性质 2 和欧拉定理可知，${\delta }_m(g)\mid \phi (m)$．由此，设 $p$ 是 ${\displaystyle \frac{\phi (m)}{{\delta }_m(g)}}$ 的一个素因子，就有 ${\delta }_m(g)\mid {\displaystyle \frac{\phi (m)}{p}}$．再次应用性质 2 就得到

$$g^{\frac{\phi (m)}{p}}\equiv 1(\mathrm{mod}m).$$

但是，$p$ 也是 $\phi (m)$ 的一个因子，这就与题设条件矛盾．由此，原命题的充分性成立．

原根个数

原根如果存在，也未必唯一．一般地，对于模 $m$ 既约剩余系中所有元素可能的阶和某个阶的元素数量，有如下结论：

证明

根据原根的定义，所有模 $m$ 的既约同余类都可以写作 的形式，且 $k$ 是 $1,2,\cdots ,\phi (m)$ 之一．由 性质 3，这些元素的阶等于

$${\delta }_m(g^k)=\frac{\phi (m)}{(\phi (m),k)}.$$

因此，$d$ 阶元素存在，当且仅当 $d\mid \phi (m)$．而且，对于 $d\mid \phi (m)$，令 $d^{\prime }=\phi (m)/d$，这些元素的集合就是

这些元素对应的 $k^{\prime }=k/d^{\prime }$ 恰为那些不超过 $d$ 且与 $d$ 互素的正整数．由欧拉函数的定义，这就是 $\phi (d)$．

原根存在定理

本节将建立如下原根存在定理：

为说明这一结论，需要分别讨论如下四种情形：

1. $m=1,2,4$，原根分别是 $g=0,1,3$，显然存在．

2. $m=p^e$ 是奇素数的幂，其中，$p$ 为奇素数，$e\in {\mathbf{N}}_{+}$．

   引理 1

   对于奇素数 $p$，模 $p$ 的原根存在．

   证明

   证明分为两步．

   第一步：对于 $d\mid (p-1)$，同余方程 $x^d\equiv 1(\mathrm{mod}p)$ 恰有 $d$ 个互不相同的解．

   令 $p-1=kd$，多项式

   $$f(x)=x^{d(k-1)}+x^{d(k-2)}+\cdots +x^d+1.$$

   根据 欧拉定理，同余方程 $(x^d-1)f(x)=x^{p-1}-1\equiv 0(\mathrm{mod}p)$ 恰有 $p-1$ 个互不相同的解．这些解分别是 $x^d-1$ 和 $f(x)$ 的零点．由 Lagrange 定理，它们分别至多只能有 $d$ 个和 $d(k-1)$ 个互不相同的零点．由于 $d+d(k-1)=p-1$，前者只能恰好有 $d$ 个互不相同的零点．这说明同余方程 $x^d\equiv 1(\mathrm{mod}p)$ 恰有 $d$ 个互不相同的解．

   第二步：对于 $d\mid (p-1)$，$d$ 阶元素恰好有 $\phi (d)$ 个．

   对于 $\phi (p)$ 的所有因子排序，然后应用归纳法．因为 $1$ 阶元素只能是 $1$，只有一个，归纳起点成立．对于 $d\mid (p-1)$，根据前文的 性质 2，同余方程 $x^d\equiv 1(\mathrm{mod}p)$ 的解一定满足 ${\delta }_p(x)\mid d$．因此，其中 $d$ 阶元素个数为

   $$N(d)=d-\sum _{e\mid d,e\ne d}N(e)=d-\sum _{e\mid d,e\ne d}\phi (e)=\phi (d).$$

   第二个等号是归纳假设，第三个等号是欧拉函数的性质．由数学归纳法，就知道对于所有 $d\mid (p-1)$，都恰有 $\phi (d)$ 个 $d$ 阶元素．

   特别地，对于 $d=p-1$，恰有 $\phi (p-1)$ 个 $(p-1)$ 阶元素．因此，模 $p$ 的原根存在．

   引理 2

   对于奇素数 $p$ 和 $e\in {\mathbf{N}}_{+}$，模 $p^e$ 的原根存在．

   证明

   证明分为三步．

   第一步：存在模 $p$ 的原根 $g$，使得 $g^{p-1}\not\equiv 1(\mathrm{mod}{p}^2)$．

   任取一个模 $p$ 的原根 $g$．如果它不符合条件，即 $g^{p-1}\equiv 1(\mathrm{mod}{p}^2)$，那么，可以证明 $g+p$ 符合条件：$g+p$ 也是模 $p$ 的原根，且

   

   第二步：上文选取的 $g$，对于任意 $e\ge 1$，都有 $g^{\phi (p^e)}\not\equiv 1(\mathrm{mod}{p}^{e+1})$．

   对 $g$ 的选取保证了 $e=1$ 时，该式成立．假设该式对于 $e$ 的情形成立，现要证明 $e+1$ 的情形也成立．对于任意 $e\ge 1$，由欧拉定理可知，存在 $\lambda$ 使得

   $$g^{\phi (p^e)}=1+\lambda p^e$$

   成立．由归纳假设，$\lambda ⟂p$．因为 $\phi (p^{e+1})=p\phi (p^e)$，所以

   $$g^{\phi (p^{e+1})}={\left(g^{\phi (p^e)}\right)}^p=(1+\lambda p^e{)}^p\equiv 1+\lambda p^{e+1}(\mathrm{mod}{p}^{e+2}).$$

   结合 $\lambda ⟂p$ 可知，$g^{\phi (p^{e+1})}\not\equiv 1(\mathrm{mod}{p}^{e+2})$．由数学归纳法可知，命题成立．

   第三步：上文选取的 $g$，对于任意 $e\ge 1$，都是模 $p^e$ 的原根．

   对 $g$ 的选取保证了 $e=1$ 时，命题成立．假设命题对于 $e$ 成立，现在要证明命题对于 $e+1$ 也成立．将 ${\delta }_{p^{e+1}}(g)$ 简记为 $\delta$．由于 $g^{\delta }\equiv 1(\mathrm{mod}{p}^{e+1})$，必然也有 $g^{\delta }\equiv 1(\mathrm{mod}{p}^e)$．由归纳假设可知，${\delta }_{p^e}(g)=\phi (p^e)$．因此，由前文阶的 性质 2，就有 $\phi (p^e)\mid \delta$．又由欧拉定理可知，$\delta \mid \phi (p^{e+1})$．但是，$\phi (p^{e+1})=p\phi (p^e)$．因此，只有两种可能：$\delta =\phi (p^e)$ 或 $\delta =\phi (p^{e+1})$．但是，第二步的结论说明，$g^{\phi (p^e)}\not\equiv 1(\mathrm{mod}{p}^{e+1})$．因此，可能性 $\delta =\phi (p^e)$ 并不成立．唯一的可能性就是 $\delta =\phi (p^{e+1})$．这就说明 $g$ 是 $p^{e+1}$ 的原根．由数学归纳法，命题对于所有 $e\ge 1$ 都成立．

3. $m=2p^e$，其中，$p$ 为奇素数，$e\in {\mathbf{N}}_{+}$．

   引理 3

   对于奇素数 $p$ 和 $e\in {\mathbf{N}}_{+}$，模 $2p^e$ 的原根存在．

   证明

   设 $g$ 是模 $p^e$ 的原根，则 $g+p^e$ 也是模 $p^e$ 的原根．两者之间必然有一个是奇数，不妨设它就是 $g$．显然，$(g,2p^e)=1$．设 $\delta ={\delta }_{2p^e}(g)$，需要证明 $\delta =\phi (2p^e)$．由欧拉定理，$\delta \mid \phi (2p^e)$．同时，根据定义 $g^{\delta }\equiv 1(\mathrm{mod}2p^e)$，所以，$g^{\delta }\equiv 1(\mathrm{mod}{p}^e)$，因此，由阶的 性质 2 和 $g$ 的选取可知，${\delta }_{p^e}(g)=\phi (p^e)\mid \delta$．由欧拉函数表达式可知，$\phi (2p^e)=\phi (p^e)$．所以，$\delta ={\delta }_{2p^e}(g)=\phi (p^e)$．这就说明 $\delta$ 是模 $2p^e$ 的原根．

4. $m\ne 1,2,4,p^e,2p^e$，其中，$p$ 为奇素数，$e\in {\mathbf{N}}_{+}$．

   引理 4

   假设 $m\ne 1,2,4$ 且不存在奇素数 $p$ 和正整数 $e$ 使得 $m=p^e$ 或 $m=2p^e$．那么，模 $m$ 的原根不存在．

   证明

   对于 $m=2^e$ 且 $e\ge 3$，假设模 $m$ 的原根 $g$ 存在．由于 $g⟂m$，它一定是奇数．假设 $g=2k+1$ 且 $k\in \mathbf{N}$，那么，有

   

   倒数第二行中，因为 $k$ 与 $(2^{e-2}-1)k^2$ 奇偶性相同，所以它们的和是偶数．由阶的定义可知，．这与假设中 $g$ 是原根矛盾．由反证法，这样的原根并不存在．

   假设 $m$ 满足所述条件，且不是 $2$ 的幂，那么，一定存在 且 $m_1⟂m_2$ 使得 $m=m_1{m}_2$ 成立．假设模 $m$ 的原根 $g$ 存在．因为 $g⟂m$，所以对于 $i=1,2$，都有 $g⟂m_i$．由欧拉定理可知，

   $$g^{\phi (m_i)}\equiv 1(\mathrm{mod}{m}_i).$$

   由于 ，所以 $\phi (m_i)$ 为偶数，所以，对于 $i=1,2$，有

   $$g^{\frac{1}{2}\phi (m_1)\phi (m_2)}\equiv 1(\mathrm{mod}{m}_i).$$

   由 中国剩余定理 可知

   $$g^{\frac{1}{2}\phi (m_1)\phi (m_2)}\equiv 1(\mathrm{mod}m).$$

   又因为 $\phi (m)=\phi (m_1)\phi (m_2)$，所以由阶的定义可知

   

   这与 $g$ 是模 $m$ 的原根的假设矛盾．故而，由反证法知，模 $m$ 的原根不存在．

综合以上四个引理，我们便给出了一个数存在原根的充要条件．

求原根的算法

对于任何存在原根的模数 $m$，要求得它的原根 $g$，只需要枚举可能的正整数，并逐个判断它是否为原根即可．枚举时，通常有两种处理方式：从小到大逐一枚举、随机生成一些正整数．这两种枚举方式的实际效率相当．

从小到大逐一枚举时，得到的是模 $m$ 的最小原根 $g_m$，因此，枚举部分的复杂度取决于 $g_m$ 的大小．对此，有如下估计：

• 上界的估计：王元⁵和 Burgess⁶证明了素数 $p$ 的最小原根 $g_p=O\left(p^{0.25+ϵ}\right)$，其中 ．Cohen, Odoni, and Stothers⁷和 Elliott and Murata⁸分别证明了该估计对于模数 $p^2$ 和 $2p^2$ 也成立，其中，$p$ 是奇素数．由于对于 ，模 $p^2$（或 $2p^2$）的原根也是模 $p^e$（或 $2p^e$）的原根，所以，最小原根的上界 $O\left(p^{0.25+ϵ}\right)$ 对于所有情形都成立．
• 下界的估计：Fridlander⁹和 Salié¹⁰证明了存在 ，使得对于无穷多素数 $p$，都有最小原根 成立．
• 平均情形的估计：Burgess and Elliott¹¹证明了平均情形下素数 $p$ 的最小原根 $g_p=O((\log p{)}^2(\log \log p{)}^4)$．Elliott and Murata¹²进一步猜想素数 $p$ 的最小原根的平均值是一个常数，且通过数值验证¹³得到它大概为 $4.926$．随后，Elliott and Murata⁸将这一猜想推广到模 $2p^2$ 的情形．

根据这些分析，暴力寻找最小原根时，枚举部分的复杂度 $O(g_m(\log m{)}^2)$ 是可以接受的．

除了从小到大枚举外，还可以通过随机生成正整数并验证的方法寻找原根．原根的密度并不低：¹

$$\frac{\phi (\phi (m))}{m}=\mathrm{\Omega }\left(\frac{1}{\log \log m}\right).$$

所以，通过随机方法寻找原根时，枚举部分的期望复杂度为 $O((\log m{)}^2\log \log m)$．

需要注意的是，判定原根时需要已知 $\phi (m)$ 的质因数分解．算法竞赛 常用质因数分解算法 中，复杂度最优的 Phollard Rho 算法也需要 $O(m^{1/4+\epsilon })$ 的时间．因此，只要 $\phi (m)$ 的质因数分解是未知的，无论采用哪种枚举方式，求原根的复杂度瓶颈都在于质因数分解这一步，而非枚举验证的部分．

Carmichael 函数

相对于模 $m$ 元素的阶这一局部概念，Carmichael 函数是一个全局概念．它是所有与 $m$ 互素的整数的幂次的最小公共循环节．

根据 性质 2，能够使得 $a^n\equiv 1(\mathrm{mod}m)$ 对于所有 $a⟂m$ 都成立，意味着 ${\delta }_m(a)\mid n$ 对于所有 $a⟂m$ 都成立．也就是说，符合这一条件的正整数 $n$，一定是全体 ${\delta }_m(a)$ 的公倍数．因此，最小的这样的 $n$ 就是它们的最小公倍数：

$$\lambda (m)=\mathrm{lcm}\{{\delta }_m(a):a⟂m\}.$$

这也常用作 Carmichael 函数的等价定义．

反复应用 性质 5 可知，一定存在某个元素 $a⟂m$ 使得 ${\delta }_m(a)=\lambda (m)$．因此，上式也可以写作

$$\lambda (m)=max\{{\delta }_m(a):a⟂m\}.$$

取得这一最值的元素 $a⟂m$ 也称为模 $m$ 的 $\lambda$‑原根．它对于所有模数 $m$ 都存在．

递推公式

Carmichael 函数是一个 数论函数．本节讨论它的一个递推公式，并由此给出原根存在定理的另一个证明．

虽然不是积性函数，但是计算 Carmichael 函数时，同样可以对互素的因子分别处理．

因此，接下来只要计算 Carmichael 函数在素数幂处的取值．首先，处理 $2$ 的幂次的情形．

证明

对于 $m=2,4$ 的情形，单独讨论即可．对于 $m=2^e$ 且 $e\ge 3$ 的情形，首先重复前文 引理 4 的证明的第一部分，就得到 $\lambda (m)\le 2^{e-2}$．进而，只需要证明存在 $2^{e-2}$ 阶元素即可．为此，有

$$5^{2^{e-3}}=(1+2^2{)}^{2^{e-3}}=1+2^2\times 2^{e-3}=1+2^{e-1}\not\equiv 1(\mathrm{mod}{2}^e).$$

这说明 ${\delta }_m(5)\nmid 2^{e-3}$，又因为 ${\delta }_m(5)\mid 2^{e-2}$，所以，$5$ 只能是 $2^{e-2}$ 阶元素．这就说明，$\lambda (m)=2^{e-2}$．

在这个引理的证明过程中，实际上得到了关于模 $2^e$ 既约剩余系结构的刻画：

然后，处理奇素数幂的情形．

证明

首先证明命题对于 $e=1$，即 $m=p$ 是奇素数的情形成立．为此，由 Carmichael 函数的定义可知，与 $p$ 互素的所有整数 $a$ 都是同余方程 $x^{\lambda (p)}\equiv 1(\mathrm{mod}p)$ 的解．在模 $p$ 的意义下，该方程共有 $p-1$ 个互不相同的解．根据 Lagrange 定理 可知，$p-1\le \lambda (p)$．同时，欧拉定理要求，$\lambda (p)\mid \phi (p)=p-1$．因此，$\lambda (p)=p-1$．

对于 $m=p^e$ 且 的情形，可以从证明 $1+p$ 是 $p^{e-1}$ 阶元开始．为此，有

$$(1+p{)}^{p^{e-1}}\equiv 1,(1+p{)}^{p^{e-2}}\equiv 1+p^{e-1}\not\equiv 1(\mathrm{mod}{p}^e).$$

所以，${\delta }_m(1+p)=p^{e-1}$．另外，设模 $p$ 的原根为 $g$，那么，由于 $g^{{\delta }_m(g)}\equiv 1(\mathrm{mod}p)$，所以，由阶的 性质 2 可知，$p-1\mid {\delta }_m(p)$．由 Carmichael 函数的定义和欧拉定理可知

$$p^{e-1}(p-1)=[{\delta }_m(p),p^{e-1}]\mid \lambda (m)\mid \phi (m)=p^{e-1}(p-1).$$

因此，$\lambda (m)=p^{e-1}(p-1)$．

将本节的结果简单归纳，就得到 Carmichael 函数的递推公式：

定理

对于任意正整数 $m$，有

利用该递推公式可以加强前文的结果：

比较原根和 Carmichael 函数的定义可知，模 $m$ 的原根存在，当且仅当 $\lambda (m)=\phi (m)$．从 Carmichael 函数的递推公式中，容易归纳出如下结果：

由于本节对于递推公式的证明并没有用到原根存在定理，因此，这就构成了对该定理的又一个证明．

Carmichael 数

利用 Carmichael 函数，可以讨论 Carmichael 数（卡迈克尔数，OEIS:A002997）的性质与分布．这是 Fermat 素性测试 一定无法正确排除的合数．

最小的 Carmichael 数是 $561=3\times 11\times 17$．

由 Carmichael 函数的定义可知，合数 $n$ 是 Carmichael 数当且仅当 $\lambda (n)\mid n-1$，其中 $\lambda (n)$ 为 Carmichael 函数．进一步地，可以得到如下判断合数 $n$ 是否为 Carmichael 数的方法：

从这一判别法出发，可以建立 Carmichael 数的一些简单性质：

证明

前两条性质可以直接从 Korselt 判别法及其证明中得到．要得到第三条性质，只需要再证明：互异素数 $p_1,p_2$ 的乘积 $n=p_1{p}_2$ 一定不是 Carmichael 数．假设 $n=p_1{p}_2$ 是 Carmichael 数．由 Korselt 判别法可知，$(p_i-1)\mid (n-1)$．但是，有

$$n-1=p_1{p}_2-1\equiv p_2-1(\mathrm{mod}{p}_1-1).$$

因此，$(p_1-1)\mid (p_2-1)$．同理，$(p_2-1)\mid (p_1-1)$．也就是说，$p_1=p_2$．这与假设矛盾．因此，Carmichael 数 $n$ 至少有 $3$ 个互异素因子．

利用解析数论还可以得到 Carmichael 数分布的一些性质．设 $C(n)$ 为小于等于 $n$ 的 Carmichael 数个数．Alford, Granville, and Pomerance²证明，对于充分大的 $n$，有 ．由此，Carmichael 数有无限多个．在这之前，Erdős³已经证明，，其中 $c$ 为常数．因此，Carmichael 数的分布（相对于素数来说）十分稀疏．实际上，有⁴ $C({10}^9)=646$，$C({10}^{18})=1401644$．

参考资料与注释

• Primitive root modulo n - Wikipedia
• The order of a unit - Course Notes
• The primitive root theorem - Amin Witno's notes
• Carmichael function - Wikipedia
• Carmichael's Lambda Function - Brilliant Math & Science Wiki
• Carmichael number - Wikipedia
• Carmichael Number - Wolfram MathWorld

本页面最近更新：2025/10/29 21:16:33，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Peanut-Tang, Early0v0, c-forrest, Ir1d, Tiphereth-A, StudyingFather, Great-designer, MegaOwIer, Xeonacid, 2008verser, Enter-tainer, bobhan1, CCXXXI, chuxin0816, CroMarmot, GavinZhengOI, GeorgePlover, hhc0001, huhaoo, Larry0716, Marcythm, opsiff, ouuan, PeterlitsZo, ShelpAm, tml104, wty-yy
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用