卡迈克尔函数

卡迈克尔函数${\displaystyle \mathrm{\lambda <!--\; \lambda \; -->}(n)}$（OEIS数列A002322）满足${\displaystyle a^{\mathrm{\lambda <!--\; \lambda \; -->}(n)}\equiv <!--\; \equiv \; -->1(\mathrm{mod}n)}$，其中a与n互质。

当n为1、2、4、奇质数的次幂、奇质数的次幂的两倍时为欧拉函数，当n为2,4以外的2的次幂时为它的一半。

欧拉函数有${\displaystyle \mathrm{\phi <!--\; \phi \; -->}(p^k)=p^{k-<!--\; -\; -->1}(p-<!--\; -\; -->1)}$

由算术基本定理，正整数n可写为质数的积${\displaystyle n=p_1^{a_1}{p}_2^{a_2}\dots <!--\; \dots \; -->p_{\mathrm{\omega <!--\; \omega \; -->}(n)}^{a_{\mathrm{\omega <!--\; \omega \; -->}(n)}}}$

对于所有n，${\displaystyle \mathrm{\lambda <!--\; \lambda \; -->}(n)}$是它们最小公倍数：

${\displaystyle \mathrm{\lambda <!--\; \lambda \; -->}(n)=\mathrm{lcm}<!--\; \; -->}$

${\displaystyle \mathrm{\lambda <!--\; \lambda \; -->}(8)=2}$

${\displaystyle 7^2\equiv <!--\; \equiv \; -->1(\mathrm{mod}8)}$

证明当a与n互质时，满足${\displaystyle a^{\mathrm{\lambda <!--\; \lambda \; -->}(n)}\equiv <!--\; \equiv \; -->1(\mathrm{mod}n)}$

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

${\displaystyle a^{p^{k-<!--\; -\; -->1}(p-<!--\; -\; -->1)}=1+h{p}^k}$

${\displaystyle a^{p^k(p-<!--\; -\; -->1)}=(1+h{p}^k{)}^p=1+h^p{p}^{k+1}+\cdots <!--\; \cdots \; -->=1+h_0{p}^{k+1}}$

由数学归纳法得${\displaystyle a^{p^{k-<!--\; -\; -->1}(p-<!--\; -\; -->1)}\equiv <!--\; \equiv \; -->1(\mathrm{mod}{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\ge <!--\; \ge \; -->3}$时，${\displaystyle a^{2^{k-<!--\; -\; -->2}}\equiv <!--\; \equiv \; -->1(\mathrm{mod}{2}^k)}$成立。

证明${\displaystyle \mathrm{\phi <!--\; \phi \; -->}(n)=\mathrm{\lambda <!--\; \lambda \; -->}(n)}$为存在模n原根的充要条件。

而${\displaystyle \mathrm{\phi <!--\; \phi \; -->}(n)=\mathrm{\lambda <!--\; \lambda \; -->}(n)}$当且仅当${\displaystyle n=1,2,4,p^k,2p^k}$（${\displaystyle p\ne <!--\; \ne \; -->2}$）

${\displaystyle \mathrm{\phi <!--\; \phi \; -->}(n)\ge <!--\; \ge \; -->\mathrm{\lambda <!--\; \lambda \; -->}(n)}$，若${\displaystyle \mathrm{\phi <!--\; \phi \; -->}(n)>\mathrm{\lambda <!--\; \lambda \; -->}(n)}$，则不存在阶为${\displaystyle \mathrm{\phi <!--\; \phi \; -->}(n)}$的模n元素，即不存在原根。

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

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

${\displaystyle (\prod <!--\; \prod \; -->p{)}^k|(x^{\mathrm{\lambda <!--\; \lambda \; -->}(\prod <!--\; \prod \; -->p)+1}-<!--\; -\; -->x{)}^k}$

余式：${\displaystyle x^{\mathrm{\lambda <!--\; \lambda \; -->}(\prod <!--\; \prod \; -->p)(k+n)+k}\equiv <!--\; \equiv \; -->\underset{i=1}{\overset{k}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^{i-<!--\; -\; -->1}(\genfrac{}{}{0ex}{}{n+i-<!--\; -\; -->1}{i-<!--\; -\; -->1})(\genfrac{}{}{0ex}{}{n+k}{k-<!--\; -\; -->i})x^{\mathrm{\lambda <!--\; \lambda \; -->}(\prod <!--\; \prod \; -->p)(k-<!--\; -\; -->i)+k}(\mathrm{mod}(\prod <!--\; \prod \; -->p{)}^k)}$