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.

  • 1
    $\begingroup$ Hint: $x \equiv y \mod n$ iff $x \equiv y \mod p_i$ for all $i$. $\endgroup$ – Chris Eagle Nov 18 '11 at 13:04
  • 1
    $\begingroup$ 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$? $\endgroup$ – TheEnigmaMachine Nov 18 '11 at 14:53
  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.