# 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 '14 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 '14 at 14:41
@miracle173, but, if $a^{p-1}\not\equiv 1 \pmod p,p$ can not be prime – lab bhattacharjee Feb 1 '14 at 14:43
@DonAntonio, I do know group theory. – SuperStamp Feb 1 '14 at 14:44

## 2 Answers

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|\;$

Now you can easily show that

$$r=\left|\Bbb F_p^*\right|=p-1\iff p\;\;\text{is a prime number}\ldots$$

-
Actually I have a basic knowledge in group theory, but thanks for the enrichment! – SuperStamp Feb 1 '14 at 14:52