# 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.

• How would you proceed if there was no "mod $p$" (meaning how do you show $a^2 = 1$ implies $a = 1$ or $a = -1$) ? Commented Sep 16, 2011 at 20:45
• Ah, it was much simpler than I thought. Thank you. Commented Sep 16, 2011 at 21:02

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$).

• Thanks, Bill - you're answers are always not only insightful, but also helpful! Commented Sep 16, 2011 at 21:10

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.