卡邁克爾函数\lambda(n)满足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\ge 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)\ge\lambda(n)，若\varphi(n)>\lambda(n)，则不存在阶为\varphi(n)的模n元素，即不存在原根。
参见
*卡邁克爾數
参考资料
评论 (0)