# Carmichael function

2010 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

**How to Cite This Entry:**

Carmichael function.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Carmichael_function&oldid=35703