Backwards proof of Fermat's Little Theorem

Question

$$\textrm{Let }p \in \mathbb{N}. \textrm{ Show that }\forall n \in \left \{ 1,2,...,p-1 \right \} \textrm{if } n^{p-1} \equiv 1 \mod p \Rightarrow p \in \mathbb{P}$$

This is basically Fermat's Little Theorem, I know the proof of that, but here it seems it is backwards. Every FLT proof starts with that $p \in \mathbb{P}$ but here I have to proof that $p \in \mathbb{P}$ at the end.

As a hint it says:

Do Reductio ad absurdum (contradiction), show that $n^{p-1} \equiv 1 \mod p$ cannot be true for divisors of $p$.

What I did so far:
Assumption: $p \notin \mathbb{P}$
$p = kp' \Rightarrow p'\mid p$
Plug that into the formula:
$p \mid n^{kp'-1}-1\Rightarrow kp' \mid n^{kp'-1}-1\Rightarrow p' \mid n^{kp'-1}-1\Rightarrow p' \mid n^{p-1}-1$

But I can see no contradiction there and also don't know how to continue.

Can anyone help?

Answer 1

What you can do is the following assume that $p=kp'$ with $p'|p$ and assume that: $$p'^{p-1}\equiv 1\mod p \tag 1$$

by multiplying both sides by $k^{p-1}$ we get : $$(kp')^{p-1}\equiv k^{p-1}\mod p \tag 2$$

but $p=kp'\equiv 0\mod p$ and this gives you $$k^{p-1}\equiv 0\mod p$$

and this is a contradiction because $k\in\{1,2,\cdots,p-1\}$ and it verifies $k^{p-1}\equiv 1 \mod p$

Answer 2

If $n^{p-1} \equiv 1 \bmod p$, then $n$ and $p$ are coprime because $nx = 1 + py$ for $x=n^{p-2}$ and some $y$.

If this holds for all $ n \in \left \{ 1,2,...,p-1 \right \}$, then the only proper divisor of $p$ is $1$.

Theferore, $p$ must be prime.