跳转至

# 阶 & 原根

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

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

## 阶

本节中，总是假设模数 𝑚 ∈𝐍+m∈N+ 和底数 𝑎 ∈𝐙 a∈Z 互素，即 (𝑎,𝑚) =1(a,m)=1，也记作 𝑎 ⟂𝑚 a⟂m．

对于 𝑛 ∈𝐙 n∈Z，幂次 𝑎 𝑛 m o d 𝑚 a n mod m 呈现一种循环结构．这个循环节的最小长度，就是 𝑎 a 模 𝑚 m 的阶．阶就定义为幂 𝑎 𝑛 m o d 𝑚 a n mod m 第一次回到起点 𝑎 0 m o d 𝑚 =1 a 0 mod m=1 时的指数：

阶

对于 𝑎 ∈𝐙,𝑚 ∈𝐍+a∈Z,m∈N+ 且 𝑎 ⟂𝑚 a⟂m，满足同余式 𝑎 𝑛 ≡1(m o d 𝑚)a n≡1(mod m) 的最小正整数 𝑛 n 称作 𝑎 a 模 𝑚 m 的阶（the order of 𝑎 a modulo 𝑚 m），记作 𝛿 𝑚(𝑎)δ m(a) 或 o r d 𝑚⁡(𝑎)ord m⁡(a)．

注

在 抽象代数 中，这里的「阶」就是模 𝑚 m 既约剩余系关于乘法形成的群中，元素 𝑎 a 的阶．用记号 𝛿 δ 表示阶只适用于这个特殊的群．下面的诸多性质可以直接推广到抽象代数中群元素的阶的性质．

另外还有「半阶」的概念，在数论中会用 𝛿−δ− 记号表示．它是满足同余式 𝑎 𝑛 ≡ −1(m o d 𝑚)a n≡−1(mod m) 的最小正整数．半阶不是群论中的概念．阶一定存在，半阶不一定存在．

### 幂的循环结构

利用阶，可以刻画幂的循环结构．对于幂 𝑎 𝑛 m o d 𝑚 a n mod m，可以将指数 𝑛 n 对阶 𝛿 𝑚(𝑎)δ m(a) 做带余除法：

𝑛=𝛿 𝑚(𝑎)𝑞+𝑟, 0≤𝑟<𝛿 𝑚(𝑎).n=δ m(a)q+r, 0≤r<δ m(a).

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

𝑎 𝑛=𝑎 𝛿 𝑚(𝑎)𝑞+𝑟=(𝑎 𝛿 𝑚(𝑎))𝑞⋅𝑎 𝑟≡𝑎 𝑟(m o d 𝑚).a n=a δ m(a)q+r=(a δ m(a))q⋅a r≡a r(mod m).

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

性质 1

对于 𝑎 ∈𝐙,𝑚 ∈𝐍+a∈Z,m∈N+ 且 𝑎 ⟂𝑚 a⟂m，幂次 𝑎 0( =1),𝑎,𝑎 2,⋯,𝑎 𝛿 𝑚(𝑎)−1 a 0(=1),a,a 2,⋯,a δ m(a)−1 模 𝑚 m 两两不同余．

证明

考虑反证．假设存在两个数 0 ≤𝑖 <𝑗 <𝛿 𝑚(𝑎)0≤i<j<δ m(a)，且 𝑎 𝑖 ≡𝑎 𝑗(m o d 𝑚)a i≡a j(mod m)，则有 𝑎 𝑗−𝑖 ≡1(m o d 𝑚)a j−i≡1(mod m)．但是，0 <𝑗 −𝑖 <𝛿 𝑚(𝑎)0<j−i<δ m(a)．这与阶的最小性矛盾，故原命题成立．

性质 2

对于 𝑎,𝑛 ∈𝐙,𝑚 ∈𝐍+a,n∈Z,m∈N+ 且 𝑎 ⟂𝑚 a⟂m，同余关系 𝑎 𝑛 ≡1(m o d 𝑚)a n≡1(mod m) 成立，当且仅当 𝛿 𝑚(𝑎) ∣𝑛 δ m(a)∣n．

证明

如前文所述，𝑎 𝑛 ≡𝑎 𝑛 m o d 𝛿 𝑚(𝑎)(m o d 𝑚)a n≡a n mod δ m(a)(mod m)．由 性质 1 可知，0 ≤𝑟 <𝛿 𝑚(𝑎)0≤r<δ m(a) 中唯一一个使得 𝑎 𝑟 ≡1(m o d 𝑚)a r≡1(mod m) 成立的 𝑟 r 就是 𝑟 =0 r=0．因此，𝑎 𝑛 ≡1(m o d 𝑚)a n≡1(mod m)，当且仅当 𝑛 m o d 𝛿 𝑚(𝑎) =0 n mod δ m(a)=0，也就是 𝛿 𝑚(𝑎) ∣𝑛 δ m(a)∣n．

欧拉定理 中，同余关系 𝑎 𝜑(𝑚) ≡1(m o d 𝑚)a φ(m)≡1(mod m) 对于所有 𝑎 ⟂𝑚 a⟂m 都成立．结合 性质 2，这说明对于所有 𝑎 ⟂𝑚 a⟂m，都有 𝛿 𝑚(𝑎) ∣𝜑(𝑚)δ m(a)∣φ(m)．换句话说，𝜑(𝑚)φ(m) 是所有 𝑎 ⟂𝑚 a⟂m 的阶的一个公倍数．对于一个正整数 𝑚 m，所有 𝑎 ⟂𝑚 a⟂m 的阶 𝛿 𝑚(𝑎)δ m(a) 的最小公倍数，记作 𝜆(𝑚)λ(m)，就是 𝑚 m 的 Carmichael 函数．后文会详细讨论它的性质．

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

性质 3

对于 𝑘,𝑎 ∈𝐙,𝑚 ∈𝐍+k,a∈Z,m∈N+ 且 𝑎 ⟂𝑚 a⟂m，有

𝛿 𝑚(𝑎 𝑘)=𝛿 𝑚(𝑎)(𝛿 𝑚(𝑎),𝑘).δ m(a k)=δ m(a)(δ m(a),k).
证明

由 性质 2，同余关系 (𝑎 𝑘)𝑛 =𝑎 𝑘 𝑛 ≡1(m o d 𝑚)(a k)n=a k n≡1(mod m) 成立，当且仅当 𝛿 𝑚(𝑎) ∣𝑘 𝑛 δ m(a)∣k n．这一条件就等价于

𝛿 𝑚(𝑎)(𝛿 𝑚(𝑎),𝑘)∣𝑛.δ m(a)(δ m(a),k)∣n.

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

𝛿 𝑚(𝑎 𝑘)=𝛿 𝑚(𝑎)(𝛿 𝑚(𝑎),𝑘).δ m(a k)=δ m(a)(δ m(a),k).

### 乘积的阶

设 𝑎,𝑏 a,b 是与 𝑚 m 互素的不同整数．如果已知阶 𝛿 𝑚(𝑎)δ m(a) 和 𝛿 𝑚(𝑏)δ m(b)，那么，同样可以获得一些关于它们乘积 𝑎 𝑏 a b 的阶 𝛿 𝑚(𝑎 𝑏)δ m(a b) 的信息．

性质 4

对于 𝑎,𝑏 ∈𝐙,𝑚 ∈𝐍+a,b∈Z,m∈N+ 且 𝑎,𝑏 ⟂𝑚 a,b⟂m，那么，有

[𝛿 𝑚(𝑎),𝛿 𝑚(𝑏)](𝛿 𝑚(𝑎),𝛿 𝑚(𝑏))∣𝛿 𝑚(𝑎 𝑏)∣[𝛿 𝑚(𝑎),𝛿 𝑚(𝑏)].[δ m(a),δ m(b)](δ m(a),δ m(b))∣δ m(a b)∣[δ m(a),δ m(b)].
证明

因为 [𝛿 𝑚(𝑎),𝛿 𝑚(𝑏)][δ m(a),δ m(b)] 是 𝛿 𝑚(𝑎)δ m(a) 和 𝛿 𝑚(𝑏)δ m(b) 的倍数，所以，由 性质 2 可知

(𝑎 𝑏)[𝛿 𝑚(𝑎),𝛿 𝑚(𝑏)]=𝑎[𝛿 𝑚(𝑎),𝛿 𝑚(𝑏)]𝑏[𝛿 𝑚(𝑎),𝛿 𝑚(𝑏)]≡1(m o d 𝑚).(a b)[δ m(a),δ m(b)]=a[δ m(a),δ m(b)]b[δ m(a),δ m(b)]≡1(mod m).

再次应用性质 2，就得到

𝛿 𝑚(𝑎 𝑏)∣[𝛿 𝑚(𝑎),𝛿 𝑚(𝑏)].δ m(a b)∣[δ m(a),δ m(b)].

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

反过来，由于

1≡(𝑎 𝑏)𝛿 𝑚(𝑎 𝑏)𝛿 𝑚(𝑏)≡𝑎 𝛿 𝑚(𝑎 𝑏)𝛿 𝑚(𝑏)(m o d 𝑚),1≡(a b)δ m(a b)δ m(b)≡a δ m(a b)δ m(b)(mod m),

所以，应用性质 2，就得到 𝛿 𝑚(𝑎) ∣𝛿 𝑚(𝑎 𝑏)𝛿 𝑚(𝑏)δ m(a)∣δ m(a b)δ m(b)．两侧消去 (𝛿 𝑚(𝑎),𝛿 𝑚(𝑏))(δ m(a),δ m(b))，就得到

𝛿 𝑚(𝑎)(𝛿 𝑚(𝑎),𝛿 𝑚(𝑏))∣𝛿 𝑚(𝑎 𝑏)𝛿 𝑚(𝑏)(𝛿 𝑚(𝑎),𝛿 𝑚(𝑏)).δ m(a)(δ m(a),δ m(b))∣δ m(a b)δ m(b)(δ m(a),δ m(b)).

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

𝛿 𝑚(𝑎)(𝛿 𝑚(𝑎),𝛿 𝑚(𝑏))∣𝛿 𝑚(𝑎 𝑏).δ m(a)(δ m(a),δ m(b))∣δ m(a b).

同理，也有

𝛿 𝑚(𝑏)(𝛿 𝑚(𝑎),𝛿 𝑚(𝑏))∣𝛿 𝑚(𝑎 𝑏).δ m(b)(δ m(a),δ m(b))∣δ m(a b).

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

[𝛿 𝑚(𝑎),𝛿 𝑚(𝑏)](𝛿 𝑚(𝑎),𝛿 𝑚(𝑏))=𝛿 𝑚(𝑎)𝛿 𝑚(𝑏)(𝛿 𝑚(𝑎),𝛿 𝑚(𝑏))2∣𝛿 𝑚(𝑎 𝑏).[δ m(a),δ m(b)](δ m(a),δ m(b))=δ m(a)δ m(b)(δ m(a),δ m(b))2∣δ m(a b).

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

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

性质 4'

对于 𝑎,𝑏 ∈𝐙,𝑚 ∈𝐍+a,b∈Z,m∈N+ 且 𝑎,𝑏 ⟂𝑚 a,b⟂m，那么，有

𝛿 𝑚(𝑎 𝑏)=𝛿 𝑚(𝑎)𝛿 𝑚(𝑏)⟺𝛿 𝑚(𝑎)⟂𝛿 𝑚(𝑏).δ m(a b)=δ m(a)δ m(b)⟺δ m(a)⟂δ m(b).
证明

如果 𝛿 𝑚(𝑎) ⟂𝛿 𝑚(𝑏)δ m(a)⟂δ m(b)，那么 性质 4 中所有整除关系都是等式，所以有

𝛿 𝑚(𝑎 𝑏)=[𝛿 𝑚(𝑎),𝛿 𝑚(𝑏)]=𝛿 𝑚(𝑎)𝛿 𝑚(𝑏).δ m(a b)=[δ m(a),δ m(b)]=δ m(a)δ m(b).

反过来，如果 𝛿 𝑚(𝑎 𝑏) =𝛿 𝑚(𝑎)𝛿 𝑚(𝑏)δ m(a b)=δ m(a)δ m(b)，那么根据性质 4，就有

𝛿 𝑚(𝑎)𝛿 𝑚(𝑏)=𝛿 𝑚(𝑎 𝑏)∣[𝛿 𝑚(𝑎),𝛿 𝑚(𝑏)].δ m(a)δ m(b)=δ m(a b)∣[δ m(a),δ m(b)].

这立马说明 (𝛿 𝑚(𝑎),𝛿 𝑚(𝑏)) =1(δ m(a),δ m(b))=1，即 𝛿 𝑚(𝑎) ⟂𝛿 𝑚(𝑏)δ m(a)⟂δ m(b)．

一般情形中，性质 4 得到的界已经是紧的．乘积的阶取得下界的情形很容易构造：例如 (𝑎,𝑏,𝑚) =(3,5,7)(a,b,m)=(3,5,7) 时，𝛿 𝑚(𝑎) =𝛿 𝑚(𝑏) =6 δ m(a)=δ m(b)=6，但是它们的乘积的阶 𝛿 𝑚(𝑎 𝑏) =1 δ m(a b)=1．

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

性质 5

对于 𝑎,𝑏 ∈𝐙,𝑚 ∈𝐍+a,b∈Z,m∈N+ 且 𝑎,𝑏 ⟂𝑚 a,b⟂m，总是存在 𝑐 ∈𝐙 c∈Z 且 𝑐 ⟂𝑚 c⟂m 使得

𝛿 𝑚(𝑐)=[𝛿 𝑚(𝑎),𝛿 𝑚(𝑏)].δ m(c)=[δ m(a),δ m(b)].
证明

考虑素因数分解：

𝛿 𝑚(𝑎)=∏𝑝 𝑝 𝛼 𝑝, 𝛿 𝑚(𝑏)=∏𝑝 𝑝 𝛽 𝑝.δ m(a)=∏p p α p, δ m(b)=∏p p β p.

利用 𝛼 𝑝 α p 和 𝛽 𝑝 β p 的大小关系，可以将所有素因子分为两类：

𝐴={𝑝:𝛼 𝑝≥𝛽 𝑝}, 𝐵={𝑝:𝛼 𝑝<𝛽 𝑝}.A={p:α p≥β p}, B={p:α p<β p}.

由此，分别设

𝛾 𝐴=∏𝑝∈𝐴 𝑝 𝛼 𝑝, 𝛾 𝐵=∏𝑝∈𝐵 𝑝 𝛼 𝑝, 𝜂 𝐴=∏𝑝∈𝐴 𝑝 𝛽 𝑝, 𝜂 𝐵=∏𝑝∈𝐵 𝑝 𝛽 𝑝,γ A=∏p∈A p α p, γ B=∏p∈B p α p, η A=∏p∈A p β p, η B=∏p∈B p β p,

就有 𝛿 𝑚(𝑎) =𝛾 𝐴 𝛾 𝐵 δ m(a)=γ A γ B 和 𝛿 𝑚(𝑏) =𝜂 𝐴 𝜂 𝐵 δ m(b)=η A η B．根据 性质 3，可知

𝛿 𝑚(𝑎 𝛾 𝐵)=𝛿 𝑚(𝑎)(𝛿 𝑚(𝑎),𝛾 𝐵)=𝛿 𝑚(𝑎)𝛾 𝐵=𝛾 𝐴,𝛿 𝑚(𝑏 𝜂 𝐴)=𝛿 𝑚(𝑏)(𝛿 𝑚(𝑏),𝜂 𝐴)=𝛿 𝑚(𝑏)𝜂 𝐴=𝜂 𝐵.δ m(a γ B)=δ m(a)(δ m(a),γ B)=δ m(a)γ B=γ A,δ m(b η A)=δ m(b)(δ m(b),η A)=δ m(b)η A=η B.

因为 𝛾 𝐴 ⟂𝜂 𝐵 γ A⟂η B，由 性质 4'，就有

𝛿 𝑚(𝑎 𝛾 𝐵 𝑏 𝜂 𝐴)=𝛾 𝐴 𝜂 𝐵=∏𝑝 𝑝 m a x{𝛼 𝑝,𝛽 𝑝}=[𝛿 𝑚(𝑎),𝛿 𝑚(𝑏)].δ m(a γ B b η A)=γ A η B=∏p p max{α p,β p}=[δ m(a),δ m(b)].

因此，𝑐 =𝑎 𝛾 𝐵 𝑏 𝜂 𝐴 c=a γ B b η A 就是阶为 [𝛿 𝑚(𝑎),𝛿 𝑚(𝑏)][δ m(a),δ m(b)] 的元素．

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

## 原根

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

原根

对于 𝑚 ∈𝐍+m∈N+，如果存在 𝑔 ∈𝐙 g∈Z 且 𝑔 ⟂𝑚 g⟂m 使得 𝛿 𝑚(𝑔) =|𝐙∗𝑚| =𝜑(𝑚)δ m(g)=|Z m∗|=φ(m)，就称 𝑔 g 为 模 𝑚 m 的原根（primitive root modulo 𝑚 m）．其中，𝜑(𝑚)φ(m) 是 欧拉函数．

并非所有正整数 𝑚 m 都存在模 𝑚 m 的原根．由上文的 性质 1，如果模 𝑚 m 的原根 𝑔 g 存在，那么，𝑔,𝑔 2,⋯,𝑔 𝜑(𝑚)g,g 2,⋯,g φ(m) 所在的同余类互不相同，构成模 𝑚 m 既约剩余系．特别地，对于素数 𝑝 p，余数 𝑔 𝑖 m o d 𝑝 g i mod p 对于 𝑖 =1,2,⋯,𝑝 −1 i=1,2,⋯,p−1 两两不同．

注

在 抽象代数 中，原根就是循环群的生成元．这个概念只在模 𝑚 m 既约剩余系关于乘法形成的群中有「原根」这个名字，在一般的循环群中都称作「生成元」．并非每个模 𝑚 m 既约剩余系关于乘法形成的群都是循环群，存在原根就表明它同构于循环群，如果不存在原根就表明不同构．

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

### 原根判定定理

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

定理

对于整数 𝑚 ≥3 m≥3 和 𝑔 ⟂𝑚 g⟂m，那么，𝑔 g 是模 𝑚 m 的原根，当且仅当对于 𝜑(𝑚)φ(m) 的每个素因数 𝑝 p，都有

𝑔 𝜑(𝑚)𝑝≢1(m o d 𝑚).g φ(m)p≢1(mod m).
证明

必要性显然．为证明充分性，考虑使用反证法．如果 𝑔 g 不是模 𝑚 m 的原根，那么一定有 𝛿 𝑚(𝑔) <𝜑(𝑚)δ m(g)<φ(m)．由 性质 2 和欧拉定理可知，𝛿 𝑚(𝑔) ∣𝜑(𝑚)δ m(g)∣φ(m)．由此，设 𝑝 p 是 𝜑(𝑚)𝛿 𝑚(𝑔)φ(m)δ m(g) 的一个素因子，就有 𝛿 𝑚(𝑔) ∣𝜑(𝑚)𝑝 δ m(g)∣φ(m)p．再次应用性质 2 就得到

𝑔 𝜑(𝑚)𝑝≡1(m o d 𝑚).g φ(m)p≡1(mod m).

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

### 原根个数

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

定理

如果正整数 𝑚 m 有原根 𝑔 g，那么，当且仅当 𝑑 ∣𝜑(𝑚)d∣φ(m) 时，模 𝑚 m 的 𝑑 d 阶元素存在，且恰有 𝜑(𝑑)φ(d) 个．特别地，模 𝑚 m 的原根个数为 𝜑(𝜑(𝑚))φ(φ(m))．

证明

根据原根的定义，所有模 𝑚 m 的既约同余类都可以写作 𝑔 𝑘 m o d 𝑚 g k mod m 的形式，且 𝑘 k 是 1,2,⋯,𝜑(𝑚)1,2,⋯,φ(m) 之一．由 性质 3，这些元素的阶等于

𝛿 𝑚(𝑔 𝑘)=𝜑(𝑚)(𝜑(𝑚),𝑘).δ m(g k)=φ(m)(φ(m),k).

因此，𝑑 d 阶元素存在，当且仅当 𝑑 ∣𝜑(𝑚)d∣φ(m)．而且，对于 𝑑 ∣𝜑(𝑚)d∣φ(m)，令 𝑑′ =𝜑(𝑚)/𝑑 d′=φ(m)/d，这些元素的集合就是

𝐴={𝑔 𝑘:(𝜑(𝑚),𝑘)=𝑑′, 1≤𝑘≤𝜑(𝑚)}={𝑔 𝑘:𝑑′∣𝑘, (𝑑,𝑘/𝑑′)=1, 1≤𝑘/𝑑′≤𝑑}.A={g k:(φ(m),k)=d′, 1≤k≤φ(m)}={g k:d′∣k, (d,k/d′)=1, 1≤k/d′≤d}.

这些元素对应的 𝑘′ =𝑘/𝑑′k′=k/d′ 恰为那些不超过 𝑑 d 且与 𝑑 d 互素的正整数．由欧拉函数的定义，这就是 𝜑(𝑑)φ(d)．

### 原根存在定理

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

定理

模 𝑚 m 的原根存在，当且仅当 𝑚 =1,2,4,𝑝 𝑒,2 𝑝 𝑒 m=1,2,4,p e,2 p e，其中，𝑝 p 是奇素数且 𝑒 ∈𝐍+e∈N+．

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

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

2. 𝑚 =𝑝 𝑒 m=p e 是奇素数的幂，其中，𝑝 p 为奇素数，𝑒 ∈𝐍+e∈N+．

   引理 1

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

   证明

   证明分为两步．

   第一步：对于 𝑑 ∣(𝑝 −1)d∣(p−1)，同余方程 𝑥 𝑑 ≡1(m o d 𝑝)x d≡1(mod p) 恰有 𝑑 d 个互不相同的解．

   令 𝑝 −1 =𝑘 𝑑 p−1=k d，多项式

   𝑓(𝑥)=𝑥 𝑑(𝑘−1)+𝑥 𝑑(𝑘−2)+⋯+𝑥 𝑑+1.f(x)=x d(k−1)+x d(k−2)+⋯+x d+1.

   根据 欧拉定理，同余方程 (𝑥 𝑑 −1)𝑓(𝑥) =𝑥 𝑝−1 −1 ≡0(m o d 𝑝)(x d−1)f(x)=x p−1−1≡0(mod p) 恰有 𝑝 −1 p−1 个互不相同的解．这些解分别是 𝑥 𝑑 −1 x d−1 和 𝑓(𝑥)f(x) 的零点．由 Lagrange 定理，它们分别至多只能有 𝑑 d 个和 𝑑(𝑘 −1)d(k−1) 个互不相同的零点．由于 𝑑 +𝑑(𝑘 −1) =𝑝 −1 d+d(k−1)=p−1，前者只能恰好有 𝑑 d 个互不相同的零点．这说明同余方程 𝑥 𝑑 ≡1(m o d 𝑝)x d≡1(mod p) 恰有 𝑑 d 个互不相同的解．

   第二步：对于 𝑑 ∣(𝑝 −1)d∣(p−1)，𝑑 d 阶元素恰好有 𝜑(𝑑)φ(d) 个．

   对于 𝜑(𝑝)φ(p) 的所有因子排序，然后应用归纳法．因为 1 1 阶元素只能是 1 1，只有一个，归纳起点成立．对于 𝑑 ∣(𝑝 −1)d∣(p−1)，根据前文的 性质 2，同余方程 𝑥 𝑑 ≡1(m o d 𝑝)x d≡1(mod p) 的解一定满足 𝛿 𝑝(𝑥) ∣𝑑 δ p(x)∣d．因此，其中 𝑑 d 阶元素个数为

   𝑁(𝑑)=𝑑−∑𝑒∣𝑑, 𝑒≠𝑑 𝑁(𝑒)=𝑑−∑𝑒∣𝑑, 𝑒≠𝑑 𝜑(𝑒)=𝜑(𝑑).N(d)=d−∑e∣d, e≠d N(e)=d−∑e∣d, e≠d φ(e)=φ(d).

   第二个等号是归纳假设，第三个等号是欧拉函数的性质．由数学归纳法，就知道对于所有 𝑑 ∣(𝑝 −1)d∣(p−1)，都恰有 𝜑(𝑑)φ(d) 个 𝑑 d 阶元素．

   特别地，对于 𝑑 =𝑝 −1 d=p−1，恰有 𝜑(𝑝 −1)φ(p−1) 个 (𝑝 −1)(p−1) 阶元素．因此，模 𝑝 p 的原根存在．

   引理 2

   对于奇素数 𝑝 p 和 𝑒 ∈𝐍+e∈N+，模 𝑝 𝑒 p e 的原根存在．

   证明

   证明分为三步．

   第一步：存在模 𝑝 p 的原根 𝑔 g，使得 𝑔 𝑝−1 ≢1(m o d 𝑝 2)g p−1≢1(mod p 2)．

   任取一个模 𝑝 p 的原根 𝑔 g．如果它不符合条件，即 𝑔 𝑝−1 ≡1(m o d 𝑝 2)g p−1≡1(mod p 2)，那么，可以证明 𝑔 +𝑝 g+p 符合条件：𝑔 +𝑝 g+p 也是模 𝑝 p 的原根，且

   (𝑔+𝑝)𝑝−1≡(𝑝−1 0)𝑔 𝑝−1+(𝑝−1 1)𝑔 𝑝−2 𝑝=𝑔 𝑝−1+𝑔 𝑝−2 𝑝(𝑝−1)≡1−𝑝 𝑔 𝑝−2≢1(m o d 𝑝 2).(g+p)p−1≡(p−1 0)g p−1+(p−1 1)g p−2 p=g p−1+g p−2 p(p−1)≡1−p g p−2≢1(mod p 2).

   第二步：上文选取的 𝑔 g，对于任意 𝑒 ≥1 e≥1，都有 𝑔 𝜑(𝑝 𝑒) ≢1(m o d 𝑝 𝑒+1)g φ(p e)≢1(mod p e+1)．

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

   𝑔 𝜑(𝑝 𝑒)=1+𝜆 𝑝 𝑒 g φ(p e)=1+λ p e

   成立．由归纳假设，𝜆 ⟂𝑝 λ⟂p．因为 𝜑(𝑝 𝑒+1) =𝑝 𝜑(𝑝 𝑒)φ(p e+1)=p φ(p e)，所以

   𝑔 𝜑(𝑝 𝑒+1)=(𝑔 𝜑(𝑝 𝑒))𝑝=(1+𝜆 𝑝 𝑒)𝑝≡1+𝜆 𝑝 𝑒+1(m o d 𝑝 𝑒+2).g φ(p e+1)=(g φ(p e))p=(1+λ p e)p≡1+λ p e+1(mod p e+2).

   结合 𝜆 ⟂𝑝 λ⟂p 可知，𝑔 𝜑(𝑝 𝑒+1) ≢1(m o d 𝑝 𝑒+2)g φ(p e+1)≢1(mod p e+2)．由数学归纳法可知，命题成立．

   第三步：上文选取的 𝑔 g，对于任意 𝑒 ≥1 e≥1，都是模 𝑝 𝑒 p e 的原根．

   对 𝑔 g 的选取保证了 𝑒 =1 e=1 时，命题成立．假设命题对于 𝑒 e 成立，现在要证明命题对于 𝑒 +1 e+1 也成立．将 𝛿 𝑝 𝑒+1(𝑔)δ p e+1(g) 简记为 𝛿 δ．由于 𝑔 𝛿 ≡1(m o d 𝑝 𝑒+1)g δ≡1(mod p e+1)，必然也有 𝑔 𝛿 ≡1(m o d 𝑝 𝑒)g δ≡1(mod p e)．由归纳假设可知，𝛿 𝑝 𝑒(𝑔) =𝜑(𝑝 𝑒)δ p e(g)=φ(p e)．因此，由前文阶的 性质 2，就有 𝜑(𝑝 𝑒) ∣𝛿 φ(p e)∣δ．又由欧拉定理可知，𝛿 ∣𝜑(𝑝 𝑒+1)δ∣φ(p e+1)．但是，𝜑(𝑝 𝑒+1) =𝑝 𝜑(𝑝 𝑒)φ(p e+1)=p φ(p e)．因此，只有两种可能：𝛿 =𝜑(𝑝 𝑒)δ=φ(p e) 或 𝛿 =𝜑(𝑝 𝑒+1)δ=φ(p e+1)．但是，第二步的结论说明，𝑔 𝜑(𝑝 𝑒) ≢1(m o d 𝑝 𝑒+1)g φ(p e)≢1(mod p e+1)．因此，可能性 𝛿 =𝜑(𝑝 𝑒)δ=φ(p e) 并不成立．唯一的可能性就是 𝛿 =𝜑(𝑝 𝑒+1)δ=φ(p e+1)．这就说明 𝑔 g 是 𝑝 𝑒+1 p e+1 的原根．由数学归纳法，命题对于所有 𝑒 ≥1 e≥1 都成立．

3. 𝑚 =2 𝑝 𝑒 m=2 p e，其中，𝑝 p 为奇素数，𝑒 ∈𝐍+e∈N+．

   引理 3

   对于奇素数 𝑝 p 和 𝑒 ∈𝐍+e∈N+，模 2 𝑝 𝑒 2 p e 的原根存在．

   证明

   设 𝑔 g 是模 𝑝 𝑒 p e 的原根，则 𝑔 +𝑝 𝑒 g+p e 也是模 𝑝 𝑒 p e 的原根．两者之间必然有一个是奇数，不妨设它就是 𝑔 g．显然，(𝑔,2 𝑝 𝑒) =1(g,2 p e)=1．设 𝛿 =𝛿 2 𝑝 𝑒(𝑔)δ=δ 2 p e(g)，需要证明 𝛿 =𝜑(2 𝑝 𝑒)δ=φ(2 p e)．由欧拉定理，𝛿 ∣𝜑(2 𝑝 𝑒)δ∣φ(2 p e)．同时，根据定义 𝑔 𝛿 ≡1(m o d 2 𝑝 𝑒)g δ≡1(mod 2 p e)，所以，𝑔 𝛿 ≡1(m o d 𝑝 𝑒)g δ≡1(mod p e)，因此，由阶的 性质 2 和 𝑔 g 的选取可知，𝛿 𝑝 𝑒(𝑔) =𝜑(𝑝 𝑒) ∣𝛿 δ p e(g)=φ(p e)∣δ．由欧拉函数表达式可知，𝜑(2 𝑝 𝑒) =𝜑(𝑝 𝑒)φ(2 p e)=φ(p e)．所以，𝛿 =𝛿 2 𝑝 𝑒(𝑔) =𝜑(𝑝 𝑒)δ=δ 2 p e(g)=φ(p e)．这就说明 𝛿 δ 是模 2 𝑝 𝑒 2 p e 的原根．

4. 𝑚 ≠1,2,4,𝑝 𝑒,2 𝑝 𝑒 m≠1,2,4,p e,2 p e，其中，𝑝 p 为奇素数，𝑒 ∈𝐍+e∈N+．

   引理 4

   假设 𝑚 ≠1,2,4 m≠1,2,4 且不存在奇素数 𝑝 p 和正整数 𝑒 e 使得 𝑚 =𝑝 𝑒 m=p e 或 𝑚 =2 𝑝 𝑒 m=2 p e．那么，模 𝑚 m 的原根不存在．

   证明

   对于 𝑚 =2 𝑒 m=2 e 且 𝑒 ≥3 e≥3，假设模 𝑚 m 的原根 𝑔 g 存在．由于 𝑔 ⟂𝑚 g⟂m，它一定是奇数．假设 𝑔 =2 𝑘 +1 g=2 k+1 且 𝑘 ∈𝐍 k∈N，那么，有

   𝑔 2 𝑒−2=(2 𝑘+1)2 𝑒−2≡1+(2 𝑒−2 1)(2 𝑘)+(2 𝑒−2 2)(2 𝑘)2=1+2 𝑒−1 𝑘+2 𝑒−1(2 𝑒−2−1)𝑘 2=1+2 𝑒−1(𝑘+(2 𝑒−2−1)𝑘 2)≡1(m o d 2 𝑒).g 2 e−2=(2 k+1)2 e−2≡1+(2 e−2 1)(2 k)+(2 e−2 2)(2 k)2=1+2 e−1 k+2 e−1(2 e−2−1)k 2=1+2 e−1(k+(2 e−2−1)k 2)≡1(mod 2 e).

   倒数第二行中，因为 𝑘 k 与 (2 𝑒−2 −1)𝑘 2(2 e−2−1)k 2 奇偶性相同，所以它们的和是偶数．由阶的定义可知，𝛿 2 𝑒(𝑔) ≤2 𝑒−2 <𝜑(2 𝑒) =2 𝑒−1 δ 2 e(g)≤2 e−2<φ(2 e)=2 e−1．这与假设中 𝑔 g 是原根矛盾．由反证法，这样的原根并不存在．

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

   𝑔 𝜑(𝑚 𝑖)≡1(m o d 𝑚 𝑖).g φ(m i)≡1(mod m i).

   由于 𝑚 𝑖 >2 m i>2，所以 𝜑(𝑚 𝑖)φ(m i) 为偶数，所以，对于 𝑖 =1,2 i=1,2，有

   𝑔 1 2 𝜑(𝑚 1)𝜑(𝑚 2)≡1(m o d 𝑚 𝑖).g 1 2 φ(m 1)φ(m 2)≡1(mod m i).

   由 中国剩余定理 可知

   𝑔 1 2 𝜑(𝑚 1)𝜑(𝑚 2)≡1(m o d 𝑚).g 1 2 φ(m 1)φ(m 2)≡1(mod m).

   又因为 𝜑(𝑚) =𝜑(𝑚 1)𝜑(𝑚 2)φ(m)=φ(m 1)φ(m 2)，所以由阶的定义可知

   𝛿 𝑚(𝑔)≤1 2 𝜑(𝑚 1)𝜑(𝑚 2)=1 2 𝜑(𝑚)<𝜑(𝑚).δ m(g)≤1 2 φ(m 1)φ(m 2)=1 2 φ(m)<φ(m).

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

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

### 求原根的算法

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

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

- 上界的估计：王元5和 Burgess6证明了素数 𝑝 p 的最小原根 𝑔 𝑝 =𝑂(𝑝 0.2 5+𝜖)g p=O(p 0.25+ϵ)，其中 𝜖 >0 ϵ>0．Cohen, Odoni, and Stothers7和 Elliott and Murata8分别证明了该估计对于模数 𝑝 2 p 2 和 2 𝑝 2 2 p 2 也成立，其中，𝑝 p 是奇素数．由于对于 𝑒 >2 e>2，模 𝑝 2 p 2（或 2 𝑝 2 2 p 2）的原根也是模 𝑝 𝑒 p e（或 2 𝑝 𝑒 2 p e）的原根，所以，最小原根的上界 𝑂(𝑝 0.2 5+𝜖)O(p 0.25+ϵ) 对于所有情形都成立．
- 下界的估计：Fridlander9和 Salié10证明了存在 𝐶 >0 C>0，使得对于无穷多素数 𝑝 p，都有最小原根 𝑔 𝑝 >𝐶 l o g⁡𝑝 g p>C log⁡p 成立．
- 平均情形的估计：Burgess and Elliott11证明了平均情形下素数 𝑝 p 的最小原根 𝑔 𝑝 =𝑂((l o g⁡𝑝)2(l o g⁡l o g⁡𝑝)4)g p=O((log⁡p)2(log⁡log⁡p)4)．Elliott and Murata12进一步猜想素数 𝑝 p 的最小原根的平均值是一个常数，且通过数值验证13得到它大概为 4.9 2 6 4.926．随后，Elliott and Murata8将这一猜想推广到模 2 𝑝 2 2 p 2 的情形．

根据这些分析，暴力寻找最小原根时，枚举部分的复杂度 𝑂(𝑔 𝑚(l o g⁡𝑚)2)O(g m(log⁡m)2) 是可以接受的．

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

𝜑(𝜑(𝑚))𝑚=Ω(1 l o g⁡l o g⁡𝑚).φ(φ(m))m=Ω(1 log⁡log⁡m).

所以，通过随机方法寻找原根时，枚举部分的期望复杂度为 𝑂((l o g⁡𝑚)2 l o g⁡l o g⁡𝑚)O((log⁡m)2 log⁡log⁡m)．

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

## Carmichael 函数

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

Carmichael 函数

对于 𝑚 ∈𝐍+m∈N+，定义 𝜆(𝑚)λ(m) 为能够使得同余关系 𝑎 𝑛 ≡1(m o d 𝑚)a n≡1(mod m) 对于所有 𝑎 ⟂𝑚 a⟂m 都成立的最小正整数 𝑛 n．函数 𝜆 :𝐍+ →𝐍+λ:N+→N+ 就称为 Carmichael 函数．

根据 性质 2，能够使得 𝑎 𝑛 ≡1(m o d 𝑚)a n≡1(mod m) 对于所有 𝑎 ⟂𝑚 a⟂m 都成立，意味着 𝛿 𝑚(𝑎) ∣𝑛 δ m(a)∣n 对于所有 𝑎 ⟂𝑚 a⟂m 都成立．也就是说，符合这一条件的正整数 𝑛 n，一定是全体 𝛿 𝑚(𝑎)δ m(a) 的公倍数．因此，最小的这样的 𝑛 n 就是它们的最小公倍数：

𝜆(𝑚)=l c m⁡{𝛿 𝑚(𝑎):𝑎⟂𝑚}.λ(m)=lcm⁡{δ m(a):a⟂m}.

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

反复应用 性质 5 可知，一定存在某个元素 𝑎 ⟂𝑚 a⟂m 使得 𝛿 𝑚(𝑎) =𝜆(𝑚)δ m(a)=λ(m)．因此，上式也可以写作

𝜆(𝑚)=m a x{𝛿 𝑚(𝑎):𝑎⟂𝑚}.λ(m)=max{δ m(a):a⟂m}.

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

### 递推公式

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

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

引理

对于互素的正整数 𝑚 1,𝑚 2 m 1,m 2，有 𝜆(𝑚 1 𝑚 2) =[𝜆(𝑚 1),𝜆(𝑚 2)]λ(m 1 m 2)=[λ(m 1),λ(m 2)]．

证明

设 𝑎 1 a 1 和 𝑎 2 a 2 分别为模 𝑚 1 m 1 和模 𝑚 2 m 2 的 𝜆 λ‑原根．令 𝑚 =𝑚 1 𝑚 2 m=m 1 m 2，由 中国剩余定理 可知，存在 𝑎 ⟂𝑚 a⟂m 使得 𝑎 ≡𝑎 𝑖(m o d 𝑚 𝑖)a≡a i(mod m i) 对于 𝑖 =1,2 i=1,2 都成立．由于 𝑎 𝜆(𝑚) ≡1(m o d 𝑚)a λ(m)≡1(mod m)，所以对于 𝑖 =1,2 i=1,2，都有 𝑎 𝜆(𝑚)𝑖 ≡1(m o d 𝑚 𝑖)a i λ(m)≡1(mod m i)，进而由 性质 2 和 𝑎 𝑖 a i 的选取可知，𝜆(𝑚 𝑖) =𝛿 𝑚 𝑖(𝑎 𝑖) ∣𝜆(𝑚)λ(m i)=δ m i(a i)∣λ(m)．这就说明 [𝜆(𝑚 1),𝜆(𝑚 2)] ∣𝜆(𝑚)[λ(m 1),λ(m 2)]∣λ(m)．

反过来，对于任意 𝑎 ⟂𝑚 a⟂m 和 𝑖 =1,2 i=1,2，都有 𝑎[𝜆(𝑚 1),𝜆(𝑚 2)] ≡1(m o d 𝑚 𝑖)a[λ(m 1),λ(m 2)]≡1(mod m i)．应用中国剩余定理，就得到 𝑎[𝜆(𝑚 1),𝜆(𝑚 2)] ≡1(m o d 𝑚)a[λ(m 1),λ(m 2)]≡1(mod m) 对于所有 𝑎 ⟂𝑚 a⟂m 都成立．根据 Carmichael 函数的定义可知，𝜆(𝑚) ∣[𝜆(𝑚 1),𝜆(𝑚 2)]λ(m)∣[λ(m 1),λ(m 2)]．

由此，命题中的等式成立．

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

引理

对于 𝑚 =2 𝑒 m=2 e 且 𝑒 ∈𝐍+e∈N+，有 𝜆(2) =1 λ(2)=1，𝜆(4) =2 λ(4)=2，且对于 𝑒 ≥3 e≥3 都有 𝜆(𝑚) =2 𝑒−2 λ(m)=2 e−2．

证明

对于 𝑚 =2,4 m=2,4 的情形，单独讨论即可．对于 𝑚 =2 𝑒 m=2 e 且 𝑒 ≥3 e≥3 的情形，首先重复前文 引理 4 的证明的第一部分，就得到 𝜆(𝑚) ≤2 𝑒−2 λ(m)≤2 e−2．进而，只需要证明存在 2 𝑒−2 2 e−2 阶元素即可．为此，有

5 2 𝑒−3=(1+2 2)2 𝑒−3=1+2 2×2 𝑒−3=1+2 𝑒−1≢1(m o d 2 𝑒).5 2 e−3=(1+2 2)2 e−3=1+2 2×2 e−3=1+2 e−1≢1(mod 2 e).

这说明 𝛿 𝑚(5) ∤2 𝑒−3 δ m(5)∤2 e−3，又因为 𝛿 𝑚(5) ∣2 𝑒−2 δ m(5)∣2 e−2，所以，5 5 只能是 2 𝑒−2 2 e−2 阶元素．这就说明，𝜆(𝑚) =2 𝑒−2 λ(m)=2 e−2．

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

推论

设模数为 2 𝑒 2 e 且 𝑒 ≥2 e≥2．那么，所有奇数都同余于唯一一个 ±5 𝑘±5 k 形式的整数同余，其中，𝑘 ∈𝐍 k∈N 且 𝑘 <2 𝑒−2 k<2 e−2．也就是说，±1, ±5,⋯, ±5 2 𝑒−2−1±1,±5,⋯,±5 2 e−2−1 两两不同余，且构成一个既约剩余系．

证明

容易验证，𝑒 =2 e=2 的情形成立．对于 𝑒 ≥3 e≥3 的情形，由于前述证明中已经得到 5 5 模 2 𝑒 2 e 的阶是 2 𝑒−2 2 e−2，所以，1,5,⋯,5 2 𝑒−2−1 1,5,⋯,5 2 e−2−1 两两不同余．因为这些整数都模 4 4 余 1 1，它们的相反数都模 4 4 余 3 3，所以 ±1, ±5,⋯, ±5 2 𝑒−2−1±1,±5,⋯,±5 2 e−2−1 模 2 𝑒 2 e 两两不同余．由于它们共计 2 𝑒−1 2 e−1 个，恰为模 2 𝑒 2 e 的既约剩余系的大小，所以，它们就构成了既约剩余系本身．

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

引理

对于 𝑚 =𝑝 𝑒 m=p e，其中，𝑝 p 是奇素数且 𝑒 ∈𝐍+e∈N+，有 𝜆(𝑚) =𝑝 𝑒−1(𝑝 −1)λ(m)=p e−1(p−1)．

证明

首先证明命题对于 𝑒 =1 e=1，即 𝑚 =𝑝 m=p 是奇素数的情形成立．为此，由 Carmichael 函数的定义可知，与 𝑝 p 互素的所有整数 𝑎 a 都是同余方程 𝑥 𝜆(𝑝) ≡1(m o d 𝑝)x λ(p)≡1(mod p) 的解．在模 𝑝 p 的意义下，该方程共有 𝑝 −1 p−1 个互不相同的解．根据 Lagrange 定理 可知，𝑝 −1 ≤𝜆(𝑝)p−1≤λ(p)．同时，欧拉定理要求，𝜆(𝑝) ∣𝜑(𝑝) =𝑝 −1 λ(p)∣φ(p)=p−1．因此，𝜆(𝑝) =𝑝 −1 λ(p)=p−1．

对于 𝑚 =𝑝 𝑒 m=p e 且 𝑒 >1 e>1 的情形，可以从证明 1 +𝑝 1+p 是 𝑝 𝑒−1 p e−1 阶元开始．为此，有

(1+𝑝)𝑝 𝑒−1≡1,(1+𝑝)𝑝 𝑒−2≡1+𝑝 𝑒−1≢1(m o d 𝑝 𝑒).(1+p)p e−1≡1,(1+p)p e−2≡1+p e−1≢1(mod p e).

所以，𝛿 𝑚(1 +𝑝) =𝑝 𝑒−1 δ m(1+p)=p e−1．另外，设模 𝑝 p 的原根为 𝑔 g，那么，由于 𝑔 𝛿 𝑚(𝑔) ≡1(m o d 𝑝)g δ m(g)≡1(mod p)，所以，由阶的 性质 2 可知，𝑝 −1 ∣𝛿 𝑚(𝑝)p−1∣δ m(p)．由 Carmichael 函数的定义和欧拉定理可知

𝑝 𝑒−1(𝑝−1)=[𝛿 𝑚(𝑝),𝑝 𝑒−1]∣𝜆(𝑚)∣𝜑(𝑚)=𝑝 𝑒−1(𝑝−1).p e−1(p−1)=[δ m(p),p e−1]∣λ(m)∣φ(m)=p e−1(p−1).

因此，𝜆(𝑚) =𝑝 𝑒−1(𝑝 −1)λ(m)=p e−1(p−1)．

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

定理

对于任意正整数 𝑚 m，有

𝜆(𝑚)=⎧{ {⎨{ {⎩𝜑(𝑚),i f 𝑚=1,2,4,𝑝 𝑒 f o r o d d p r i m e 𝑝 a n d 𝑒≥1,1 2 𝜑(𝑚),i f 𝑚=2 𝑒, 𝑒≥3,l c m⁡{𝜆(𝑝 𝑒 1 1),𝜆(𝑝 𝑒 2 2),⋯,𝜆(𝑝 𝑒 𝑠 𝑠)},i f 𝑚=𝑝 𝑒 1 1 𝑝 𝑒 2 2⋯𝑝 𝑒 𝑠 𝑠 f o r d i s t i n c t 𝑝 1,𝑝 2,⋯,𝑝 𝑠.λ(m)={φ(m),if m=1,2,4,p e for odd prime p and e≥1,1 2 φ(m),if m=2 e, e≥3,lcm⁡{λ(p 1 e 1),λ(p 2 e 2),⋯,λ(p s e s)},if m=p 1 e 1 p 2 e 2⋯p s e s for distinct p 1,p 2,⋯,p s.

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

推论

对于正整数 𝑚 1,𝑚 2 m 1,m 2，有 𝜆([𝑚 1,𝑚 2]) =[𝜆(𝑚 1),𝜆(𝑚 2)]λ([m 1,m 2])=[λ(m 1),λ(m 2)]．

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

推论

模 𝑚 m 的原根存在，当且仅当 𝑚 =1,2,4,𝑝 𝑒,2 𝑝 𝑒 m=1,2,4,p e,2 p e，其中，𝑝 p 是奇素数且 𝑒 ∈𝐍+e∈N+．

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

### Carmichael 数

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

Carmichael 数

对于合数 𝑛 n，如果对于所有整数 𝑎 ⟂𝑛 a⟂n 都有同余式 𝑎 𝑛−1 ≡1(m o d 𝑛)a n−1≡1(mod n) 成立，就称 𝑛 n 为 Carmichael 数．

最小的 Carmichael 数是 5 6 1 =3 ×1 1 ×1 7 561=3×11×17．

由 Carmichael 函数的定义可知，合数 𝑛 n 是 Carmichael 数当且仅当 𝜆(𝑛) ∣𝑛 −1 λ(n)∣n−1，其中 𝜆(𝑛)λ(n) 为 Carmichael 函数．进一步地，可以得到如下判断合数 𝑛 n 是否为 Carmichael 数的方法：

Korselt 判别法14

合数 𝑛 n 是 Carmichael 数当且仅当 𝑛 n 无平方因子且对 𝑛 n 的任意质因子 𝑝 p 均有 (𝑝 −1) ∣(𝑛 −1)(p−1)∣(n−1)．

证明

首先证明条件的必要性．假设 𝜆(𝑛) ∣(𝑛 −1)λ(n)∣(n−1)．检查 Carmichael 函数的递推公式可知，如果 𝑛 n 有平方因子 𝑝 p，那么，一定有 𝑝 ∣𝜆(𝑛)p∣λ(n)．但是 𝑝 ∤(𝑛 −1)p∤(n−1)，矛盾．同理，Carmichael 函数的递推公式说明，(𝑝 −1) ∣𝜆(𝑛)(p−1)∣λ(n)，所以，也有 (𝑝 −1) ∣(𝑛 −1)(p−1)∣(n−1)．

然后证明条件的充分性．因为 𝑛 n 是合数，所以它一定有奇素因子 𝑝 p，因此 𝑛 −1 n−1 是偶数，𝑛 n 也就一定是奇数．对于无平方因子的奇合数 𝑛 n，由 Carmichael 函数的递推公式可知，𝜆(𝑛) =l c m⁡{𝑝 −1 :𝑝 ∣𝑛}λ(n)=lcm⁡{p−1:p∣n}．因此，只要 (𝑝 −1) ∣(𝑛 −1)(p−1)∣(n−1) 对于所有素因子 𝑝 p 都成立，就一定有 𝜆(𝑛) ∣(𝑛 −1)λ(n)∣(n−1)．

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

推论

Carmichael 数是奇数，没有平方因子，而且至少有 3 3 个不同的素因子．

证明

前两条性质可以直接从 Korselt 判别法及其证明中得到．要得到第三条性质，只需要再证明：互异素数 𝑝 1,𝑝 2 p 1,p 2 的乘积 𝑛 =𝑝 1 𝑝 2 n=p 1 p 2 一定不是 Carmichael 数．假设 𝑛 =𝑝 1 𝑝 2 n=p 1 p 2 是 Carmichael 数．由 Korselt 判别法可知，(𝑝 𝑖 −1) ∣(𝑛 −1)(p i−1)∣(n−1)．但是，有

𝑛−1=𝑝 1 𝑝 2−1≡𝑝 2−1(m o d 𝑝 1−1).n−1=p 1 p 2−1≡p 2−1(mod p 1−1).

因此，(𝑝 1 −1) ∣(𝑝 2 −1)(p 1−1)∣(p 2−1)．同理，(𝑝 2 −1) ∣(𝑝 1 −1)(p 2−1)∣(p 1−1)．也就是说，𝑝 1 =𝑝 2 p 1=p 2．这与假设矛盾．因此，Carmichael 数 𝑛 n 至少有 3 3 个互异素因子．

利用解析数论还可以得到 Carmichael 数分布的一些性质．设 𝐶(𝑛)C(n) 为小于等于 𝑛 n 的 Carmichael 数个数．Alford, Granville, and Pomerance2证明，对于充分大的 𝑛 n，有 𝐶(𝑛) >𝑛 2/7 C(n)>n 2/7．由此，Carmichael 数有无限多个．在这之前，Erdős3已经证明，𝐶(𝑛) <𝑛 e x p⁡(−𝑐 l n⁡𝑛 l n⁡l n⁡l n⁡𝑛 l n⁡l n⁡𝑛)C(n)<n exp⁡(−c ln⁡n ln⁡ln⁡ln⁡n ln⁡ln⁡n)，其中 𝑐 c 为常数．因此，Carmichael 数的分布（相对于素数来说）十分稀疏．实际上，有4 𝐶(1 0 9) =6 4 6 C(10 9)=646，𝐶(1 0 1 8) =1 4 0 1 6 4 4 C(10 18)=1 401 644．

## 参考资料与注释

- 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

1. 如果模 𝑚 m 的原根存在，那么，𝜑(𝑚) ≥1 3 𝑚 φ(m)≥1 3 m，且等号仅在 𝑚 =2 ×3 𝑒 (𝑒 ∈𝐍+)m=2×3 e (e∈N+) 处取得．进一步地，当 𝑚 >2 m>2 时，对欧拉函数 𝜑(𝑚)φ(m) 有估计：𝜑(𝑚) >𝑚 𝑒 𝛾 l o g⁡l o g⁡𝑚+3 l o g⁡l o g⁡𝑚 φ(m)>m e γ log⁡log⁡m+3 log⁡log⁡m．将这两者结合，就得到文中的表达式．关于欧拉函数的该估计，可以参考论文 Rosser, J. Barkley, and Lowell Schoenfeld. "Approximate formulas for some functions of prime numbers." Illinois Journal of Mathematics 6, no. 1 (1962): 64-94． ↩

2. W. R. Alford; Andrew Granville; Carl Pomerance (1994). "There are Infinitely Many Carmichael Numbers." Annals of Mathematics. 140 (3): 703–722. ↩

3. Erdős, P. (1956). "On pseudoprimes and Carmichael numbers." Publ. Math. Debrecen. 4 (3–4): 201–206. ↩

4. PINCH, Richard GE. The Carmichael numbers up to 1 0 2 0 10 20. ↩

5. Wang Y. "On the least primitive root of a prime." (in Chinese). Acta Math Sinica, 1959, 4: 432–441; English transl. inSci. Sinica, 1961, 10: 1–14. ↩

6. BURGESS, David A. "On character sums and primitive roots." Proceedings of the London Mathematical Society, 1962, 3.1: 179-192. ↩

7. Cohen, S. D., R. W. K. Odoni, and W. W. Stothers. "On the least primitive root modulo p 2." Bulletin of the London Mathematical Society 6, no. 1 (1974): 42-46. ↩

8. Elliott, P. D. T. A., and L. Murata. "The least primitive root mod 2p2." Mathematika 45, no. 2 (1998): 371-379. ↩↩

9. FRIDLENDER, V. R. "On the least n-th power non-residue." Dokl. Akad. Nauk SSSR. 1949. p. 351-352. ↩

10. SALIÉ, Hans. "Über den kleinsten positiven quadratischen Nichtrest nach einer Primzahl." Mathematische Nachrichten, 1949, 3.1: 7-8. ↩

11. Burgess, D. A., and P. D. T. A. Elliott. "The average of the least primitive root." Mathematika 15, no. 1 (1968): 39-50. ↩

12. Elliott, Peter DTA, and Leo Murata. "On the average of the least primitive root modulo p." Journal of The london Mathematical Society 56, no. 3 (1997): 435-454. ↩

13. 更多结果可以参考 Least prime primitive root of prime numbers． ↩

14. Korselt, A. R. (1899). "Problème chinois." L'Intermédiaire des Mathématiciens. 6: 142–143. ↩

> 本页面最近更新：2025/11/1 11:21:19，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Peanut-Tang, c-forrest, Early0v0, 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 协议之条款下提供，附加条款亦可能应用