= Carmichael function
{c}
{title2=$\lambda(n)$}
{wiki}
= Carmichael period
{c}
{synonym}
= Carmichael's function
{c}
{synonym}
For an <integer> $n>1$, the <Carmichael function> $\lambda(n)$ is the <exponent of a finite group> for the <unit group> $U(n)=(\mathbb Z/n\mathbb Z)^\times$: the least <positive integer> $m$ for which
$$
a^m\equiv1\pmod n\qquad\text{for every }a\text{ with }\gcd(a,n)=1.
$$
Here the <greatest common divisor> condition selects the <units>. <Euler's totient function> $\varphi(n)$ counts them; the <Carmichael function> gives their least common return exponent.<Notes on primitive lambda-roots by Peter J. Cameron and others>[pp. 7–8, definition]{ref}
Modulo eight, the <units> are $1,3,5,7$, and their squares are all congruent to one. Their <multiplicative orders> are $1,2,2,2$, so $\lambda(8)=2$ although $\varphi(8)=4$. Modulo fifteen, the <units> $1,2,4,7,8,11,13,14$ have <multiplicative orders> $1,4,2,4,4,2,4,2$. For example, the powers of two return through $1,2,4,8,1$. Thus $\lambda(15)=4$ although $\varphi(15)=8$; the <multiplicative order> of four is only two.
\Image[/carmichael-unit-orders-common-exponent.png]
{title=Individual unit orders divide the least common return exponent modulo eight and fifteen}
The three quantities are related by
$$
\lambda(n)=\mathop{\operatorname{lcm}}_{\substack{1\leq a<n\\\gcd(a,n)=1}}\operatorname{ord}_n(a),\qquad
\operatorname{ord}_n(a)\mid\lambda(n)\mid\varphi(n).
$$
A common return exponent must be a multiple of every <multiplicative order>, hence of their <least common multiple>. Conversely, that <least common multiple> makes every <unit> return to one. <Lagrange's theorem> makes each <multiplicative order> divide the <group order> $\varphi(n)$, proving the final <divisibility>. The <Carmichael function> applies to all <units> at once, while the <multiplicative order> concerns a chosen <unit>.
For the <prime factorization> $n=\prod_{i=1}^r p_i^{e_i}$ with distinct <prime numbers> $p_i$ and $e_i\geq1$, the formulas are
$$
\lambda(n)=\operatorname{lcm}\bigl(\lambda(p_1^{e_1}),\ldots,\lambda(p_r^{e_r})\bigr),\qquad
\lambda(p^e)=p^{e-1}(p-1)\quad(p\text{ an odd prime}),
$$
$$
\lambda(2^e)=
\begin{cases}
1,&e=1,\\
2,&e=2,\\
2^{e-2},&e\geq3.
\end{cases}
$$
These are <least common multiples>, rather than products: $\lambda(15)=\operatorname{lcm}(2,4)=4$. The convention $\lambda(1)=1$ handles the trivial case separately.<Notes on primitive lambda-roots by Peter J. Cameron and others>[p. 8, Proposition 5.1(a–c)]{ref}
The <Chinese remainder theorem for unit groups> explains the <least common multiple>: a power returns to one in every <prime power> component exactly when it is a multiple of each component's <exponent of a finite group>. For an odd <prime power>, the <unit group> is a <cyclic group> of <group order> $p^{e-1}(p-1)$. For $e\geq3$, the <unit group> modulo $2^e$ is a <direct product of groups> $C_2\times C_{2^{e-2}}$, generated by the classes of $-1$ and five, so its <exponent of a finite group> is $2^{e-2}$.<A Computational Introduction to Number Theory and Algebra by Victor Shoup>[Section 7.5, pp. 203–205, Theorem 7.28 and its proof]{ref}
This gives a uniform reduction for <modular exponentiation>: for a <unit> $a$ and a nonnegative <integer> $k$, reduce $k$ modulo $\lambda(n)$. For example, $2^{1001}\equiv2\pmod{15}$ because $1001\equiv1\pmod4$. The <unit> hypothesis matters: $3^2\equiv1\pmod8$, but $2^2\not\equiv1\pmod8$. Computing the formula assumes the <prime factorization> is available. The same common-exponent viewpoint explains <Carmichael numbers>: a <composite number> $n$ passes the <Fermat primality test> for every <unit> base exactly when $\lambda(n)\mid n-1$. For example, $\lambda(561)=\operatorname{lcm}(2,10,16)=80\mid560$.
Back to article page
