查看“︁Carmichael 函数”︁的源代码

[[分类:数论函数]]
[[分类:以 Carmichael 命名]]
{{InfoBox
|name=卡迈克尔函数
|eng_name=Carmichael function
|aliases=Carmichael's lambda function,reduced totient function,least universal exponent function
}}
'''<ins>卡迈克尔</ins>函数'''是一个[[数论函数]]，把正整数映射到使 [[Euler 定理（同余理论）|Euler 定理]]形式对任意底成立的最小指数。

Euler 定理表明 <math>a^{\varphi(n)} \equiv 1 \pmod n</math> ，但是 <math>\varphi(n)</math> 不总是满足这一式子的最小解，最小解即定义为 Carmichael 函数。

== 定义 ==

{{Function
|name=Carmichael 函数
|symbol=<math>\lambda()</math>
|latex=\lambda
|prototype=数论函数
|domain=<math>\mathbb{N}^*</math>
|codomain=<math>\mathbb{N}^*</math>
}}
对整数 <math>n</math> ，必存在整数 <math>m</math> 满足 <math>(\forall a)(\operatorname{gcd}(a,n)=1 \rightarrow a^m \equiv \pmod n)</math> （其中的一个取值是 <math>\varphi(n)</math> ）。记函数将正整数 <math>n</math> 映射到这个 <math>n</math> 下 <math>m</math> 的最小正整数取值，称这个函数为 '''<ins>卡迈克尔</ins>函数'''('''Carmichael function''') <math>\lambda(n)</math> ，记作 <math>\lambda(n)</math> 。

== 性质 ==

* <math>\lambda(n) \mid \varphi(n)</math>
* <math>a\mid b \Rightarrow \lambda(a)\mid \lambda(b)</math>
* <math>\lambda(\operatorname{lcm}(a,b)) = \operatorname{lcm}(\lambda(a),\lambda(b))</math>
** 不是[[乘性函数]]，而是在最小公倍数意义上才相当于相乘。
* 考虑与欧拉函数的关系，有：
** 当且仅当 <math>n</math> 有[[原根]]，或者说取 1、2、4、奇质数幂、二倍奇质数幂时， <math>\lambda(n) = \varphi(n)</math>
** 对 2 的幂，即 <math>n=2^k, k\geq 3</math> 时， <math>\lambda(n) = \tfrac{1}{2}\varphi(n) = 2^{k-2}</math>
** 对一般的 <math>n=p_1^{n_1} p_2^{n_2} \dots p_m^{n_m}</math> 有 <math>\lambda(n) = \operatorname{lcm}(\lambda(p_1^{n_1}), \lambda(p_2^{n_2}), \dots, \lambda(p_m^{n_m}))</math>


{{数论函数}}

== 琐事 ==

=== 数列编号 ===

{{OEIS|A002322}}