Carmichael 函数
| 卡迈克尔函数 | |
|---|---|
| 术语名称 | 卡迈克尔函数 |
| 英语名称 | Carmichael function |
| 别名 | Carmichael's lambda function, reduced totient function, least universal exponent function |
卡迈克尔函数是一个数论函数，把正整数映射到使 Euler 定理形式对任意底成立的最小指数。
Euler 定理表明 [math]\displaystyle{ a^{\varphi(n)} \equiv 1 \pmod n }[/math] ，但是 [math]\displaystyle{ \varphi(n) }[/math] 不总是满足这一式子的最小解，最小解即定义为 Carmichael 函数。
定义
| Carmichael 函数 | |
|---|---|
| 函数名称 | Carmichael 函数 |
| 函数符号 | [math]\displaystyle{ \lambda() }[/math] |
| Latex | \lambda
|
| 类型 | 数论函数 |
| 定义域 | [math]\displaystyle{ \mathbb{N}^* }[/math] |
| 陪域 | [math]\displaystyle{ \mathbb{N}^* }[/math] |
对整数 [math]\displaystyle{ n }[/math] ，必存在整数 [math]\displaystyle{ m }[/math] 满足 [math]\displaystyle{ (\forall a)(\operatorname{gcd}(a,n)=1 \rightarrow a^m \equiv \pmod n) }[/math] （其中的一个取值是 [math]\displaystyle{ \varphi(n) }[/math] ）。记函数将正整数 [math]\displaystyle{ n }[/math] 映射到这个 [math]\displaystyle{ n }[/math] 下 [math]\displaystyle{ m }[/math] 的最小正整数取值，称这个函数为 卡迈克尔函数(Carmichael function) [math]\displaystyle{ \lambda(n) }[/math] ，记作 [math]\displaystyle{ \lambda(n) }[/math] 。
性质
- [math]\displaystyle{ \lambda(n) \mid \varphi(n) }[/math]
- [math]\displaystyle{ a\mid b \Rightarrow \lambda(a)\mid \lambda(b) }[/math]
- [math]\displaystyle{ \lambda(\operatorname{lcm}(a,b)) = \operatorname{lcm}(\lambda(a),\lambda(b)) }[/math]
- 不是乘性函数，而是在最小公倍数意义上才相当于相乘。
- 考虑与欧拉函数的关系，有：
- 当且仅当 [math]\displaystyle{ n }[/math] 有原根，或者说取 1、2、4、奇质数幂、二倍奇质数幂时， [math]\displaystyle{ \lambda(n) = \varphi(n) }[/math]
- 对 2 的幂，即 [math]\displaystyle{ n=2^k, k\geq 3 }[/math] 时， [math]\displaystyle{ \lambda(n) = \tfrac{1}{2}\varphi(n) = 2^{k-2} }[/math]
- 对一般的 [math]\displaystyle{ n=p_1^{n_1} p_2^{n_2} \dots p_m^{n_m} }[/math] 有 [math]\displaystyle{ \lambda(n) = \operatorname{lcm}(\lambda(p_1^{n_1}), \lambda(p_2^{n_2}), \dots, \lambda(p_m^{n_m})) }[/math]