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!
 A: 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
A: 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$$
