# Prime number test and Fermat's little theorem

We've learn in class that if $a^{p-1} \not\equiv 1 \pmod p$ then $p$ must be a composite number.
What is the explanation for that?

Thanks!

-
Do you already know some group theory? –  DonAntonio Feb 1 at 14:39
$a^{p-1} \equiv 1 \pmod p$ if $p$ is a prime: en.wikipedia.org/wiki/Fermat's_little_theorem .But there are none primes such that the equation holds, like $341=11 \cdot 31$. –  miracle173 Feb 1 at 14:41
@miracle173, but, if $a^{p-1}\not\equiv 1 \pmod p,p$ can not be prime –  lab bhattacharjee Feb 1 at 14:43
@DonAntonio, I do know group theory. –  SuperStamp Feb 1 at 14:44

At first $a$ and $p$ must be coprime, otherwise the statement is false. For example: Let $p$ be prime number and let $a=p$, then obviously we have:

$$p^{p-1} \equiv 0 \not \equiv 1 \pmod p$$

But we said that $p$ is prime number, so the statement is false:

If $(a,p) = 1$, then for every prime number we have:

$$a^{p-1} \equiv 1 \pmod p$$

This is true due to Fermat's Little Theorem. If you are interested in proof for this Theorem, I'm sure there are few on the Internet, because this is famous theorem.

So if $p$ is prime then $a^{p-1} \equiv 1 \pmod p$ holds, but if it doesn't hold it then $p$ can't be a prime number. So $p$ must be compisite.

Note that the converse doesn't hold, i.e. if $p$ is composite, then $a^{p-1} \equiv 1 \pmod p$ isn't always true. For more you can check Fermat pseudoprimes

-
Since you know group theory, you can see that if $\;\Bbb F_p:=$ the ring with $\;p\;$ elements, then $\;\Bbb F_p^*=\;$ the multiplicative group of invertible elements, and thus $\;\forall\;a\in\Bbb F_p^*\;,\;\;a^r=1\;,\;\;r=\left|\Bbb F_p^*\right|\;$
$$r=\left|\Bbb F_p^*\right|=p-1\iff p\;\;\text{is a prime number}\ldots$$