Exercise 2.8.26* (Characterization of Carmichael numbers)

Proof. Here $m>1$ is a composite number.

If $m$ is a Carmichael number, the number $N$ of solutions of the congruence $a^{m-1}\equiv 1(\mathit{mod}m)$ is $\varphi (m)$. By Problem 25, $N=\underset{p\mid m}{\prod <!--\; FUNCTION\; APPLICATION\; -->}(p-1)\wedge (m-1)$, so

where for each prime factor $p$ of $m$, $p^{\alpha }\mid m$, $p^{\alpha +1}\nmid m$.

Note that

If one of these inequality is a strict inequality, then $\varphi (m)>{\prod <!--\; FUNCTION\; APPLICATION\; -->}_{p\mid m}[(p-1)\wedge (m-1)]$, in contradiction with (1). Therefore, all these inequalities are equalities: for all prime $p$ such that $p\mid m$,

This shows that $p^{\alpha -1}=1$, thus $\alpha =1$. Therefore $m$ is square-free. Moreover, $(p-1)\wedge (m-1)=p-1$, thus $p-1\mid m-1$ for all primes $p$ dividing $m$.

Conversely, suppose that $m=p_1\cdots p_l$ is square-free, and that $p-1\mid m-1$ for all primes $p$ dividing $m$. For all integers $a$ such that $a\wedge m=1$, a fortiori $a\wedge p_k=1$, then $a^{p_k-1}\equiv 1(\mathit{mod}{p}_k)$ by Fermat’s Theorem, and $p_k-1\mid m-1$, thus

Since the $p_k$ are distinct, $a^{m-1}\equiv 1(\mathit{mod}{p}_1\cdots p_l)$, so

for every $a$ such that $a\wedge m=1$, so that $m$ is a Carmichael number.

For instance,

$13\cdot 31\equiv 1(\mathit{mod}6),7\cdot 31=217=18\cdot 12+1\equiv 1(mod12),7\cdot 13=91\equiv 1(mod30)$, and $2821=7\cdot 13\cdot 31$, thus

Therefore $2821=7\cdot 13\cdot 31$ is a Carmichael number. □