卡邁克爾函數

卡邁克爾函數$\lambda (n)$（OEIS數列A002322）滿足$a^{\lambda (n)}\equiv 1{\pmod {n}}$，其中a與n互質。

定義

當n為1、2、4、奇質數的次冪、奇質數的次冪的兩倍時為歐拉函數，當n為2,4以外的2的次冪時為它的一半。 $\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}}$

歐拉函數有$\varphi (p^{k})=p^{k-1}(p-1)$

由算術基本定理，正整數n可寫為質數的積$n=p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{\omega (n)}^{a_{\omega (n)}}$

對於所有n，$\lambda (n)$是它們最小公倍數：

$\lambda (n)=\operatorname {lcm} [\lambda (p_{1}^{a_{1}}),\;\lambda (p_{2}^{a_{2}}),\dots ,\lambda (p_{\omega (n)}^{a_{\omega (n)}})]$

例子

$\lambda (8)=2$

$7^{2}\equiv 1{\pmod {8}}$

證明

證明當a與n互質時，滿足$a^{\lambda (n)}\equiv 1{\pmod {n}}$

由費馬小定理得$a^{p-1}=1+hp$

$a^{p^{k-1}(p-1)}=1+hp^{k}$

$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)}\equiv 1{\pmod {p^{k}}}$成立，這是一般情況。

$a=1+2h$

$a^{2}=1+4h(h+1)=1+8C_{h+1}^{2}$

$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})$

由數學歸納法得當$k\geq 3$時，$a^{2^{k-2}}\equiv 1{\pmod {2^{k}}}$成立。

原根的充要條件

證明$\varphi (n)=\lambda (n)$為存在模n原根的充要條件。

而$\varphi (n)=\lambda (n)$當且僅當$n=1,2,4,p^{k},2p^{k}$（$p\neq 2$）

必要性

$\varphi (n)\geq \lambda (n)$，若$\varphi (n)>\lambda (n)$，則不存在階為$\varphi (n)$的模n元素，即不存在原根。

λ原根

階為$\lambda (n)$的模n元素為λ原根。模n的λ原根的個數參見 A111725。

當$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$

$5^{2^{k-3}}=(1+2^{2})^{2^{k-3}}=1+2^{k-1}+2^{k}I$

多項式除法

$(\prod p)^{k}|(x^{\lambda (\prod p)+1}-x)^{k}$

餘式：$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}}}$

參見

• 卡邁克爾數