Carmichael function

2020 Mathematics Subject Classification: Primary: 11A25 [MSN][ZBL]

of a positive integer $n$

The exponent of the multiplicative group of integers modulo $n$, denoted $\lambda(n)$; the least positive integer $\lambda$ such that $a^\lambda \equiv 1 \pmod n$ for all integers $a$ coprime to $n$. It is equal to the least common multiple of its values on the prime power factors of $n$: $$ \lambda(n) = \mathrm{lcm}\{\lambda(p_i^{a_i})\}\ \ \text{where}\ n = \prod_i p_i^{a_i} \ . $$

Since the multiplicative group modulo an odd prime power $p^a$ is cyclic, in these cases we have $\lambda(p^a) = \phi(p^a) = p^{a-1}(p-1)$ where $\phi$ denotes the Euler totient function. For powers of 2, we have $\lambda(2) = 1$, $\lambda(4)= 2$ and $\lambda(2^a) = 2^{a-2}$ for $a \ge 3$.

The order of the multiplicative group modulo $n$ is $\phi(n)$, so by Lagrange's theorem in group theory, $\lambda(n)$ divides $\phi(n)$.

A Carmichael number is a composite number with the property that $\lambda(n)$ divides $n-1$.

References

• Eric Bach, Jeffrey O. Shallit, Algorithmic Number Theory: Efficient algorithms, Volume 1, MIT Press (1996) ISBN 0262024055