= Solution
<Fermat's little theorem> states that, for a <prime number> $p$ and any integer $a$,
$$
a^p\equiv a\pmod p.
$$
If $p\mid a$, both sides vanish modulo $p$. Otherwise multiplication by $a$ permutes the nonzero residue classes modulo $p$: it is injective because $ai\equiv aj$ implies $i\equiv j$ by cancellation. Taking the products of these residues gives
$$
a^{p-1}(p-1)!\equiv(p-1)!\pmod p.
$$
The <factorial> is <coprime> to $p$, so cancellation proves $a^{p-1}\equiv1\pmod p$ and hence the stated version. This proves <Fermat's little theorem> in both cases.
Let $n$ be a <Carmichael number>. If a <prime> square $p^2$ divided $n$, choose $a=p$. Since $n$ is an odd composite integer, $n>1$, and $p^n-p\equiv-p\not\equiv0\pmod{p^2}$. This contradicts the required <modular congruence> modulo $n$. Therefore \b[every Carmichael number is squarefree].
For each <prime> divisor $p$ of $n$, choose the allowed <primitive root> $g$ modulo $p$. The Carmichael identity applied to the positive integer $g$ gives $g^n\equiv g\pmod p$, and cancellation gives $g^{n-1}\equiv1\pmod p$. By its defining order property,
$$
p-1\mid n-1.
$$
Conversely, suppose a composite integer $n$ is squarefree and has this divisibility for every <prime> divisor. For an arbitrary integer $a$, modulo a <prime> divisor $p$ there are two cases. If $p\mid a$, then $a^n\equiv a\equiv0$. Otherwise <Fermat's little theorem> and $p-1\mid n-1$ give $a^{n-1}\equiv1$, so again $a^n\equiv a$. Since the <prime> divisors are distinct and pairwise <coprime>, their product $n$ divides $a^n-a$. This is the <proof of Korselt criterion>:
$$
\boxed{n\text{ is Carmichael}\ \Longleftrightarrow\
n\text{ is composite and squarefree, and }p-1\mid n-1\text{ for all }p\mid n.}
$$
If $n=pq$ for distinct odd <primes> with $p<q$, the condition at $q$ would require $q-1\mid pq-1$. Reducing $p q-1$ modulo $q-1$ gives $p-1$, so $q-1\mid p-1$. But $0<p-1<q-1$, which is impossible. Thus \b[a product of two distinct odd <primes> is not Carmichael].
For $n=pqr$, squarefreeness is automatic. Since $p\equiv1\pmod{p-1}$,
$$
pqr-1\equiv qr-1\pmod{p-1}.
$$
Apply the analogous reductions at $q$ and $r$ to obtain
$$
\boxed{pqr\text{ is Carmichael}\ \Longleftrightarrow\
p-1\mid qr-1,\quad q-1\mid pr-1,\quad r-1\mid pq-1.}
$$
Finally $1729=7\cdot13\cdot19$, with distinct odd <prime factors>, and
$$
13\cdot19-1=246=6\cdot41,\qquad
7\cdot19-1=132=12\cdot11,\qquad
7\cdot13-1=90=18\cdot5.
$$
All three divisibilities hold, so \b[1729 is a Carmichael number].
Back to article page
