卡迈克尔函数

1. 定义

卡迈克尔函数定义为：当 $n$ 为 1、2、4、奇质数的次幂、奇质数的次幂的两倍时为欧拉函数，当 $n$ 为 2、4 以外的 2 的次幂时为欧拉函数的一半。

$$\begin{array}{c} \lambda(n) = \left\{ \begin{aligned} \phi(n) \,\, & \,\, n = 1,2,3,4,5,6,7,9,10,\cdots \\ {1 \over 2}\phi(n) \,\, & \,\, n = 8,16,32,64,128,256,\cdots \end{aligned} \right. \end{array}$$

2. 性质

• 对于任意整数 $n$，由算数基本定理（整数唯一分解定理）：$n = p_1^{a_1}p_2^{a_2} \cdots p_w^{a_w}$，则卡迈克尔函数满足：

$$\begin{array}{c} \lambda(n) = lcm[\lambda(p_1^{a_1}),\lambda(p_2^{a_2}),\cdots,\lambda(p_w^{a_w})] \end{array}$$

证明：根据欧拉函数性质，有 $\phi(p^k) = p^{k-1}(p-1)$（$p$ 为质数）