# How do I prove $n$ is a Carmichael number?

I am having some trouble with this proof and I need some help heading down the right direction:

Suppose $n = p_1p_2 \cdots p_k$ where $p_i$ are distinct primes and that $p_i - 1 \mid n - 1$. Show that $n$ is a Carmichael number, that is, that $a^{n - 1} \equiv 1 \pmod n$ for all $a$ with $\gcd(a, n) = 1$.

-
Hint: $x \equiv y \mod n$ iff $x \equiv y \mod p_i$ for all $i$. – Chris Eagle Nov 18 '11 at 13:04
I think I understand. So the solution is basically using this fact and Fermat's little theorem to show that $a^{p_i-1} \equiv 1 (mod p_i)$ for all $p_i$? – TheEnigmaMachine Nov 18 '11 at 14:53
You can find full proofs of Korselt's criterion and generalizations in the links of my post here. Note: some sci.math links need to change from "google.com/..." to "groups.google.com/..." to work nowadays. – Bill Dubuque Nov 18 '11 at 16:41

Actually much stronger is true. We have that

For $n > 2$, $n$ is Carmichael if and only if $n = \prod_{i=1}^k p_i$, where the $p_i$ are distinct primes with $k \geq 2$ and $p_i - 1 \mid n - 1$ for every $i$.

The proof is as follows

Assume $n = \prod_{i=1}^k p_i$, where the $p_i$ are distinct primes with $k \geq 2$ and $p_i - 1 \mid n - 1$ for every $i$. For $b \in \Bbb{Z}$, we have that, if $p_i \mid b$,then $b^n \equiv 0 \equiv b \pmod{p_i}$ and if $p_i \nmid b$,then $b^{n - 1} \equiv b^{(p_1 -1)\ell} \equiv 1 \pmod{p_i}$. So $b^{n} \equiv b \pmod{p_i}$. Therefore by the Chinese Remainder Theorem, $$b^n \equiv b \pmod{n}$$ and hence $n$ is Carmichael.

Conversely suppose that $n$ is Carmichael. First we will prove that $n$ is squarefree. Assume by contradiction that it is not squarefree. Then there exists some integer $v$ such that $v^2 \mid n$. Now we have that $v^n \equiv v \pmod{n}$ since $n$ is Carmichael. So this implies that $n \mid v^n - v$. Since $v^2 \mid v^n$ (since $n$ is Carmichael, it is composite and hence $n > 2$) and $v^2 \mid n$ we have that $v^2 \mid v$ which is impossible. So $n$ is squarefree. Since $n$ is squarefree, $n = p_1 \cdots p_k$ for distinct primes $p_i$.

Since $n$ is Carmichael, we have that $$b^n \equiv b \pmod{n}$$ for all integers $b$ such that $gcd(b, n) = 1$. Therefore $b^{n-1} \equiv 1 \pmod{n}$. So we have that $ord_n(b)$ divides $n - 1$. In particular we have that the universal exponent of $U_n$, which we denote $\kappa_n$, where $U_n$ is the unit group of $\Bbb{Z}/n\Bbb{Z}$, which consists of all the elements in $\Bbb{Z}/n\Bbb{Z}$ that are coprime to $n$, divides $n-1$. Since $$\kappa_n = lcm (\kappa_{p_i}) = lcm(p_i - 1)$$ we have that $p_i - 1 \mid n-1$ for all $i$. This completes our proof.

-