Fermat Pseudoprimes and Carmichael Numbers

Introduction to Carmichael Numbers

When you first encountered Fermat's little theorem, you must have pondered if the reverse is true. That is, if $a^n\equiv a\pmod n$ for all integers $a$, then $n$ is prime or not. If you see some examples by hand, you may convince yourself that $n$ must be a prime in order to hold the condition true. Unfortunately, that is not the case. There are infinitely such $n$, which we will call Carmichael number. Here, by $a\bot n$, we mean $\gcd(a,b)=1$.

If $n$ is a composite integer so that $a^n\equiv a\pmod n$, then $n$ is a pseudoprime base $a$. If $a^n\equiv a\pmod n$ for all integer $a$ i.e. $n$ is a pseudoprime base $a$ for all integer $a$, then $n$ is a Carmichael number. For $a\bot n$ one has \begin{align*} a^{n-1} & \equiv1\pmod n \end{align*} The following criterion gives us a way to determine if a number is Carmichael or not.

Korselt's Criterion A composite integer $n$ is a Carmichael number if and only if $n$ is squarefree and for any prime $p|n$, we have $p-1|n-1$.

Let's prove this now. We will consider $n>1$.

For the sake of contradiction, assume $p^2$ divides $n$ if $p|n$. Then for all $a$, $p^2|a^n-a$ too. Choose $a=p$ and we have $p^2|p^n-p$ or $p^2|p$, which is impossible. So, $n$ is squarefree.

For the second part, we can assume without loss of generality that $p\nmid a$. Note that, from Fermat's Little Theorem, $$a^{p-1}\equiv1\pmod p$$ We also have $a^{n-1}\equiv1\pmod p$. Since this has to be true for all $a\bot p$, we are free to choose $a$ as long as $a\bot p$. Let's choose a primitive root $g$ of $p$ i.e. . Then \begin{align*} g^{p-1} & \equiv1\pmod p\newline g^{n-1} & \equiv1\pmod p \end{align*} Since , we must have $p-1|n-1$.

Thus, the criterion is proved.

Caution: though we stated that there are infinitely many Carmichael numbers, it is not trivial. In fact, it took a long time for mathematicians to prove this fact. Alford, Granville and Pomerance proved it first in $1994$ (Annals of Mathematics, $140(1994)$, $703-722$).

Prove that $561$ is a Carmichael number. Is there a smaller such number?

Prove that $341$ is a pseudoprime base $2$.