Criteria for $p$ being a prime number.

I'm trying to prove the following problem:

$p$ is a prime iff for all $n\in \mathbb{Z}$ with $n\not \equiv 0\mod p$, we have $n^{p-1}\equiv 1 \mod p$.

The ($\Rightarrow$) direction is easy: we have that if $p$ is a prime, then $n\not \equiv 0\mod p$ is equivalent to $(n,p)=1$, and then we use the Fermat's little theorem.

I'm having trouble with the second direction: I've read that the Fermat's little theorem have a converse (Lehmer's theorem) that changes slightly the hypothesis but I don't if it's useful for my problem and how can I use it.

• I'm assuming that where you wrote $n$ you wanted to write $n$ – PenasRaul Oct 3 '14 at 17:31
• Apart from the uninteresting counterexample $n=1$, the other direction is even easier. The interesting question comes when we restrict to $a$ relatively prime to the modulus. For such matters, which are not needed to answer your question, please look at Wikipedia, Carmichael Numbers. – André Nicolas Oct 3 '14 at 17:33
• @PenasRaul: I'm assuming that where you wrote "I'm assuming that where you wrote $n$ you wanted to write $n$" you wanted to write "I'm assuming that where you wrote $a$ you wanted to write $n$". – TonyK Oct 3 '14 at 17:46
• The question is fixed. Thanks @PenasRaul for the answer. Yes, the problem has a second part that ask about if we can change the hypothesis and use $(n,p)=1$ instead of modulus, so I used the Carmichael Numbers there. – jiyanez Oct 3 '14 at 17:47
• You assumed correctly, my apologies – PenasRaul Oct 3 '14 at 18:19

The other implication, you assume $p$ is not prime, you just have to take a non trivial divisor of $p$, $n$ and then for sake of contradiction assume $n^{p-1}\equiv_p 1$, then $n \mid p \mid n^{p-1} - 1$, so $n \mid 1$ contradiction to $n$ be non trivial divisor.
Remark: $p$ is prime iff $(p,k)=1$ for all $k$ s.t $1<k<p$.
Let $k$ s.t $1<k<p$, then by hypothesis we have $k^{p-1}\equiv 1$ mod $p$, hence there exists $m\in \Bbb Z$ s.t $k^{p-1}=1+mp$, so $k.k^{p-2}+(-m)p=1$, by Bezout theorem we get $(k,p)=1$.