Exercise 2.8.27* ($m$ is a Carmichael number iff $a^m \equiv a \pmod m$ for all $a$)

Proof. Let $m>1$ be a composite number.

$\text{∙}$ Suppose that $a^m\equiv a(\mathit{mod}m)$ for all integers $a$.

If $a\wedge m=1$, then $m\mid a(a^{m-1}-1)$, therefore $m\mid a^{m-1}-1$, so $a^{m-1}\equiv 1(\mathit{mod}m)$. This shows that $m$ is a Carmichael number.

$\text{∙}$ Conversely suppose that $m$ is a Carmichael number. Then

By Problem 26, $m$ is square-free, so that

where $p_1,p_2,\dots ,p_l$ are distinct primes such that $p_i-1\mid m-1$ for all indices $i$.

We can write $a$ under the form

Since $\lambda \wedge m=1$, (1) shows that ${\lambda }^{m-1}\equiv 1(\mathit{mod}m)$, thus, multiplying by $\lambda$,

Moreover, using Fermat’s Theorem, since $p_1^{a_1}\wedge p_i=1$ for $i=2,3,\dots ,l$,

Since $p_i-1\mid m-1$ for all $i$,

Multiplying by $p_1^{a_1}$,

Moreover, ${(p_1^{a_1})}^m\equiv p_1^{a_1}\equiv 0(\mathit{mod}{p}_1)$, thus

Since $p_1,p_2,\dots ,p_l$ are distinct, and $m=p_1{p}_2\cdots p_l$,

and similarly, for all $k\in [[1,l]]$,

Then, using (2) and (3),

So, for all integers $a$,

This proves that a composite $m$ is a Carmichael number if and only if $a^m\equiv a(\mathit{mod}m)$ for all integers $a$. □

Proof. Here $n>1$.

$(i)\Rightarrow (\mathit{ii}).$ Let $p$ be a prime factor of $n$, and let $a$ be any integer.

• If $p\nmid a$, by Fermat’s Theorem, $a^{p-1}\equiv 1(\mathit{mod}p)$. Since $p-1\mid n-1$, $a^{n-1}\equiv 1(\mathit{mod}p)$. Multiplying by $a$, we obtain $a^n\equiv a(\mathit{mod}p)$.
• If $p\mid a$, $a^n\equiv 0\equiv a(\mathit{mod}p)$.

This shows that for every prime factor $p$ of $n$,

Since $n$ is square-free, $n=p_1{p}_2\cdots p_l$, where $p_1,p_2,\dots ,p_l$ are distinct prime. Therefore $a^n\equiv a(\mathit{mod}{p}_1{p}_2\cdots p_n)$, so

$(\mathit{ii})\Rightarrow (\mathit{iii})$. If $a\wedge n=1$, then $n\mid a(a^{n-1}-1)$, therefore $n\mid a^{n-1}-1$, so $a^{n-1}\equiv 1(\mathit{mod}n)$.

$(\mathit{iii})\Rightarrow (i)$. Suppose now that $a^{n-1}\equiv 1(\mathit{mod}n)$ for every integer $a$ prime to $n$.

Assume for contradiction that $n$ is not square-free, so that $n=p^{2}m$ for some prime $p$ and some integer $m$. Take $a=1+\mathit{pm}$. By the binomial formula,

so $a^p\equiv 1(\mathit{mod}n)$. Moreover $a\not\equiv 1(\mathit{mod}n)$, otherwise $p^{2}m\mid \mathit{pm}$, and $p\mid 1$. Therefore the order of $a$ modulo $n$ is $p$.

But by(iii), $a^{n-1}\equiv 1(\mathit{mod}n)$. Therefore $p\mid n-1=p^{2}m-1$, thus $p\mid 1$. This is a contradiction, which proves that $n$ is square-free.

We can write $n=p_1{p}_2\cdots p_l$, where $p_1,p_2,\dots ,p_l$ are distinct primes. Let $a_i$ be a primitive root modulo $p_i$ for each index $i$. By the Chinese Remainder Theorem, there is some integer $a$ such that $a\equiv a_i(\mathit{mod}{p}_i)$ for all $i$. By (iii), $a^{n-1}\equiv 1(\mathit{mod}n)$. A fortiori, $a^{n-1}\equiv 1(\mathit{mod}{p}_i)$. Therefore $a_i^{n-1}\equiv 1(\mathit{mod}{p}_i)$. Since the order of $a_i$ is $p_i-1$, this implies $p_i-1\mid n-1$ for all $i$. □