Criteria for $p$ being a prime number.

Question

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.

Answer 1

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.

Answer 2

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