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.

  • 1
    Hint: $x \equiv y \mod n$ iff $x \equiv y \mod p_i$ for all $i$.2011-11-18
  • 1
    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$?2011-11-18
  • 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