阶 & 原根 前置知识:费马小定理 、欧拉定理 、拉格朗日定理
阶和原根,是理解模 m 既约剩余系 Z m ∗ 乘法结构的重要工具.基于此,可以定义 离散对数 等概念.更为一般的讨论可以参见抽象代数部分 群论 和 环论 等页面相关章节.
阶 本节中,总是假设模数 m ∈ N + 和底数 a ∈ Z 互素,即 ( a , m ) = 1 ,也记作 a ⊥ m .
对于 n ∈ Z ,幂次 a n mod m 呈现一种循环结构.这个循环节的最小长度,就是 a 模 m 的阶.阶就定义为幂 a n mod m 第一次回到起点 a 0 mod m = 1 时的指数:
阶 对于 a ∈ Z , m ∈ N + 且 a ⊥ m ,满足同余式 a n ≡ 1 ( mod m ) 的最小正整数 n 称作 a 模 m 的阶 (the order of a modulo m ),记作 δ m ( a ) 或 ord m ( a ) .
注 在 抽象代数 中,这里的「阶」就是模 m 既约剩余系关于乘法形成的群中,元素 a 的阶.用记号 δ 表示阶只适用于这个特殊的群.下面的诸多性质可以直接推广到抽象代数中群元素的阶的性质.
另外还有「半阶」的概念,在数论中会用 δ − 记号表示.它是满足同余式 a n ≡ − 1 ( mod m ) 的最小正整数.半阶不是群论中的概念.阶一定存在,半阶不一定存在.
幂的循环结构 利用阶,可以刻画幂的循环结构.对于幂 a n mod m ,可以将指数 n 对阶 δ 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 ( mod m ) . 这说明,对于任意指数的幂,可以将它平移到第一个非负的循环节.由此,可以得到一系列关于阶的性质.
性质 1 对于 a ∈ Z , m ∈ N + 且 a ⊥ m ,幂次 a 0 ( = 1 ) , a , a 2 , ⋯ , a δ m ( a ) − 1 模 m 两两不同余.
证明 考虑反证.假设存在两个数 0 ≤ i < j < δ m ( a ) ,且 a i ≡ a j ( mod m ) ,则有 a j − i ≡ 1 ( mod m ) .但是,0 < j − i < δ m ( a ) .这与阶的最小性矛盾,故原命题成立.
性质 2 对于 a , n ∈ Z , m ∈ N + 且 a ⊥ m ,同余关系 a n ≡ 1 ( mod m ) 成立,当且仅当 δ m ( a ) ∣ n .
证明 如前文所述,a n ≡ a n mod δ m ( a ) ( mod m ) .由性质 1 可知,0 ≤ r < δ m ( a ) 中唯一一个使得 a r ≡ 1 ( mod m ) 成立的 r 就是 r = 0 .因此,a n ≡ 1 ( mod m ) ,当且仅当 n mod δ m ( a ) = 0 ,也就是 δ m ( a ) ∣ a .
欧拉定理 中,同余关系 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,同余关系 ( 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 可知
( 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 ≡ ( 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 ) . 由于两个整除关系的左侧互素,有
[ δ 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 ) ] . 这立马说明 ( δ m ( a ) , δ m ( b ) ) = 1 ,即 δ m ( a ) ⊥ δ m ( b ) .
一般情形中,性质 4 得到的界已经是紧的.乘积的阶取得下界的情形很容易构造:例如 ( a , b , m ) = ( 3 , 5 , 7 ) 时,δ m ( a ) = δ m ( b ) = 6 ,但是它们的乘积的阶 δ 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 γ 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 存在,那么,g , g 2 , ⋯ , g φ ( m ) 所在的同余类互不相同,构成模 m 既约剩余系.特别地,对于素数 p ,余数 g i mod p 对于 i = 1 , 2 , ⋯ , p − 1 两两不同.
注 在 抽象代数 中,原根就是循环群的生成元.这个概念只在模 m 既约剩余系关于乘法形成的群中有「原根」这个名字,在一般的循环群中都称作「生成元」.并非每个模 m 既约剩余系关于乘法形成的群都是循环群,存在原根就表明它同构于循环群,如果不存在原根就表明不同构.
模为 1 时,模 1 整数乘法群就是 { 0 } .这显然是循环群,所以原根就是 0 .
原根判定定理 如果已知模数 φ ( m ) 的全体素因子,那么很容易判断模 m 的原根是否存在.
定理 对于整数 m ≥ 3 和 g ⊥ m ,那么,g 是模 m 的原根,当且仅当对于 φ ( m ) 的每个素因数 p ,都有
g φ ( m ) p ≢ 1 ( mod m ) . 证明 必要性显然.为证明充分性,考虑使用反证法.如果 g 不是模 m 的原根,那么一定有 δ m ( g ) < φ ( m ) .由性质 2 和欧拉定理可知,δ m ( g ) ∣ φ ( m ) .由此,设 p 是 φ ( m ) δ m ( g ) 的一个素因子,就有 δ m ( g ) ∣ φ ( m ) p .再次应用性质 2 就得到
g φ ( m ) p ≡ 1 ( mod m ) . 但是,p 也是 φ ( m ) 的一个因子,这就与题设条件矛盾.由此,原命题的充分性成立.
原根个数 原根如果存在,也未必唯一.一般地,对于模 m 既约剩余系中所有元素可能的阶和某个阶的元素数量,有如下结论:
定理 如果正整数 m 有原根 g ,那么,当且仅当 d ∣ φ ( m ) 时,模 m 的 d 阶元素存在,且恰有 φ ( d ) 个.特别地,模 m 的原根个数为 φ ( φ ( m ) ) .
证明 根据原根的定义,所有模 m 的既约同余类都可以写作 g k mod m 的形式,且 k 是 1 , 2 , ⋯ , φ ( m ) 之一.由性质 3,这些元素的阶等于
δ m ( g k ) = φ ( m ) ( φ ( m ) , k ) . 因此,d 阶元素存在,当且仅当 d ∣ φ ( m ) .而且,对于 d ∣ φ ( m ) ,令 d ′ = φ ( m ) / d ,这些元素的集合就是
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 的原根存在,当且仅当 m = 1 , 2 , 4 , p e , 2 p e ,其中,p 是奇素数且 e ∈ N + .
为说明这一结论,需要分别讨论如下四种情形:
m = 1 , 2 , 4 ,原根分别是 g = 0 , 1 , 3 ,显然存在.
m = p e 是奇素数的幂,其中,p 为奇素数,e ∈ N + .
引理 1 对于奇素数 p ,模 p 的原根存在.
证明 证明分为两步.
第一步 :对于 d ∣ ( p − 1 ) ,同余方程 x d ≡ 1 ( mod p ) 恰有 d 个互不相同的解.
令 p − 1 = k d ,多项式
f ( x ) = x d ( k − 1 ) + x d ( k − 2 ) + ⋯ + x d + 1. 根据 欧拉定理 ,同余方程 ( x d − 1 ) f ( x ) = x p − 1 − 1 ≡ 0 ( mod p ) 恰有 p − 1 个互不相同的解.这些解分别是 x d − 1 和 f ( x ) 的零点.由 Lagrange 定理 ,它们分别至多只能有 d 个和 d ( k − 1 ) 个互不相同的零点.由于 d + d ( k − 1 ) = p − 1 ,前者只能恰好有 d 个互不相同的零点.这说明同余方程 x d ≡ 1 ( mod p ) 恰有 d 个互不相同的解.
第二步 :对于 d ∣ ( p − 1 ) ,d 阶元素恰好有 φ ( d ) 个.
对于 φ ( m ) 的所有因子排序,然后应用归纳法.因为 1 阶元素只能是 1 ,只有一个,归纳起点成立.对于 d ∣ ( p − 1 ) ,根据前文的性质 2,同余方程 x d ≡ 1 ( mod m ) 的解一定满足 δ p ( x ) ∣ d .因此,其中 d 阶元素个数为
N ( d ) = d − ∑ e ∣ d , e ≠ d N ( e ) = d − ∑ e ∣ d , e ≠ d φ ( e ) = φ ( d ) . 第二个等号是归纳假设,第三个等号是欧拉函数的性质.由数学归纳法,就知道对于所有 d ∣ ( p − 1 ) ,都恰有 φ ( d ) 个 d 阶元素.
特别地,对于 d = p − 1 ,恰有 φ ( p − 1 ) 个 ( p − 1 ) 阶元素.因此,模 p 的原根存在.
引理 2 对于奇素数 p 和 e ∈ N + ,模 p e 的原根存在.
证明 证明分为三步.
第一步 :存在模 p 的原根 g ,使得 g p − 1 ≢ 1 ( mod p 2 ) .
任取一个模 p 的原根 g .如果它不符合条件,即 g p − 1 ≡ 1 ( mod p 2 ) ,那么,可以证明 g + p 符合条件:g + p 也是模 p 的原根,且
( 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 ,对于任意 e ≥ 1 ,都有 g φ ( p e ) ≢ 1 ( mod p e + 1 ) .
对 g 的选取保证了 e = 1 时,该式成立.假设该式对于 e 的情形成立,现要证明 e + 1 的情形也成立.对于任意 e ≥ 1 ,由欧拉定理可知,存在 λ 使得
g φ ( p e ) = 1 + λ p e 成立.由归纳假设,λ ⊥ p .因为 φ ( p e + 1 ) = p φ ( p e ) ,所以
g φ ( p e + 1 ) = ( g φ ( p e ) ) p = ( 1 + λ p e ) p ≡ 1 + λ p e + 1 ( mod p e + 2 ) . 结合 λ ⊥ p 可知,g φ ( p e + 1 ) ≢ 1 ( mod p e + 2 ) .由数学归纳法可知,命题成立.
第三步 :上文选取的 g ,对于任意 e ≥ 1 ,都是模 p e 的原根.
对 g 的选取保证了 e = 1 时,命题成立.假设命题对于 e 成立,现在要证明命题对于 e + 1 也成立.将 δ p e + 1 ( g ) 简记为 δ .由于 g δ ≡ 1 ( mod p e + 1 ) ,必然也有 g δ ≡ 1 ( mod p e ) .由归纳假设可知,δ p e ( g ) = φ ( p e ) .因此,由前文阶的性质 2,就有 φ ( p e ) ∣ δ .又由欧拉定理可知,δ ∣ φ ( p e + 1 ) .但是,φ ( p e + 1 ) = p φ ( p e ) .因此,只有两种可能:δ = φ ( p e ) 或 δ = φ ( p e + 1 ) .但是,第二步的结论说明,g φ ( p e ) ≢ 1 ( mod p e + 1 ) .因此,可能性 δ = φ ( p e ) 并不成立.唯一的可能性就是 δ = φ ( p e + 1 ) .这就说明 g 是 p e + 1 的原根.由数学归纳法,命题对于所有 e ≥ 1 都成立.
m = 2 p e ,其中,p 为奇素数,e ∈ N + .
引理 3 对于奇素数 p 和 e ∈ N + ,模 2 p e 的原根存在.
证明 设 g 是模 p e 的原根,则 g + p e 也是模 p e 的原根.两者之间必然有一个是奇数,不妨设它就是 g .显然,( g , 2 p e ) = 1 .设 δ = δ 2 p e ( g ) ,需要证明 δ = φ ( 2 p e ) .由欧拉定理,δ ∣ φ ( 2 p e ) .同时,根据定义 g δ ≡ 1 ( mod 2 p e ) ,所以,g δ ≡ 1 ( mod p e ) ,因此,由阶的性质 2 和 g 的选取可知,δ p e ( g ) = φ ( p e ) ∣ δ .由欧拉函数表达式可知,φ ( 2 p e ) = φ ( p e ) .所以,δ = δ 2 p e ( g ) = φ ( p e ) .这就说明 δ 是模 2 p e 的原根.
m ≠ 1 , 2 , 4 , p e , 2 p e ,其中,p 为奇素数,e ∈ N + .
引理 4 假设 m ≠ 1 , 2 , 4 且不存在奇素数 p 和正整数 e 使得 m = p e 或 m = 2 p e .那么,模 m 的原根不存在.
证明 对于 m = 2 e 且 e ≥ 3 ,假设模 m 的原根 g 存在.由于 g ⊥ m ,它一定是奇数.假设 g = 2 k + 1 且 k ∈ N ,那么,有
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 e − 2 − 1 ) k 2 奇偶性相同,所以它们的和是偶数.由阶的定义可知,δ 2 e ( g ) ≤ 2 e − 2 < φ ( 2 e ) = 2 e − 1 .这与假设中 g 是原根矛盾.由反证法,这样的原根并不存在.
假设 m 满足所述条件,且不是 2 的幂,那么,一定存在 2 < m 1 < m 2 且 m 1 ⊥ m 2 使得 m = m 1 m 2 成立.假设模 m 的原根 g 存在.因为 g ⊥ m ,所以对于 i = 1 , 2 ,都有 g ⊥ m i .由欧拉定理可知,
g φ ( m i ) ≡ 1 ( mod m i ) . 由于 m i > 2 ,所以 φ ( m i ) 为偶数,所以,对于 i = 1 , 2 ,有
g 1 2 φ ( m 1 ) φ ( m 2 ) ≡ 1 ( mod m i ) . 由 中国剩余定理 可知
g 1 2 φ ( m 1 ) φ ( m 2 ) ≡ 1 ( mod m ) . 又因为 φ ( m ) = φ ( m 1 ) φ ( m 2 ) ,所以由阶的定义可知
δ m ( g ) ≤ 1 2 φ ( m 1 ) φ ( m 2 ) = 1 2 φ ( m ) < φ ( m ) . 这与 g 是模 m 的原根的假设矛盾.故而,由反证法知,模 m 的原根不存在.
综合以上四个引理,我们便给出了一个数存在原根的充要条件.
最小原根的范围估计 王元 和 Burgess 证明了素数 p 的最小原根 g p = O ( p 0.25 + ϵ ) ,其中 ϵ > 0 .Cohen, Odoni, and Stothers 和 Elliott and Murata 分别证明了该估计对于模数 p 2 和 2 p 2 也成立,其中,p 是奇素数.由于对于 e > 2 ,模 p 2 (或 2 p 2 )的原根也是模 p e (或 2 p e )的原根,所以,最小原根的上界 O ( p 0.25 + ϵ ) 对于所有情形都成立.
Fridlander 和 Salié 证明了素数 p 的最小原根 g p = Ω ( log p ) .
这保证了暴力找一个数的最小原根时,复杂度可以接受.
Carmichael 函数 相对于模 m 元素的阶这一局部概念,Carmichael 函数是一个全局概念.它是所有与 m 互素的整数的幂次的最小公共循环节.
Carmichael 函数 对于 m ∈ N + ,定义 λ ( m ) 为能够使得同余关系 a n ≡ 1 ( mod m ) 对于所有 a ⊥ m 都成立的最小正整数 n .函数 λ : N + → N + 就称为 Carmichael 函数 .
根据性质 2,能够使得 a n ≡ 1 ( mod m ) 对于所有 a ⊥ m 都成立,意味着 δ m ( a ) ∣ n 对于所有 a ⊥ m 都成立.也就是说,符合这一条件的正整数 n ,一定是全体 δ m ( a ) 的公倍数.因此,最小的这样的 n 就是它们的最小公倍数:
λ ( m ) = lcm { δ m ( a ) : a ⊥ m } . 这也常用作 Carmichael 函数的等价定义.
反复应用性质 5 可知,一定存在某个元素 a ⊥ m 使得 δ m ( a ) = λ ( m ) .因此,上式也可以写作
λ ( m ) = max { δ m ( a ) : a ⊥ m } . 取得这一最值的元素 a ⊥ m 也称为模 m 的 λ ‑原根 .它对于所有模数 m 都存在.
递推公式 Carmichael 函数是一个 数论函数 .本节讨论它的一个递推公式,并由此给出原根存在定理的另一个证明.
虽然不是积性函数,但是计算 Carmichael 函数时,同样可以对互素的因子分别处理.
引理 对于互素的正整数 m 1 , m 2 ,有 λ ( m 1 m 2 ) = [ λ ( m 1 ) , λ ( m 2 ) ] .
证明 设 a 1 和 a 2 分别为模 m 1 和模 m 2 的 λ ‑原根.令 m = m 1 m 2 ,由 中国剩余定理 可知,存在 a ⊥ m 使得 a ≡ a i ( mod m i ) 对于 i = 1 , 2 都成立.由于 a λ ( m ) ≡ 1 ( mod m ) ,所以对于 i = 1 , 2 ,都有 a i λ ( m ) ≡ 1 ( mod m i ) ,进而由性质 2 和 a i 的选取可知,λ ( m i ) = δ m i ( a i ) ∣ λ ( m ) .这就说明 [ λ ( m 1 ) , λ ( m 2 ) ] ∣ λ ( m ) .
反过来,对于任意 a ⊥ m 和 i = 1 , 2 ,都有 a [ λ ( m 1 ) , λ ( m 2 ) ] ≡ 1 ( mod m i ) .应用中国剩余定理,就得到 a [ λ ( m 1 ) , λ ( m 2 ) ] ≡ 1 ( mod m ) 对于所有 a ⊥ m 都成立.根据 Carmichael 函数的定义可知,λ ( m ) ∣ [ λ ( m 1 ) , λ ( m 2 ) ] .
由此,命题中的等式成立.
因此,接下来只要计算 Carmichael 函数在素数幂处的取值.首先,处理 2 的幂次的情形.
引理 对于 m = 2 e 且 e ∈ N + ,有 λ ( 2 ) = 1 ,λ ( 4 ) = 2 ,且对于 e ≥ 3 都有 λ ( m ) = 2 e − 2 .
证明 对于 m = 2 , 4 的情形,单独讨论即可.对于 m = 2 e 且 e ≥ 3 的情形,首先重复前文定理 4 的证明的第一部分,就得到 λ ( m ) ≤ 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 ( mod 2 e ) . 这说明 δ m ( 5 ) ∤ 2 e − 3 ,又因为 δ m ( 5 ) ∣ 2 e − 2 ,所以,5 只能是 2 e − 2 阶元素.这就说明,λ ( m ) = 2 e − 2 .
然后,处理奇素数幂的情形.
引理 对于 m = p e ,其中,p 是奇素数且 e ∈ N + ,有 λ ( m ) = p e − 1 ( p − 1 ) .
证明 首先证明命题对于 e = 1 ,即 m = p 是奇素数的情形成立.为此,由 Carmichael 函数的定义可知,与 p 互素的所有整数 a 都是同余方程 x λ ( p ) ≡ 1 ( mod p ) 的解.在模 p 的意义下,该方程共有 p − 1 个互不相同的解.根据 Lagrange 定理 可知,p − 1 ≤ λ ( p ) .同时,欧拉定理要求,λ ( p ) ∣ φ ( p ) = p − 1 .因此,λ ( p ) = p − 1 .
对于 m = p e 且 e > 1 的情形,可以从证明 1 + p 是 p e − 1 阶元开始.为此,有
( 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 .另外,设模 p 的原根为 g ,那么,由于 g δ m ( g ) ≡ 1 ( mod p ) ,所以,由阶的性质 2 可知,p − 1 ∣ δ m ( p ) .由 Carmichael 函数的定义和欧拉定理可知
p e − 1 ( p − 1 ) = [ δ m ( p ) , p e − 1 ] ∣ λ ( m ) ∣ φ ( m ) = p e − 1 ( p − 1 ) . 因此,λ ( m ) = p e − 1 ( p − 1 ) .
将本节的结果简单归纳,就得到 Carmichael 函数的递推公式:
定理 对于任意正整数 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 . 利用该递推公式可以加强前文的结果:
推论 对于正整数 m 1 , m 2 ,有 λ ( [ m 1 , m 2 ] ) = [ λ ( m 1 ) , λ ( m 2 ) ] .
比较原根和 Carmichael 函数的定义可知,模 m 的原根存在,当且仅当 λ ( m ) = φ ( m ) .从 Carmichael 函数的递推公式中,容易归纳出如下结果:
推论 模 m 的原根存在,当且仅当 m = 1 , 2 , 4 , p e , 2 p e ,其中,p 是奇素数且 e ∈ N + .
由于本节对于递推公式的证明并没有用到原根存在定理,因此,这就构成了对该定理的又一个证明.
Carmichael 数 利用 Carmichael 函数,可以讨论 Carmichael 数(卡迈克尔数,OEIS:A002997 )的性质与分布.这是 Fermat 素性测试 一定无法正确排除的合数.
Carmichael 数 对于合数 n ,如果对于所有整数 a ⊥ n 都有同余式 a n − 1 ≡ 1 ( mod n ) 成立,就称 n 为 Carmichael 数 .
最小的 Carmichael 数是 561 = 3 × 11 × 17 .
由 Carmichael 函数的定义可知,合数 n 是 Carmichael 数当且仅当 λ ( n ) ∣ n − 1 ,其中 λ ( n ) 为 Carmichael 函数.进一步地,可以得到如下判断合数 n 是否为 Carmichael 数的方法:
Korselt 判别法 合数 n 是 Carmichael 数当且仅当 n 无平方因子且对 n 的任意质因子 p 均有 ( p − 1 ) ∣ ( n − 1 ) .
证明 首先证明条件的必要性.假设 λ ( n ) ∣ ( n − 1 ) .检查 Carmichael 函数的递推公式可知,如果 n 有平方因子 p ,那么,一定有 p ∣ λ ( n ) .但是 p ∤ ( n − 1 ) ,矛盾.同理,Carmichael 函数的递推公式说明,( p − 1 ) ∣ λ ( n ) ,所以,也有 ( p − 1 ) ∣ ( n − 1 ) .
然后证明条件的充分性.因为 n 是合数,所以它一定有奇素因子 p ,因此 n − 1 是偶数,n 也就一定是奇数.对于无平方因子的奇合数 n ,由 Carmichael 函数的递推公式可知,λ ( n ) = lcm { p − 1 : p ∣ n } .因此,只要 ( p − 1 ) ∣ ( n − 1 ) 对于所有素因子 p 都成立,就一定有 λ ( n ) ∣ ( n − 1 ) .
从这一判别法出发,可以建立 Carmichael 数的一些简单性质:
推论 Carmichael 数是奇数,没有平方因子,而且至少有 3 个不同的素因子.
证明 前两条性质可以直接从 Korselt 判别法及其证明中得到.要得到第三条性质,只需要再证明:互异素数 p 1 , p 2 的乘积 n = p 1 p 2 一定不是 Carmichael 数.假设 n = p 1 p 2 是 Carmichael 数.由 Korselt 判别法可知,( p i − 1 ) ∣ ( n − 1 ) .但是,有
n − 1 = p 1 p 2 − 1 ≡ p 2 − 1 ( mod p 1 − 1 ) . 因此,( p 1 − 1 ) ∣ ( p 2 − 1 ) .同理,( p 2 − 1 ) ∣ ( p 1 − 1 ) .也就是说,p 1 = p 2 .这与假设矛盾.因此,Carmichael 数 n 至少有 3 个互异素因子.
利用解析数论还可以得到 Carmichael 数分布的一些性质.设 C ( n ) 为小于等于 n 的 Carmichael 数个数.Alford, Granville, and Pomerance 证明,对于充分大的 n ,有 C ( n ) > n 2 / 7 .由此,Carmichael 数有无限多个.在这之前,Erdős 已经证明,C ( n ) < n exp ( − c ln n ln ln ln n ln ln n ) ,其中 c 为常数.因此,Carmichael 数的分布(相对于素数来说)十分稀疏.实际上,有 C ( 10 9 ) = 646 ,C ( 10 18 ) = 1 401 644 .
参考资料与注释 本页面最近更新:2025/8/30 15:23:07 ,更新历史 发现错误?想一起完善? 在 GitHub 上编辑此页! 本页面贡献者:Peanut-Tang , Early0v0 , Ir1d , StudyingFather , Tiphereth-A , Great-designer , MegaOwIer , Xeonacid , 2008verser , Enter-tainer , bobhan1 , c-forrest , CCXXXI , chuxin0816 , CroMarmot , GavinZhengOI , GeorgePlover , hhc0001 , huhaoo , Larry0716 , Marcythm , opsiff , ouuan , PeterlitsZo , ShelpAm , tml104 , wty-yy 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用