3
$\begingroup$

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$.

Thank you for your help.

  • 0
    You can find full proofs of Korselt's criterion and generalizations in the links of my [post here.](http://math.stackexchange.com/questions/1626/modular-exponentiation-using-eulers-theorem/1726#1726) Note: some sci.math links need to change from "google.com/..." to "groups.google.com/..." to work nowadays.2011-11-18

1 Answers 1

3

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.