Prove that if $p$ is a prime and if $a^2\equiv 1 \bmod p$ then $a \equiv 1 \bmod p$ or $a \equiv -1 \bmod p$ The title says it all, but for being thorough:

Prove that if $p$ is a prime and if $a^2 \equiv 1 \bmod p$ then $a \equiv 1 \bmod p$ or $a \equiv -1 \bmod p$.

Just looking for hints / tips, not full out solutions.
 A: Just a note on this problem, did you know that with the problem you have (and with a little knowledge of group theory) you can prove one direction of Wilson's Theorem?
$\textbf{Theorem :}$ If $p$ is a prime number, then $(p-1)! \equiv -1$ mod $p$.
Now the first step to this proof has already been done above by Bill. Now for the second part:
$\textbf{Exercise :}$ Prove that in a finite abelian group with $a_1 \ldots a_n$ all its elements, the element $x = a_1a_2 \ldots a_n$ must necessarily satisfy $x^2 = e$, the group's identity.
Hint: Note that $x$ is the product of all the elements in the group. What is the inverse of such an $x$?
Finally, put this all together and prove one direction of Wilson's Theorem as stated above.  
A: HINT $\rm\ \ a^2\equiv 1\pmod{p}\ \iff\ p\ |\ a^2-1\:.\:$ A prime divides a product iff it divides some factor.   
Can you write $\rm\:a^2-1\:$ as a product? $\ $ Hint: $\:1 = 1^2\:$ might make a difference.
NOTE $\ $ The primality of $\rm\:p\:$ is crucial. Can you find a counterexample if $\rm\:p\:$ is composite?  If you get stuck see my post here for more on nontrivial square roots (of $1$).
