查看“︁卡邁克爾函數”︁的源代码

'''[[羅伯特·丹尼·卡邁克爾|卡邁克爾]]函数'''<math>\lambda(n)</math>{{OEIS|id=A002322}}满足<math>a^{\lambda(n)}\equiv 1\pmod{n}</math>，其中a与n[[互质]]。

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

欧拉函数有<math>\varphi(p^k) = p^{k-1}(p-1)</math>

由[[算术基本定理]]，正整数n可写为质数的积<math>n= p_1^{a_1}p_2^{a_2} \dots p_{\omega(n)}^{a_{\omega(n)}}</math>

对于所有n，<math>\lambda(n)</math>是它们[[最小公倍數]]：

<math>\lambda(n) = \operatorname{lcm}[\lambda(p_1^{a_1}),\;\lambda(p_2^{a_2}),\dots,\lambda(p_{\omega(n)}^{a_{\omega(n)}}) ]</math>

==例子==
<math>\lambda(8)=2</math>

<math>7^2\equiv 1\pmod{8}</math>

==证明==
证明当a与n[[互质]]时，满足<math>a^{\lambda(n)}\equiv 1\pmod{n}</math>

由[[费马小定理]]得<math>a^{p-1}=1+hp</math>

<math>a^{p^{k-1}(p-1)}=1+hp^k</math>

<math>a^{p^k(p-1)}=(1+hp^k)^p=1+h^p p^{k+1}+\dots=1+h_0 p^{k+1}</math>

由[[数学归纳法]]得<math>a^{p^{k-1}(p-1)}\equiv 1\pmod{p^k}</math>成立，这是一般情况。

<math>a=1+2h</math>

<math>a^2=1+4h(h+1)=1+8C_{h+1}^2</math>

<math>a^{2^{k-2}}=1+2^k h</math>

<math>a^{2^{k-1}}=(1+2^k h)^2=1+2^{k+1}(h+2^{k-1}h^2)</math>

由[[数学归纳法]]得当<math>k\ge 3</math>时，<math>a^{2^{k-2}}\equiv 1\pmod{2^k}</math>成立。
<ref name="car">{{cite book|author=Robert Daniel Carmichael|title=The Theory of Numbers|location=Nabu Press|isbn=1144400341|url=http://www.gutenberg.org/ebooks/13693|access-date=2015-07-29|archive-date=2020-12-02|archive-url=https://web.archive.org/web/20201202114603/http://www.gutenberg.org/ebooks/13693|dead-url=no}}</ref>

==原根的充要条件==
证明<math>\varphi(n)=\lambda(n)</math>为存在模n[[原根]]的充要条件。

而<math>\varphi(n)=\lambda(n)</math>当且仅当<math>n=1,2,4,p^k,2p^k</math>（<math>p\neq 2</math>）
===必要性===
<math>\varphi(n)\ge\lambda(n)</math>，若<math>\varphi(n)>\lambda(n)</math>，则不存在阶为<math>\varphi(n)</math>的模n元素，即不存在原根。<ref name="car"/>

==λ原根==
阶为<math>\lambda(n)</math>的模n元素为λ原根。模n的λ原根的个数参见{{oeis|A111725}}。

当<math>n=2^k,k>2</math>时，3、5为模n的λ原根，因而所有模8余3或5的数都是模n的λ原根。
:<math>3^{2^{k-3}}=(2^2-1)^{2^{k-3}}=1-2^{k-1}+2^k I</math><ref name="car"/>
:<math>5^{2^{k-3}}=(1+2^2)^{2^{k-3}}=1+2^{k-1}+2^k I</math><ref name="car"/>

==多项式除法==
<math>(\prod p)^k|(x^{\lambda(\prod p)+1}-x)^k</math>

余式：<math>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}</math> <ref>{{cite journal|author=黄嘉威|year=2015|title=多项式除法解高次同余|journal=数学学习与研究|issue=9|pages=第104页|url=http://www.cnki.com.cn/Article/CJFDTOTAL-SXYG201509084.htm|access-date=2017-09-24|archive-date=2020-10-20|archive-url=https://web.archive.org/web/20201020225326/http://www.cnki.com.cn/Article/CJFDTOTAL-SXYG201509084.htm|dead-url=no}}</ref>

==参见==
*[[卡邁克爾數]]

==参考资料==
{{reflist}}

[[分类:同余]]
[[分类:函数]]