卡邁克爾函數

卡邁克爾函数${\displaystyle \lambda (n)}$（OEIS數列A002322）满足${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}$，其中a与n互质。

定义

当n为1、2、4、奇质数的次幂、奇质数的次幂的两倍时为欧拉函数，当n为2,4以外的2的次幂时为它的一半。 ${\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}}}$

欧拉函数有${\displaystyle \varphi (p^{k})=p^{k-1}(p-1)}$

由算术基本定理，正整数n可写为质数的积${\displaystyle n=p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{\omega (n)}^{a_{\omega (n)}}}$

对于所有n，${\displaystyle \lambda (n)}$是它们最小公倍數：

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

例子

${\displaystyle \lambda (8)=2}$

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

证明

证明当a与n互质时，满足${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}$

由费马小定理得${\displaystyle a^{p-1}=1+hp}$

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

${\displaystyle a^{p^{k}(p-1)}=(1+hp^{k})^{p}=1+h^{p}p^{k+1}+\dots =1+h_{0}p^{k+1}}$

由数学归纳法得${\displaystyle a^{p^{k-1}(p-1)}\equiv 1{\pmod {p^{k}}}}$成立，这是一般情况。

${\displaystyle a=1+2h}$

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

${\displaystyle a^{2^{k-2}}=1+2^{k}h}$

${\displaystyle a^{2^{k-1}}=(1+2^{k}h)^{2}=1+2^{k+1}(h+2^{k-1}h^{2})}$

由数学归纳法得当${\displaystyle k\geq 3}$时，${\displaystyle a^{2^{k-2}}\equiv 1{\pmod {2^{k}}}}$成立。 [1]

原根的充要条件

证明${\displaystyle \varphi (n)=\lambda (n)}$为存在模n原根的充要条件。

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

必要性

${\displaystyle \varphi (n)\geq \lambda (n)}$，若${\displaystyle \varphi (n)>\lambda (n)}$，则不存在阶为${\displaystyle \varphi (n)}$的模n元素，即不存在原根。[1]

λ原根

阶为${\displaystyle \lambda (n)}$的模n元素为λ原根。模n的λ原根的个数参见 A111725。

当${\displaystyle n=2^{k},k>2}$时，3、5为模n的λ原根，因而所有模8余3或5的数都是模n的λ原根。

${\displaystyle 3^{2^{k-3}}=(2^{2}-1)^{2^{k-3}}=1-2^{k-1}+2^{k}I}$[1]

${\displaystyle 5^{2^{k-3}}=(1+2^{2})^{2^{k-3}}=1+2^{k-1}+2^{k}I}$[1]

多项式除法

${\displaystyle (\prod p)^{k}|(x^{\lambda (\prod p)+1}-x)^{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）.