前置知识：费马小定理 、欧拉定理 、拉格朗日定理
阶和原根，是理解模 m m m 既约剩余系 Z m ∗ \mathbf Z_m^* Z m ∗ 离散对数 等概念．更为一般的讨论可以参见抽象代数部分 群论 和 环论 等页面相关章节．
阶
本节中，总是假设模数 m ∈ N + m\in\mathbf N_+ m ∈ N + a ∈ Z a\in\mathbf Z a ∈ Z ( a , m ) = 1 (a,m)=1 ( a , m ) = 1 a ⊥ m a\perp m a ⊥ m
对于 n ∈ Z n\in\mathbf Z n ∈ Z a n m o d m a^n\bmod m a n mod m a a a m m m a n m o d m a^n \bmod m a n mod m a 0 m o d m = 1 a^0\bmod m = 1 a 0 mod m = 1
阶
对于 a ∈ Z , m ∈ N + a\in\mathbf Z,m\in\mathbf N_+ a ∈ Z , m ∈ N + a ⊥ m a\perp m a ⊥ m a n ≡ 1 ( m o d m ) a^n \equiv 1 \pmod m a n ≡ 1 ( mod m ) n n n a a a m m m a a a m m m δ m ( a ) \delta_m(a) δ m ( a ) ord m ( a ) \operatorname{ord}_m(a) ord m ( a )
注
在 抽象代数 中，这里的「阶」就是模 m m m a a a δ \delta δ
另外还有「半阶」的概念，在数论中会用 δ − \delta^- δ − a n ≡ − 1 ( m o d m ) a^n \equiv -1 \pmod m a n ≡ − 1 ( mod m )
幂的循环结构
利用阶，可以刻画幂的循环结构．对于幂 a n m o d m a^n\bmod m a n mod m n n n δ m ( a ) \delta_m(a) δ m ( a )
n = δ m ( a ) q + r , 0 ≤ r < δ m ( a ) . n = \delta_m(a)q + r, ~ 0\le r < \delta_m(a). n = δ m ( a ) q + r , 0 ≤ r < δ m ( a ) . 进而，利用幂的运算律，就得到
a n = a δ m ( a ) q + r = ( a δ m ( a ) ) q ⋅ a r ≡ a r ( m o d m ) . a^n = a^{\delta_m(a)q + r} = (a^{\delta_m(a)})^q \cdot a^r \equiv a^r \pmod m. a n = a δ m ( a ) q + r = ( a δ m ( a ) ) q ⋅ a r ≡ a r ( mod m ) . 这说明，对于任意指数的幂，可以将它平移到第一个非负的循环节．由此，可以得到一系列关于阶的性质．
性质 1
对于 a ∈ Z , m ∈ N + a\in\mathbf Z,m\in\mathbf N_+ a ∈ Z , m ∈ N + a ⊥ m a\perp m a ⊥ m a 0 ( = 1 ) , a , a 2 , ⋯ , a δ m ( a ) − 1 a^0(=1),a,a^2,\cdots,a^{\delta_m(a)-1} a 0 ( = 1 ) , a , a 2 , ⋯ , a δ m ( a ) − 1 m m m
证明
考虑反证．假设存在两个数 0 ≤ i < j < δ m ( a ) 0\le i< j<\delta_m(a) 0 ≤ i < j < δ m ( a ) a i ≡ a j ( m o d m ) a^i\equiv a^j\pmod m a i ≡ a j ( mod m ) a j − i ≡ 1 ( m o d m ) a^{j - i}\equiv 1\pmod m a j − i ≡ 1 ( mod m ) 0 < j − i < δ m ( a ) 0 < j - i < \delta_m(a) 0 < j − i < δ m ( a )
性质 2
对于 a , n ∈ Z , m ∈ N + a,n\in\mathbf Z,m\in\mathbf N_+ a , n ∈ Z , m ∈ N + a ⊥ m a\perp m a ⊥ m a n ≡ 1 ( m o d m ) a^n \equiv 1 \pmod m a n ≡ 1 ( mod m ) δ m ( a ) ∣ n \delta_m(a)\mid n δ m ( a ) ∣ n
证明
如前文所述，a n ≡ a n m o d δ m ( a ) ( m o d m ) a^{n}\equiv a^{n\bmod\delta_m(a)}\pmod m a n ≡ a n mod δ m ( a ) ( mod m ) 性质 1 可知，0 ≤ r < δ m ( a ) 0\le r < \delta_m(a) 0 ≤ r < δ m ( a ) a r ≡ 1 ( m o d m ) a^r\equiv 1\pmod m a r ≡ 1 ( mod m ) r r r r = 0 r=0 r = 0 a n ≡ 1 ( m o d m ) a^n \equiv 1 \pmod m a n ≡ 1 ( mod m ) n m o d δ m ( a ) = 0 n\bmod \delta_m(a) = 0 n mod δ m ( a ) = 0 δ m ( a ) ∣ n \delta_m(a)\mid n δ m ( a ) ∣ n
欧拉定理 中，同余关系 a φ ( m ) ≡ 1 ( m o d m ) a^{\varphi(m)}\equiv 1\pmod m a φ ( m ) ≡ 1 ( mod m ) a ⊥ m a\perp m a ⊥ m 性质 2 ，这说明对于所有 a ⊥ m a\perp m a ⊥ m δ m ( a ) ∣ φ ( m ) \delta_m(a)\mid\varphi(m) δ m ( a ) ∣ φ ( m ) φ ( m ) \varphi(m) φ ( m ) a ⊥ m a\perp m a ⊥ m m m m a ⊥ m a\perp m a ⊥ m δ m ( a ) \delta_m(a) δ m ( a ) λ ( m ) \lambda(m) λ ( m ) m m m Carmichael 函数 ．后文会详细讨论它的性质．
和其他的循环结构类似，可以根据 a a a a k a^k a k
性质 3
对于 k , a ∈ Z , m ∈ N + k,a\in\mathbf Z,m\in\mathbf N_+ k , a ∈ Z , m ∈ N + a ⊥ m a\perp m a ⊥ m
δ m ( a k ) = δ m ( a ) ( δ m ( a ) , k ) . \delta_m(a^k) = \dfrac{\delta_m(a)}{(\delta_m(a),k)}. δ m ( a k ) = ( δ m ( a ) , k ) δ m ( a ) .
证明
由 性质 2 ，同余关系 ( a k ) n = a k n ≡ 1 ( m o d m ) (a^k)^n = a^{kn} \equiv 1\pmod m ( a k ) n = a k n ≡ 1 ( mod m ) δ m ( a ) ∣ k n \delta_m(a) \mid kn δ m ( a ) ∣ k n
δ m ( a ) ( δ m ( a ) , k ) ∣ n . \dfrac{\delta_m(a)}{\left(\delta_m(a),k\right)} \mid n. ( δ m ( a ) , k ) δ m ( a ) ∣ n . 使得这一条件成立的最小正整数就是
δ m ( a k ) = δ m ( a ) ( δ m ( a ) , k ) . \delta_m(a^k)=\dfrac{\delta_m(a)}{\left(\delta_m(a),k\right)}. δ m ( a k ) = ( δ m ( a ) , k ) δ m ( a ) .
乘积的阶
设 a , b a,b a , b m m m δ m ( a ) \delta_m(a) δ m ( a ) δ m ( b ) \delta_m(b) δ m ( b ) a b ab ab δ m ( a b ) \delta_{m}(ab) δ m ( ab )
性质 4
对于 a , b ∈ Z , m ∈ N + a,b\in\mathbf Z,m\in\mathbf N_+ a , b ∈ Z , m ∈ N + a , b ⊥ m a,b\perp m a , b ⊥ m
[ δ m ( a ) , δ m ( b ) ] ( δ m ( a ) , δ m ( b ) ) ∣ δ m ( a b ) ∣ [ δ m ( a ) , δ m ( b ) ] . \dfrac{[\delta_m(a),\delta_m(b)]}{(\delta_m(a),\delta_m(b))} \mid \delta_m(ab) \mid [\delta_m(a),\delta_m(b)]. ( δ m ( a ) , δ m ( b )) [ δ m ( a ) , δ m ( b )] ∣ δ m ( ab ) ∣ [ δ m ( a ) , δ m ( b )] .
证明
因为 [ δ m ( a ) , δ m ( b ) ] [\delta_m(a),\delta_m(b)] [ δ m ( a ) , δ m ( b )] δ m ( a ) \delta_m(a) δ m ( a ) δ m ( b ) \delta_m(b) δ m ( b ) 性质 2 可知
( a b ) [ δ m ( a ) , δ m ( b ) ] = a [ δ m ( a ) , δ m ( b ) ] b [ δ m ( a ) , δ m ( b ) ] ≡ 1 ( m o d m ) . (ab)^{[\delta_m(a),\delta_m(b)]} = a^{[\delta_m(a),\delta_m(b)]} b^{[\delta_m(a),\delta_m(b)]} \equiv 1 \pmod m. ( ab ) [ δ 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 ) ] . \delta_m(ab) \mid [\delta_m(a),\delta_m(b)]. δ m ( ab ) ∣ [ δ m ( a ) , δ m ( b )] . 这就得到右侧的整除关系．
反过来，由于
1 ≡ ( a b ) δ m ( a b ) δ m ( b ) ≡ a δ m ( a b ) δ m ( b ) ( m o d m ) , 1 \equiv (ab)^{\delta_m(ab)\delta_m(b)} \equiv a^{\delta_m(ab)\delta_m(b)} \pmod m, 1 ≡ ( ab ) δ m ( ab ) δ m ( b ) ≡ a δ m ( ab ) δ m ( b ) ( mod m ) , 所以，应用性质 2，就得到 δ m ( a ) ∣ δ m ( a b ) δ m ( b ) \delta_m(a)\mid\delta_m(ab)\delta_m(b) δ m ( a ) ∣ δ m ( ab ) δ m ( b ) ( δ m ( a ) , δ m ( b ) ) (\delta_m(a),\delta_m(b)) ( δ m ( a ) , δ m ( b ))
δ m ( a ) ( δ m ( a ) , δ m ( b ) ) ∣ δ m ( a b ) δ m ( b ) ( δ m ( a ) , δ m ( b ) ) . \dfrac{\delta_m(a)}{(\delta_m(a),\delta_m(b))}\mid\delta_m(ab)\dfrac{\delta_m(b)}{(\delta_m(a),\delta_m(b))}. ( δ m ( a ) , δ m ( b )) δ m ( a ) ∣ δ m ( ab ) ( δ m ( a ) , δ m ( b )) δ m ( b ) . 消去公因子后，两个分式互素，这就得到
δ m ( a ) ( δ m ( a ) , δ m ( b ) ) ∣ δ m ( a b ) . \dfrac{\delta_m(a)}{(\delta_m(a),\delta_m(b))}\mid\delta_m(ab). ( δ m ( a ) , δ m ( b )) δ m ( a ) ∣ δ m ( ab ) . 同理，也有
δ m ( b ) ( δ m ( a ) , δ m ( b ) ) ∣ δ m ( a b ) . \dfrac{\delta_m(b)}{(\delta_m(a),\delta_m(b))}\mid\delta_m(ab). ( δ m ( a ) , δ m ( b )) δ m ( b ) ∣ δ m ( ab ) . 由于两个整除关系的左侧互素，有
[ δ m ( a ) , δ m ( b ) ] ( δ m ( a ) , δ m ( b ) ) = δ m ( a ) δ m ( b ) ( δ m ( a ) , δ m ( b ) ) 2 ∣ δ m ( a b ) . \dfrac{[\delta_m(a),\delta_m(b)]}{(\delta_m(a),\delta_m(b))} =\dfrac{\delta_m(a)\delta_m(b)}{(\delta_m(a),\delta_m(b))^2}\mid\delta_m(ab). ( δ m ( a ) , δ m ( b )) [ δ m ( a ) , δ m ( b )] = ( δ m ( a ) , δ m ( b ) ) 2 δ m ( a ) δ m ( b ) ∣ δ m ( ab ) . 这就得到左侧的整除关系．
对于 a a a b b b
性质 4'
对于 a , b ∈ Z , m ∈ N + a,b\in\mathbf Z,m\in\mathbf N_+ a , b ∈ Z , m ∈ N + a , b ⊥ m a,b\perp m a , b ⊥ m
δ m ( a b ) = δ m ( a ) δ m ( b ) ⟺ δ m ( a ) ⊥ δ m ( b ) . \delta_m(ab) = \delta_m(a)\delta_m(b) \iff \delta_m(a)\perp\delta_m(b). δ m ( ab ) = δ m ( a ) δ m ( b ) ⟺ δ m ( a ) ⊥ δ m ( b ) .
证明
如果 δ m ( a ) ⊥ δ m ( b ) \delta_m(a)\perp\delta_m(b) δ m ( a ) ⊥ δ m ( b ) 性质 4 中所有整除关系都是等式，所以有
δ m ( a b ) = [ δ m ( a ) , δ m ( b ) ] = δ m ( a ) δ m ( b ) . \delta_m(ab) = [\delta_m(a),\delta_m(b)] = \delta_m(a)\delta_m(b). δ m ( ab ) = [ δ m ( a ) , δ m ( b )] = δ m ( a ) δ m ( b ) . 反过来，如果 δ m ( a b ) = δ m ( a ) δ m ( b ) \delta_m(ab)=\delta_m(a)\delta_m(b) δ m ( ab ) = δ m ( a ) δ m ( b )
δ m ( a ) δ m ( b ) = δ m ( a b ) ∣ [ δ m ( a ) , δ m ( b ) ] . \delta_m(a)\delta_m(b) = \delta_m(ab) \mid [\delta_m(a),\delta_m(b)]. δ m ( a ) δ m ( b ) = δ m ( ab ) ∣ [ δ m ( a ) , δ m ( b )] . 这立马说明 ( δ m ( a ) , δ m ( b ) ) = 1 (\delta_m(a),\delta_m(b))=1 ( δ m ( a ) , δ m ( b )) = 1 δ m ( a ) ⊥ δ m ( b ) \delta_m(a)\perp\delta_m(b) δ m ( a ) ⊥ δ m ( b )
一般情形中，性质 4 得到的界已经是紧的．乘积的阶取得下界的情形很容易构造：例如 ( a , b , m ) = ( 3 , 5 , 7 ) (a,b,m)=(3,5,7) ( a , b , m ) = ( 3 , 5 , 7 ) δ m ( a ) = δ m ( b ) = 6 \delta_m(a)=\delta_m(b)=6 δ m ( a ) = δ m ( b ) = 6 δ m ( a b ) = 1 \delta_m(ab)=1 δ m ( ab ) = 1
尽管一般情形中，乘积 a b ab ab
性质 5
对于 a , b ∈ Z , m ∈ N + a,b\in\mathbf Z,m\in\mathbf N_+ a , b ∈ Z , m ∈ N + a , b ⊥ m a,b\perp m a , b ⊥ m c ∈ Z c\in\mathbf Z c ∈ Z c ⊥ m c\perp m c ⊥ m
δ m ( c ) = [ δ m ( a ) , δ m ( b ) ] . \delta_m(c) = [\delta_m(a),\delta_m(b)]. δ m ( c ) = [ δ m ( a ) , δ m ( b )] .
证明
考虑素因数分解：
δ m ( a ) = ∏ p p α p , δ m ( b ) = ∏ p p β p . \delta_m(a) = \prod_p p^{\alpha_p},~ \delta_m(b) = \prod_p p^{\beta_p}. δ m ( a ) = p ∏ p α p , δ m ( b ) = p ∏ p β p . 利用 α p \alpha_p α p β p \beta_p β p
A = { p : α p ≥ β p } , B = { p : α p < β p } . A = \{p : \alpha_p \ge \beta_p\}, ~ B = \{p : \alpha_p < \beta_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 , \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}, γ A = p ∈ A ∏ p α p , γ B = p ∈ B ∏ p α p , η A = p ∈ A ∏ p β p , η B = p ∈ B ∏ p β p , 就有 δ m ( a ) = γ A γ B \delta_m(a) = \gamma_A\gamma_B δ m ( a ) = γ A γ B δ m ( b ) = η A η B \delta_m(b)=\eta_A\eta_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 . \begin{aligned}
\delta_m(a^{\gamma_B}) &= \dfrac{\delta_m(a)}{(\delta_m(a),\gamma_B)} = \dfrac{\delta_m(a)}{\gamma_B} = \gamma_A,\\
\delta_m(b^{\eta_A}) &= \dfrac{\delta_m(b)}{(\delta_m(b),\eta_A)} = \dfrac{\delta_m(b)}{\eta_A} = \eta_B.
\end{aligned} δ m ( a γ B ) δ m ( b η A ) = ( δ m ( a ) , γ B ) δ m ( a ) = γ B δ m ( a ) = γ A , = ( δ m ( b ) , η A ) δ m ( b ) = η A δ m ( b ) = η B . 因为 γ A ⊥ η B \gamma_A\perp\eta_B γ A ⊥ η B 性质 4' ，就有
δ m ( a γ B b η A ) = γ A η B = ∏ p p max { α p , β p } = [ δ m ( a ) , δ m ( b ) ] . \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)]. δ m ( a γ B b η A ) = γ A η B = p ∏ p m a x { α p , β p } = [ δ m ( a ) , δ m ( b )] . 因此，c = a γ B b η A c=a^{\gamma_B}b^{\eta_A} c = a γ B b η A [ δ m ( a ) , δ m ( b ) ] [\delta_m(a),\delta_m(b)] [ δ m ( a ) , δ m ( b )]
这一结论常用于构造出指定阶的元素．
原根
原根是一些特殊元素——它的阶就等于所有模 m m m
原根
对于 m ∈ N + m\in\mathbf N_+ m ∈ N + g ∈ Z g\in\mathbf Z g ∈ Z g ⊥ m g\perp m g ⊥ m δ m ( g ) = ∣ Z m ∗ ∣ = φ ( m ) \delta_m(g)=|\mathbf Z_m^*|=\varphi(m) δ m ( g ) = ∣ Z m ∗ ∣ = φ ( m ) g g g 模 m m m （primitive root modulo m m m φ ( m ) \varphi(m) φ ( m ) 欧拉函数 ．
并非所有正整数 m m m m m m 性质 1 ，如果模 m m m g g g g , g 2 , ⋯ , g φ ( m ) g,g^2,\cdots,g^{\varphi(m)} g , g 2 , ⋯ , g φ ( m ) m m m p p p g i m o d p g^i\bmod p g i mod p i = 1 , 2 , ⋯ , p − 1 i=1,2,\cdots,p-1 i = 1 , 2 , ⋯ , p − 1
注
在 抽象代数 中，原根就是循环群的生成元．这个概念只在模 m m m m m m
模为 1 1 1 1 1 1 { 0 } \{0\} { 0 } 0 0 0
原根判定定理
如果已知模数 φ ( m ) \varphi(m) φ ( m ) m m m
定理
对于整数 m ≥ 3 m\ge 3 m ≥ 3 g ⊥ m g\perp m g ⊥ m g g g m m m φ ( m ) \varphi(m) φ ( m ) p p p
g φ ( m ) p ≢ 1 ( m o d m ) . g^{\frac{\varphi(m)}{p}}\not\equiv 1 \pmod m. g p φ ( m ) ≡ 1 ( mod m ) .
证明
必要性显然．为证明充分性，考虑使用反证法．如果 g g g m m m δ m ( g ) < φ ( m ) \delta_m(g)< \varphi(m) δ m ( g ) < φ ( m ) 性质 2 和欧拉定理可知，δ m ( g ) ∣ φ ( m ) \delta_m(g)\mid\varphi(m) δ m ( g ) ∣ φ ( m ) p p p φ ( m ) δ m ( g ) \dfrac{\varphi(m)}{\delta_m(g)} δ m ( g ) φ ( m ) δ m ( g ) ∣ φ ( m ) p \delta_m(g)\mid\dfrac{\varphi(m)}{p} δ m ( g ) ∣ p φ ( m )
g φ ( m ) p ≡ 1 ( m o d m ) . g^{\frac{\varphi(m)}{p}} \equiv 1 \pmod m. g p φ ( m ) ≡ 1 ( mod m ) . 但是，p p p φ ( m ) \varphi(m) φ ( m )
原根个数
原根如果存在，也未必唯一．一般地，对于模 m m m
定理
如果正整数 m m m g g g d ∣ φ ( m ) d\mid\varphi(m) d ∣ φ ( m ) m m m d d d φ ( d ) \varphi(d) φ ( d ) m m m φ ( φ ( m ) ) \varphi(\varphi(m)) φ ( φ ( m ))
证明
根据原根的定义，所有模 m m m g k m o d m g^k\bmod m g k mod m k k k 1 , 2 , ⋯ , φ ( m ) 1,2,\cdots,\varphi(m) 1 , 2 , ⋯ , φ ( m ) 性质 3 ，这些元素的阶等于
δ m ( g k ) = φ ( m ) ( φ ( m ) , k ) . \delta_m(g^k) = \dfrac{\varphi(m)}{(\varphi(m),k)}. δ m ( g k ) = ( φ ( m ) , k ) φ ( m ) . 因此，d d d d ∣ φ ( m ) d\mid\varphi(m) d ∣ φ ( m ) d ∣ φ ( m ) d\mid\varphi(m) d ∣ φ ( m ) d ′ = φ ( m ) / d d'=\varphi(m)/d d ′ = φ ( m ) / d
A = { g k : ( φ ( m ) , k ) = d ′ , 1 ≤ k ≤ φ ( m ) } = { g k : d ′ ∣ k , ( d , k / d ′ ) = 1 , 1 ≤ k / d ′ ≤ d } . \begin{aligned}
A &= \{g^k : (\varphi(m),k)=d',~1\le k \le\varphi(m)\} \\
&= \{g^k : d'\mid k,~ (d, k/d') = 1,~ 1 \le k/d' \le d\}.
\end{aligned} A = { g k : ( φ ( m ) , k ) = d ′ , 1 ≤ k ≤ φ ( m )} = { g k : d ′ ∣ k , ( d , k / d ′ ) = 1 , 1 ≤ k / d ′ ≤ d } . 这些元素对应的 k ′ = k / d ′ k'=k/d' k ′ = k / d ′ d d d d d d φ ( d ) \varphi(d) φ ( d )
原根存在定理
本节将建立如下原根存在定理：
定理
模 m m m m = 1 , 2 , 4 , p e , 2 p e m=1,2,4,p^e,2p^e m = 1 , 2 , 4 , p e , 2 p e p p p e ∈ N + e\in\mathbf N_+ e ∈ N +
为说明这一结论，需要分别讨论如下四种情形：
m = 1 , 2 , 4 m=1,2,4 m = 1 , 2 , 4 g = 0 , 1 , 3 g=0,1,3 g = 0 , 1 , 3
m = p e m=p^{e} m = p e p p p e ∈ N + e\in\mathbf N_+ e ∈ N +
???+ note "引理 1"
对于奇素数 p p p p p p
??? note "证明"
证明分为两步．
**第一步**：对于 $d \mid (p-1 )$，同余方程 $x ^d\equiv 1 \pmod p $ 恰有 $d $ 个互不相同的解．
令 $p-1 =kd$，多项式
$$
f (x) = x ^{d (k-1 )} + x ^{d (k-2 )} + \cdots + x ^d + 1 .
$$
根据 [欧拉定理] (/knowledge-pages/math-number-theory-fermat#欧拉定理)，同余方程 $(x^d-1 )f (x)=x ^{p -1 }-1 \equiv 0 \pmod{p }$ 恰有 $p-1 $ 个互不相同的解．这些解分别是 $x ^d-1 $ 和 $f (x)$ 的零点．由 [Lagrange 定理] (/knowledge-pages/math-number-theory-congruence-equation#定理-3 lagrange-定理)，它们分别至多只能有 $d $ 个和 $d (k-1 )$ 个互不相同的零点．由于 $d +d (k-1 )=p -1 $，前者只能恰好有 $d $ 个互不相同的零点．这说明同余方程 $x ^d\equiv 1 \pmod p $ 恰有 $d $ 个互不相同的解．
**第二步**：对于 $d \mid (p-1 )$，$d $ 阶元素恰好有 $\varphi (d)$ 个．
对于 $\varphi (p)$ 的所有因子排序，然后应用归纳法．因为 $1 $ 阶元素只能是 $1 $，只有一个，归纳起点成立．对于 $d \mid (p-1 )$，根据前文的 [性质 2] (#ord-prop-2 )，同余方程 $x ^d\equiv 1 \pmod p $ 的解一定满足 $\delta_p (x)\mid d$．因此，其中 $d $ 阶元素个数为
$$
N (d) = d - \sum_{e\mid d,~e\neq d} N (e) = d - \sum_{e\mid d,~e\neq d} \varphi (e) = \varphi (d).
$$
第二个等号是归纳假设，第三个等号是欧拉函数的性质．由数学归纳法，就知道对于所有 $d \mid (p-1 )$，都恰有 $\varphi (d)$ 个 $d $ 阶元素．
特别地，对于 $d =p -1 $，恰有 $\varphi (p-1 )$ 个 $(p-1 )$ 阶元素．因此，模 $p $ 的原根存在．
???+ note "引理 2"
对于奇素数 p p p e ∈ N + e \in \mathbf{N}_+ e ∈ N + p e p^e p e
??? note "证明"
证明分为三步．
**第一步**：存在模 $p $ 的原根 $g $，使得 $g ^{p -1 }\not\equiv 1 \pmod{p ^2 }$．
任取一个模 $p $ 的原根 $g $．如果它不符合条件，即 $g ^{p -1 }\equiv 1 \pmod{p ^2 }$，那么，可以证明 $g +p $ 符合条件：$g +p $ 也是模 $p $ 的原根，且
$$
\begin{aligned}
(g +p )^{p -1 } &\equiv \binom{p -1 }{0 }g ^{p -1 } + \binom{p -1 }{1 }g ^{p -2 }p \\
&= g ^{p -1 } + g ^{p -2 }p (p -1 ) \\
&\equiv 1 - pg^{p -2 } \not\equiv 1 \pmod{p ^2 }.
\end{aligned}
$$
**第二步**：上文选取的 $g $，对于任意 $e\ge 1 $，都有 $g ^{\varphi(p ^e)}\not\equiv 1 \pmod{p ^{e+1 }}$．
对 $g $ 的选取保证了 $e=1 $ 时，该式成立．假设该式对于 $e$ 的情形成立，现要证明 $e+1 $ 的情形也成立．对于任意 $e \ge 1 $，由欧拉定理可知，存在 $\lambda$ 使得
$$
g ^{\varphi(p ^e)} = 1 + \lambda p ^e
$$
成立．由归纳假设，$\lambda\perp p $．因为 $\varphi(p ^{e+1 })=p \varphi(p ^e)$，所以
$$
g ^{\varphi(p ^{e+1 })} = \left (g ^{\varphi(p ^{e})}\right )^p = (1 + \lambda p ^e)^p \equiv 1 + \lambda p ^{e+1 } \pmod{p ^{e+2 }}.
$$
结合 $\lambda\perp p $ 可知，$g ^{\varphi(p ^{e+1 })}\not\equiv 1 \pmod{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 \pmod{p ^{e+1 }}$，必然也有 $g ^\delta\equiv 1 \pmod{p ^e}$．由归纳假设可知，$\delta_{p ^e}(g ) = \varphi(p ^e)$．因此，由前文阶的 [性质 2] (#ord-prop-2 )，就有 $\varphi(p ^e)\mid\delta$．又由欧拉定理可知，$\delta\mid\varphi(p ^{e+1 })$．但是，$\varphi(p ^{e+1 })=p \varphi(p ^e)$．因此，只有两种可能：$\delta=\varphi(p ^e)$ 或 $\delta=\varphi(p ^{e+1 })$．但是，第二步的结论说明，$g ^{\varphi(p ^e)}\not\equiv 1 \pmod{p ^{e+1 }}$．因此，可能性 $\delta=\varphi(p ^e)$ 并不成立．唯一的可能性就是 $\delta=\varphi(p ^{e+1 })$．这就说明 $g $ 是 $p ^{e+1 }$ 的原根．由数学归纳法，命题对于所有 $e\ge 1 $ 都成立．
m = 2 p e m=2p^{e} m = 2 p e p p p e ∈ N + e\in\mathbf N_+ e ∈ N +
???+ note "引理 3"
对于奇素数 p p p e ∈ N + e \in \mathbf{N}_+ e ∈ N + 2 p e 2p^e 2 p e
??? note "证明"
设 g g g p e p^{e} p e g + p e g+p^e g + p e p e p^{e} p e g g g ( g , 2 p e ) = 1 (g,2p^e)=1 ( g , 2 p e ) = 1 δ = δ 2 p e ( g ) \delta=\delta_{2p^e}(g) δ = δ 2 p e ( g ) δ = φ ( 2 p e ) \delta=\varphi(2p^e) δ = φ ( 2 p e ) δ ∣ φ ( 2 p e ) \delta\mid\varphi(2p^e) δ ∣ φ ( 2 p e ) g δ ≡ 1 ( m o d 2 p e ) g^\delta\equiv 1\pmod{2p^e} g δ ≡ 1 ( mod 2 p e ) g δ ≡ 1 ( m o d p e ) g^\delta\equiv 1\pmod{p^e} g δ ≡ 1 ( mod p e ) 性质 2 和 g g g δ p e ( g ) = φ ( p e ) ∣ δ \delta_{p^e}(g)=\varphi(p^e)\mid \delta δ p e ( g ) = φ ( p e ) ∣ δ φ ( 2 p e ) = φ ( p e ) \varphi(2p^e) = \varphi(p^e) φ ( 2 p e ) = φ ( p e ) δ = δ 2 p e ( g ) = φ ( p e ) \delta=\delta_{2p^e}(g)=\varphi(p^e) δ = δ 2 p e ( g ) = φ ( p e ) δ \delta δ 2 p e 2p^e 2 p e
m ≠ 1 , 2 , 4 , p e , 2 p e m\ne 1,2,4,p^{e},2p^{e} m = 1 , 2 , 4 , p e , 2 p e p p p e ∈ N + e\in\mathbf N_+ e ∈ N +
???+ note "引理 4"
假设 m ≠ 1 , 2 , 4 m\neq 1,2,4 m = 1 , 2 , 4 p p p e e e m = p e m=p^e m = p e m = 2 p e m=2p^e m = 2 p e m m m
??? note "证明"
对于 m = 2 e m=2^e m = 2 e e ≥ 3 e\ge 3 e ≥ 3 m m m g g g g ⊥ m g\perp m g ⊥ m g = 2 k + 1 g=2k+1 g = 2 k + 1 k ∈ N k\in\mathbf N k ∈ N
$$
\begin {aligned}
g^{2 ^{e-2 }}
&=(2k+1 )^{2 ^{e-2 }} \\
&\equiv 1 + \binom{2 ^{e-2 }}{1 }(2k) + \binom{{2 ^{e-2 }}}{2 }(2k)^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 ) \\
&\equiv 1 \pmod{2 ^{e}}.
\end {aligned}
$$
倒数第二行中，因为 $k$ 与 $( 2 ^{e-2 }-1 )k^2 $ 奇偶性相同，所以它们的和是偶数．由阶的定义可知，$\ delta_{2 ^{e}}(g)\le 2 ^{e-2 }< \varphi(2 ^{e}) = 2 ^{e-1 }$． 这与假设中 $g$ 是原根矛盾．由反证法，这样的原根并不存在．
假设 $m$ 满足所述条件，且不是 $2 $ 的幂，那么，一定存在 $2 < m_1 < m_2$ 且 $m_1 \perp m_2$ 使得 $m =m_1m_2$ 成立．假设模 $m$ 的原根 $g$ 存在．因为 $g \perp m$， 所以对于 $i =1 ,2 $， 都有 $g \perp m_i$． 由欧拉定理可知，
$$
g^{\varphi(m_i)} \equiv 1 \pmod{m_i}.
$$
由于 $m_i > 2 $， 所以 $\ varphi(m_i)$ 为偶数，所以，对于 $i =1 ,2 $， 有
$$
g^{\frac{1 }{2 }\varphi(m_1)\varphi(m_2)} \equiv 1 \pmod{m_i}.
$$
由 [中国剩余定理](/knowledge-pages/math -number-theory-crt) 可知
$$
g^{\frac{1 }{2 }\varphi(m_1)\varphi(m_2)} \equiv 1 \pmod{m}.
$$
又因为 $\ varphi(m)=\varphi(m_1)\varphi(m_2)$， 所以由阶的定义可知
$$
\delta_m(g) \le \frac{1 }{2 }\varphi(m_1)\varphi(m_2) = \dfrac{1 }{2 }\varphi(m) < \varphi(m).
$$
这与 $g$ 是模 $m$ 的原根的假设矛盾．故而，由反证法知，模 $m$ 的原根不存在．
综合以上四个引理，我们便给出了一个数存在原根的充要条件．
求原根的算法
对于任何存在原根的模数 m m m g g g
从小到大逐一枚举时，得到的是模 m m m g m g_m g m g m g_m g m
上界的估计：王元1 2 p p p g p = O ( p 0.25 + ϵ ) g_p=O\left(p^{0.25+\epsilon}\right) g p = O ( p 0.25 + ϵ ) ϵ > 0 \epsilon>0 ϵ > 0 3 4 p 2 p^2 p 2 2 p 2 2p^2 2 p 2 p p p e > 2 e>2 e > 2 p 2 p^2 p 2 2 p 2 2p^2 2 p 2 p e p^e p e 2 p e 2p^e 2 p e O ( p 0.25 + ϵ ) O\left(p^{0.25+\epsilon}\right) O ( p 0.25 + ϵ )
下界的估计：Fridlander5 6 C > 0 C>0 C > 0 p p p g p > C log p g_p > C\log p g p > C log p
平均情形的估计：Burgess and Elliott7 p p p g p = O ( ( log p ) 2 ( log log p ) 4 ) g_p=O((\log p)^2(\log\log p)^4) g p = O (( log p ) 2 ( log log p ) 4 ) 8 p p p 9 4.926 4.926 4.926 4 2 p 2 2p^2 2 p 2
根据这些分析，暴力寻找最小原根时，枚举部分的复杂度 O ( g m ( log m ) 2 ) O(g_m(\log m)^2) O ( g m ( log m ) 2 )
除了从小到大枚举外，还可以通过随机生成正整数并验证的方法寻找原根．原根的密度并不低：10
φ ( φ ( m ) ) m = Ω ( 1 log log m ) . \dfrac{\varphi(\varphi(m))}{m} = \Omega\left(\dfrac{1}{\log\log m}\right). m φ ( φ ( m )) = Ω ( log log m 1 ) . 所以，通过随机方法寻找原根时，枚举部分的期望复杂度为 O ( ( log m ) 2 log log m ) O((\log m)^2\log\log m) O (( log m ) 2 log log m )
需要注意的是，判定原根时需要已知 φ ( m ) \varphi(m) φ ( m ) 常用质因数分解算法 中，复杂度最优的 Pollard Rho 算法也需要 O ( m 1 / 4 + ε ) O(m^{1/4+\varepsilon}) O ( m 1/4 + ε ) φ ( m ) \varphi(m) φ ( m )
Carmichael 函数
相对于模 m m m m m m
Carmichael 函数
对于 m ∈ N + m\in\mathbf N_+ m ∈ N + λ ( m ) \lambda(m) λ ( m ) a n ≡ 1 ( m o d m ) a^n\equiv 1\pmod m a n ≡ 1 ( mod m ) a ⊥ m a\perp m a ⊥ m n n n λ : N + → N + \lambda:\mathbf N_+\to\mathbf N_+ λ : N + → N + Carmichael 函数 ．
根据 性质 2 ，能够使得 a n ≡ 1 ( m o d m ) a^n\equiv 1\pmod m a n ≡ 1 ( mod m ) a ⊥ m a\perp m a ⊥ m δ m ( a ) ∣ n \delta_m(a)\mid n δ m ( a ) ∣ n a ⊥ m a\perp m a ⊥ m n n n δ m ( a ) \delta_m(a) δ m ( a ) n n n
λ ( m ) = lcm { δ m ( a ) : a ⊥ m } . \lambda(m) = \operatorname{lcm}\{\delta_m(a) : a\perp m\}. λ ( m ) = lcm { δ m ( a ) : a ⊥ m } . 这也常用作 Carmichael 函数的等价定义．
反复应用 性质 5 可知，一定存在某个元素 a ⊥ m a\perp m a ⊥ m δ m ( a ) = λ ( m ) \delta_m(a)=\lambda(m) δ m ( a ) = λ ( m )
λ ( m ) = max { δ m ( a ) : a ⊥ m } . \lambda(m) = \max\{\delta_m(a) : a\perp m\}. λ ( m ) = max { δ m ( a ) : a ⊥ m } . 取得这一最值的元素 a ⊥ m a\perp m a ⊥ m m m m λ \lambda λ m m m
递推公式
Carmichael 函数是一个 数论函数 ．本节讨论它的一个递推公式，并由此给出原根存在定理的另一个证明．
虽然不是积性函数，但是计算 Carmichael 函数时，同样可以对互素的因子分别处理．
引理
对于互素的正整数 m 1 , m 2 m_1,m_2 m 1 , m 2 λ ( m 1 m 2 ) = [ λ ( m 1 ) , λ ( m 2 ) ] \lambda(m_1m_2)=[\lambda(m_1),\lambda(m_2)] λ ( m 1 m 2 ) = [ λ ( m 1 ) , λ ( m 2 )]
证明
设 a 1 a_1 a 1 a 2 a_2 a 2 m 1 m_1 m 1 m 2 m_2 m 2 λ \lambda λ m = m 1 m 2 m=m_1m_2 m = m 1 m 2 中国剩余定理 可知，存在 a ⊥ m a\perp m a ⊥ m a ≡ a i ( m o d m i ) a\equiv a_i\pmod{m_i} a ≡ a i ( mod m i ) i = 1 , 2 i=1,2 i = 1 , 2 a λ ( m ) ≡ 1 ( m o d m ) a^{\lambda(m)}\equiv 1\pmod m a λ ( m ) ≡ 1 ( mod m ) i = 1 , 2 i=1,2 i = 1 , 2 a i λ ( m ) ≡ 1 ( m o d m i ) a_i^{\lambda(m)} \equiv 1\pmod{m_i} a i λ ( m ) ≡ 1 ( mod m i ) 性质 2 和 a i a_i a i λ ( m i ) = δ m i ( a i ) ∣ λ ( m ) \lambda(m_i)=\delta_{m_i}(a_i)\mid \lambda(m) λ ( m i ) = δ m i ( a i ) ∣ λ ( m ) [ λ ( m 1 ) , λ ( m 2 ) ] ∣ λ ( m ) [\lambda(m_1),\lambda(m_2)]\mid\lambda(m) [ λ ( m 1 ) , λ ( m 2 )] ∣ λ ( m )
反过来，对于任意 a ⊥ m a\perp m a ⊥ m i = 1 , 2 i=1,2 i = 1 , 2 a [ λ ( m 1 ) , λ ( m 2 ) ] ≡ 1 ( m o d m i ) a^{[\lambda(m_1),\lambda(m_2)]} \equiv 1 \pmod{m_i} a [ λ ( m 1 ) , λ ( m 2 )] ≡ 1 ( mod m i ) a [ λ ( m 1 ) , λ ( m 2 ) ] ≡ 1 ( m o d m ) a^{[\lambda(m_1),\lambda(m_2)]} \equiv 1 \pmod{m} a [ λ ( m 1 ) , λ ( m 2 )] ≡ 1 ( mod m ) a ⊥ m a\perp m a ⊥ m λ ( m ) ∣ [ λ ( m 1 ) , λ ( m 2 ) ] \lambda(m)\mid [\lambda(m_1),\lambda(m_2)] λ ( m ) ∣ [ λ ( m 1 ) , λ ( m 2 )]
由此，命题中的等式成立．
因此，接下来只要计算 Carmichael 函数在素数幂处的取值．首先，处理 2 2 2
引理
对于 m = 2 e m=2^e m = 2 e e ∈ N + e\in\mathbf N_+ e ∈ N + λ ( 2 ) = 1 \lambda(2)=1 λ ( 2 ) = 1 λ ( 4 ) = 2 \lambda(4)=2 λ ( 4 ) = 2 e ≥ 3 e\ge 3 e ≥ 3 λ ( m ) = 2 e − 2 \lambda(m)=2^{e-2} λ ( m ) = 2 e − 2
证明
对于 m = 2 , 4 m=2,4 m = 2 , 4 m = 2 e m=2^e m = 2 e e ≥ 3 e\ge 3 e ≥ 3 引理 4 的证明的第一部分，就得到 λ ( m ) ≤ 2 e − 2 \lambda(m)\le 2^{e-2} λ ( m ) ≤ 2 e − 2 2 e − 2 2^{e-2} 2 e − 2
5 2 e − 3 = ( 1 + 2 2 ) 2 e − 3 = 1 + 2 2 × 2 e − 3 = 1 + 2 e − 1 ≢ 1 ( m o d 2 e ) . 5^{2^{e-3}} = (1 + 2^2)^{2^{e-3}} = 1 + 2^2\times 2^{e-3} = 1 + 2^{e-1} \not\equiv 1 \pmod{2^e}. 5 2 e − 3 = ( 1 + 2 2 ) 2 e − 3 = 1 + 2 2 × 2 e − 3 = 1 + 2 e − 1 ≡ 1 ( mod 2 e ) . 这说明 δ m ( 5 ) ∤ 2 e − 3 \delta_m(5)\nmid 2^{e-3} δ m ( 5 ) ∤ 2 e − 3 δ m ( 5 ) ∣ 2 e − 2 \delta_m(5) \mid 2^{e-2} δ m ( 5 ) ∣ 2 e − 2 5 5 5 2 e − 2 2^{e-2} 2 e − 2 λ ( m ) = 2 e − 2 \lambda(m)=2^{e-2} λ ( m ) = 2 e − 2
在这个引理的证明过程中，实际上得到了关于模 2 e 2^e 2 e
推论
设模数为 2 e 2^e 2 e e ≥ 2 e \ge 2 e ≥ 2 ± 5 k \pm 5^k ± 5 k k ∈ N k\in\mathbf N k ∈ N k < 2 e − 2 k < 2^{e-2} k < 2 e − 2 ± 1 , ± 5 , ⋯ , ± 5 2 e − 2 − 1 \pm 1,\pm 5,\cdots,\pm 5^{2^{e-2}-1} ± 1 , ± 5 , ⋯ , ± 5 2 e − 2 − 1
证明
容易验证，e = 2 e=2 e = 2 e ≥ 3 e \ge 3 e ≥ 3 5 5 5 2 e 2^e 2 e 2 e − 2 2^{e-2} 2 e − 2 1 , 5 , ⋯ , 5 2 e − 2 − 1 1,5,\cdots,5^{2^{e-2}-1} 1 , 5 , ⋯ , 5 2 e − 2 − 1 4 4 4 1 1 1 4 4 4 3 3 3 ± 1 , ± 5 , ⋯ , ± 5 2 e − 2 − 1 \pm 1,\pm 5,\cdots,\pm 5^{2^{e-2}-1} ± 1 , ± 5 , ⋯ , ± 5 2 e − 2 − 1 2 e 2^e 2 e 2 e − 1 2^{e-1} 2 e − 1 2 e 2^{e} 2 e
然后，处理奇素数幂的情形．
引理
对于 m = p e m=p^e m = p e p p p e ∈ N + e\in\mathbf N_+ e ∈ N + λ ( m ) = p e − 1 ( p − 1 ) \lambda(m)=p^{e-1}(p-1) λ ( m ) = p e − 1 ( p − 1 )
证明
首先证明命题对于 e = 1 e=1 e = 1 m = p m=p m = p p p p a a a x λ ( p ) ≡ 1 ( m o d p ) x^{\lambda(p)}\equiv 1\pmod{p} x λ ( p ) ≡ 1 ( mod p ) p p p p − 1 p-1 p − 1 Lagrange 定理 可知，p − 1 ≤ λ ( p ) p-1\le\lambda(p) p − 1 ≤ λ ( p ) λ ( p ) ∣ φ ( p ) = p − 1 \lambda(p)\mid\varphi(p)=p-1 λ ( p ) ∣ φ ( p ) = p − 1 λ ( p ) = p − 1 \lambda(p)=p-1 λ ( p ) = p − 1
对于 m = p e m=p^e m = p e e > 1 e> 1 e > 1 1 + p 1+p 1 + p p e − 1 p^{e-1} p e − 1
( 1 + p ) p e − 1 ≡ 1 , ( 1 + p ) p e − 2 ≡ 1 + p e − 1 ≢ 1 ( m o d p e ) . (1+p)^{p^{e-1}} \equiv 1,\quad (1+p)^{p^{e-2}} \equiv 1 + p^{e-1} \not\equiv 1 \pmod{p^e}. ( 1 + p ) p e − 1 ≡ 1 , ( 1 + p ) p e − 2 ≡ 1 + p e − 1 ≡ 1 ( mod p e ) . 所以，δ m ( 1 + p ) = p e − 1 \delta_m(1+p)=p^{e-1} δ m ( 1 + p ) = p e − 1 p p p g g g g δ m ( g ) ≡ 1 ( m o d p ) g^{\delta_m(g)}\equiv 1 \pmod{p} g δ m ( g ) ≡ 1 ( mod p ) 性质 2 可知，p − 1 ∣ δ m ( p ) p-1\mid\delta_m(p) p − 1 ∣ δ m ( p )
p e − 1 ( p − 1 ) = [ δ m ( p ) , p e − 1 ] ∣ λ ( m ) ∣ φ ( m ) = p e − 1 ( p − 1 ) . p^{e-1}(p-1) = [\delta_m(p),p^{e-1}]\mid\lambda(m) \mid \varphi(m) = p^{e-1}(p-1). p e − 1 ( p − 1 ) = [ δ m ( p ) , p e − 1 ] ∣ λ ( m ) ∣ φ ( m ) = p e − 1 ( p − 1 ) . 因此，λ ( m ) = p e − 1 ( p − 1 ) \lambda(m)=p^{e-1}(p-1) λ ( m ) = p e − 1 ( p − 1 )
将本节的结果简单归纳，就得到 Carmichael 函数的递推公式：
定理
对于任意正整数 m m m
λ ( 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 . \lambda(m) = \begin{cases}
\varphi(m), & \text{if }m=1,2,4,p^e\text{ for odd prime }p\text{ and }e \ge 1,\\
\frac{1}{2}\varphi(m), &\text{if }m=2^e,~e\ge 3,\\
\operatorname{lcm}\{\lambda(p_1^{e_1}),\lambda(p_2^{e_2}),\cdots,\lambda(p_s^{e_s})\}, &\text{if }m = p_1^{e_1}p_2^{e_2}\cdots p_s^{e_s}\text{ for distinct }p_1,p_2,\cdots,p_s.
\end{cases} λ ( m ) = ⎩ ⎨ ⎧ φ ( m ) , 2 1 φ ( m ) , lcm { λ ( p 1 e 1 ) , λ ( p 2 e 2 ) , ⋯ , λ ( p s e s )} , if m = 1 , 2 , 4 , p e for odd prime p and e ≥ 1 , if m = 2 e , e ≥ 3 , if m = p 1 e 1 p 2 e 2 ⋯ p s e s for distinct p 1 , p 2 , ⋯ , p s .
利用该递推公式可以加强前文的结果：
推论
对于正整数 m 1 , m 2 m_1,m_2 m 1 , m 2 λ ( [ m 1 , m 2 ] ) = [ λ ( m 1 ) , λ ( m 2 ) ] \lambda([m_1,m_2])=[\lambda(m_1),\lambda(m_2)] λ ([ m 1 , m 2 ]) = [ λ ( m 1 ) , λ ( m 2 )]
比较原根和 Carmichael 函数的定义可知，模 m m m λ ( m ) = φ ( m ) \lambda(m)=\varphi(m) λ ( m ) = φ ( m )
推论
模 m m m m = 1 , 2 , 4 , p e , 2 p e m=1,2,4,p^e,2p^e m = 1 , 2 , 4 , p e , 2 p e p p p e ∈ N + e\in\mathbf N_+ e ∈ N +
由于本节对于递推公式的证明并没有用到原根存在定理，因此，这就构成了对该定理的又一个证明．
Carmichael 数
利用 Carmichael 函数，可以讨论 Carmichael 数（卡迈克尔数，OEIS:A002997 ）的性质与分布．这是 Fermat 素性测试 一定无法正确排除的合数．
Carmichael 数
对于合数 n n n a ⊥ n a\perp n a ⊥ n a n − 1 ≡ 1 ( m o d n ) a^{n-1} \equiv 1 \pmod n a n − 1 ≡ 1 ( mod n ) n n n Carmichael 数 ．
最小的 Carmichael 数是 561 = 3 × 11 × 17 561 = 3 \times 11 \times 17 561 = 3 × 11 × 17
由 Carmichael 函数的定义可知，合数 n n n λ ( n ) ∣ n − 1 \lambda(n)\mid n-1 λ ( n ) ∣ n − 1 λ ( n ) \lambda(n) λ ( n ) n n n
Korselt 判别法11
合数 n n n n n n n n n p p p ( p − 1 ) ∣ ( n − 1 ) (p-1) \mid (n-1) ( p − 1 ) ∣ ( n − 1 )
证明
首先证明条件的必要性．假设 λ ( n ) ∣ ( n − 1 ) \lambda(n)\mid (n-1) λ ( n ) ∣ ( n − 1 ) n n n p p p p ∣ λ ( n ) p\mid \lambda(n) p ∣ λ ( n ) p ∤ ( n − 1 ) p\nmid (n-1) p ∤ ( n − 1 ) ( p − 1 ) ∣ λ ( n ) (p-1)\mid \lambda(n) ( p − 1 ) ∣ λ ( n ) ( p − 1 ) ∣ ( n − 1 ) (p-1) \mid (n-1) ( p − 1 ) ∣ ( n − 1 )
然后证明条件的充分性．因为 n n n p p p n − 1 n-1 n − 1 n n n n n n λ ( n ) = lcm { p − 1 : p ∣ n } \lambda(n)=\operatorname{lcm}\{p-1:p\mid n\} λ ( n ) = lcm { p − 1 : p ∣ n } ( p − 1 ) ∣ ( n − 1 ) (p-1) \mid (n-1) ( p − 1 ) ∣ ( n − 1 ) p p p λ ( n ) ∣ ( n − 1 ) \lambda(n)\mid (n-1) λ ( n ) ∣ ( n − 1 )
从这一判别法出发，可以建立 Carmichael 数的一些简单性质：
推论
Carmichael 数是奇数，没有平方因子，而且至少有 3 3 3
证明
前两条性质可以直接从 Korselt 判别法及其证明中得到．要得到第三条性质，只需要再证明：互异素数 p 1 , p 2 p_1,p_2 p 1 , p 2 n = p 1 p 2 n=p_1p_2 n = p 1 p 2 n = p 1 p 2 n=p_1p_2 n = p 1 p 2 ( p i − 1 ) ∣ ( n − 1 ) (p_i-1)\mid (n-1) ( p i − 1 ) ∣ ( n − 1 )
n − 1 = p 1 p 2 − 1 ≡ p 2 − 1 ( m o d p 1 − 1 ) . n-1=p_1p_2-1\equiv p_2-1 \pmod{p_1-1}. n − 1 = p 1 p 2 − 1 ≡ p 2 − 1 ( mod p 1 − 1 ) . 因此，( p 1 − 1 ) ∣ ( p 2 − 1 ) (p_1-1)\mid(p_2-1) ( p 1 − 1 ) ∣ ( p 2 − 1 ) ( p 2 − 1 ) ∣ ( p 1 − 1 ) (p_2-1)\mid(p_1-1) ( p 2 − 1 ) ∣ ( p 1 − 1 ) p 1 = p 2 p_1=p_2 p 1 = p 2 n n n 3 3 3
利用解析数论还可以得到 Carmichael 数分布的一些性质．设 C ( n ) C(n) C ( n ) n n n 12 n n n C ( n ) > n 2 / 7 C(n)>n^{2/7} C ( n ) > n 2/7 13 C ( n ) < n exp ( − c ln n ln ln ln n ln ln n ) C(n) < n\exp\left(-c\dfrac{\ln n\ln\ln\ln n}{\ln\ln n}\right) C ( n ) < n exp ( − c ln ln n ln n ln ln ln n ) c c c 14 C ( 10 9 ) = 646 C(10^9)=646 C ( 1 0 9 ) = 646 C ( 10 18 ) = 1 401 644 C(10^{18})=1~401~644 C ( 1 0 18 ) = 1 401 644
参考资料与注释