卡邁克爾函數

卡邁克爾函数$\lambda (n)$Template:OEIS满足$a^{\lambda (n)}\equiv 1(\mathrm{mod}n)$，其中a与n互质。

定义

当n为1、2、4、奇质数的次幂、奇质数的次幂的两倍时为欧拉函数，当n为2,4以外的2的次幂时为它的一半。 $\lambda (n)=\{\begin{array}{cc}\phi (n)& n=1,2,3,4,5,6,7,9,10,11,13,14,17,19,22,23,25,26,27,29\dots \\ \frac{1}{2}\phi (n)& n=8,16,32,64,128,256\dots \end{array}$

欧拉函数有$\phi (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)=\mathrm{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(\mathrm{mod}8)$

证明

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

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

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

$a^{p^k(p-1)}=(1+h{p}^k{)}^p=1+h^p{p}^{k+1}+\dots =1+h_0{p}^{k+1}$

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

原根的充要条件

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

而$\phi (n)=\lambda (n)$当且仅当$n=1,2,4,p^k,2p^k$（$p\ne 2$）

必要性

$\phi (n)\ge \lambda (n)$，若$\phi (n)>\lambda (n)$，则不存在阶为$\phi (n)$的模n元素，即不存在原根。

λ原根

阶为$\lambda (n)$的模n元素为λ原根。模n的λ原根的个数参见Template:Oeis。

当$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}(\genfrac{}{}{0ex}{}{n+i-1}{i-1})(\genfrac{}{}{0ex}{}{n+k}{k-i})x^{\lambda (\prod p)(k-i)+k}(\mathrm{mod}(\prod p{)}^k)$

参见

• 卡邁克爾數