卡邁克爾函數 λ ( n ) {\displaystyle \lambda (n)} （OEIS數列A002322）滿足 a λ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}} ，其中a與n互質。 定義 當n為1、2、4、奇質數的次冪、奇質數的次冪的兩倍時為歐拉函數，當n為2,4以外的2的次冪時為它的一半。 λ ( n ) = { φ ( n ) n = 1 , 2 , 3 , 4 , 5 , 6 , 7 , 9 , 10 , 11 , 13 , 14 , 17 , 19 , 22 , 23 , 25 , 26 , 27 , 29 … 1 2 φ ( n ) n = 8 , 16 , 32 , 64 , 128 , 256 … {\displaystyle \lambda (n)={\begin{cases}\varphi (n)&n=1,2,3,4,5,6,7,9,10,11,13,14,17,19,22,23,25,26,27,29\dots \\{\dfrac {1}{2}}\varphi (n)&n=8,16,32,64,128,256\dots \end{cases}}} 歐拉函數有 φ ( p k ) = p k − 1 ( p − 1 ) {\displaystyle \varphi (p^{k})=p^{k-1}(p-1)} 由算術基本定理，正整數n可寫為質數的積 n = p 1 a 1 p 2 a 2 … p ω ( n ) a ω ( n ) {\displaystyle n=p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{\omega (n)}^{a_{\omega (n)}}} 對於所有n， λ ( n ) {\displaystyle \lambda (n)} 是它們最小公倍數： λ ( n ) = lcm [ λ ( p 1 a 1 ) , λ ( p 2 a 2 ) , … , λ ( p ω ( n ) a ω ( n ) ) ] {\displaystyle \lambda (n)=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{\omega (n)}^{a_{\omega (n)}})]} 例子 λ ( 8 ) = 2 {\displaystyle \lambda (8)=2} 7 2 ≡ 1 ( mod 8 ) {\displaystyle 7^{2}\equiv 1{\pmod {8}}} 證明 證明當a與n互質時，滿足 a λ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}} 由費馬小定理得 a p − 1 = 1 + h p {\displaystyle a^{p-1}=1+hp} a p k − 1 ( p − 1 ) = 1 + h p k {\displaystyle a^{p^{k-1}(p-1)}=1+hp^{k}} a p k ( p − 1 ) = ( 1 + h p k ) p = 1 + h p p k + 1 + ⋯ = 1 + h 0 p k + 1 {\displaystyle a^{p^{k}(p-1)}=(1+hp^{k})^{p}=1+h^{p}p^{k+1}+\dots =1+h_{0}p^{k+1}} 由數學歸納法得 a p k − 1 ( p − 1 ) ≡ 1 ( mod p k ) {\displaystyle a^{p^{k-1}(p-1)}\equiv 1{\pmod {p^{k}}}} 成立，這是一般情況。 a = 1 + 2 h {\displaystyle a=1+2h} a 2 = 1 + 4 h ( h + 1 ) = 1 + 8 C h + 1 2 {\displaystyle a^{2}=1+4h(h+1)=1+8C_{h+1}^{2}} a 2 k − 2 = 1 + 2 k h {\displaystyle a^{2^{k-2}}=1+2^{k}h} a 2 k − 1 = ( 1 + 2 k h ) 2 = 1 + 2 k + 1 ( h + 2 k − 1 h 2 ) {\displaystyle a^{2^{k-1}}=(1+2^{k}h)^{2}=1+2^{k+1}(h+2^{k-1}h^{2})} 由數學歸納法得當 k ≥ 3 {\displaystyle k\geq 3} 時， a 2 k − 2 ≡ 1 ( mod 2 k ) {\displaystyle a^{2^{k-2}}\equiv 1{\pmod {2^{k}}}} 成立。 [1] 原根的充要條件 證明 φ ( n ) = λ ( n ) {\displaystyle \varphi (n)=\lambda (n)} 為存在模n原根的充要條件。 而 φ ( n ) = λ ( n ) {\displaystyle \varphi (n)=\lambda (n)} 當且僅當 n = 1 , 2 , 4 , p k , 2 p k {\displaystyle n=1,2,4,p^{k},2p^{k}} （ p ≠ 2 {\displaystyle p\neq 2} ） 必要性 φ ( n ) ≥ λ ( n ) {\displaystyle \varphi (n)\geq \lambda (n)} ，若 φ ( n ) > λ ( n ) {\displaystyle \varphi (n)>\lambda (n)} ，則不存在階為 φ ( n ) {\displaystyle \varphi (n)} 的模n元素，即不存在原根。[1] λ原根 階為 λ ( n ) {\displaystyle \lambda (n)} 的模n元素為λ原根。模n的λ原根的個數參見 A111725。 當 n = 2 k , k > 2 {\displaystyle n=2^{k},k>2} 時，3、5為模n的λ原根，因而所有模8餘3或5的數都是模n的λ原根。 3 2 k − 3 = ( 2 2 − 1 ) 2 k − 3 = 1 − 2 k − 1 + 2 k I {\displaystyle 3^{2^{k-3}}=(2^{2}-1)^{2^{k-3}}=1-2^{k-1}+2^{k}I} [1] 5 2 k − 3 = ( 1 + 2 2 ) 2 k − 3 = 1 + 2 k − 1 + 2 k I {\displaystyle 5^{2^{k-3}}=(1+2^{2})^{2^{k-3}}=1+2^{k-1}+2^{k}I} [1] 多項式除法 ( ∏ p ) k | ( x λ ( ∏ p ) + 1 − x ) k {\displaystyle (\prod p)^{k}|(x^{\lambda (\prod p)+1}-x)^{k}} 餘式： x λ ( ∏ p ) ( k + n ) + k ≡ ∑ i = 1 k ( − 1 ) i − 1 ( n + i − 1 i − 1 ) ( n + k k − i ) x λ ( ∏ p ) ( k − i ) + k ( mod ( ∏ p ) k ) {\displaystyle x^{\lambda (\prod p)(k+n)+k}\equiv \sum _{i=1}^{k}(-1)^{i-1}{\binom {n+i-1}{i-1}}{\binom {n+k}{k-i}}x^{\lambda (\prod p)(k-i)+k}{\pmod {(\prod p)^{k}}}} [2] 參見 卡邁克爾數 參考資料 [1]Robert Daniel Carmichael. The Theory of Numbers. Nabu Press. [2015-07-29]. ISBN 1144400341. （原始內容存檔於2020-12-02）. [2]黃嘉威. 多项式除法解高次同余. 數學學習與研究. 2015, (9): 第104頁 [2017-09-24]. （原始內容存檔於2020-10-20）. Wikiwand - on Seamless Wikipedia browsing. On steroids.
是它們最小公倍數：
![{\displaystyle \lambda (n)=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{\omega (n)}^{a_{\omega (n)}})]}](//wikimedia.org/api/rest_v1/media/math/render/svg/2c78b53f05addfe8fcc8dc26ce7d835e6314a0a7)
![{\displaystyle \lambda (n)=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{\omega (n)}^{a_{\omega (n)}})]}](http://wikimedia.org/api/rest_v1/media/math/render/svg/2c78b53f05addfe8fcc8dc26ce7d835e6314a0a7)
A111725。
