Carmichael function

There are two different functions that are both called Carmichael function. It is similar to the totient function

The first definition

The first definition is also called the reduced totient function or the least universal exponent function. It is defined as the smallest positive integer $\lambda(n)$ such that $a^{\lambda(n)} \equiv 1\pmod {n}$ for all positive integers $a$ relatively prime to $n$ . The modulo order of $a\pmod {n}$ is less than or equal to $\lambda(n)$ .

Suppose $n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ . We have

$\lambda(n) = \begin{cases} \phi(n) & \mathrm {for}\ n=p^{\alpha},\ \mathrm {with}\ p=2\ \mathrm {and}\ \alpha\le 2,\ \mathrm {or}\ p\ge 3\\ \frac{1}{2}\phi(n) & \mathrm {for}\ n=2^{\alpha}\ \mathrm {and}\ \alpha\ge 3\\ \mathrm{lcm} (\lambda(p_1^{\alpha_1}), \lambda(p_2^{\alpha_2}), \ldots, \lambda(p_k^{\alpha_k})) & \mathrm{for}\ \mathrm{all}\ n. \end{cases}$

Examples

The second definition

The second definition of the Carmichael function is the least common multiples of all the factors of $\phi(n)$ . It is written as $\lambda'(n)$ . However, in the case $8|n$ , we take $2^{\alpha-2}$ as a factor instead of $2^{\alpha-1}$ .

Page

Toolbox

Search

Carmichael function

Contents

The first definition

Examples

The second definition

Examples

See also