Showing $x^2 \equiv 1 \pmod p$ implies $x \equiv \pm 1 \pmod p$

Question

Show that $x^2 \equiv 1 \pmod p$ implies $x \equiv 1 \pmod p$ or $x \equiv (p-1)\pmod p$ for every prime $p$.

I understand one might be able to prove on of the converses but I have no clue as to how to proceed with it and any help would be really appreciated.

Answer 1

If

$x^2 \equiv 1 \mod p, \tag 1$

then

$(x - 1)(x + 1) \equiv x^2 - 1 \equiv 0 \mod p; \tag 2$

therefore,

$p \mid (x - 1)(x + 1); \tag 3$

now since $p$ is prime we have

$[p \mid (x - 1)] \vee [p \mid (x + 1)]; \tag 4$

if $p \mid (x - 1)$, then

$x - 1 \equiv 0 \mod p \Longrightarrow x \equiv 1 \mod p; \tag 5$

if this fails, that is, if $p \not \mid (x - 1)$, then we must have

$p \mid (x + 1) \Longrightarrow x + 1 \equiv 0 \mod p \Longrightarrow x \equiv -1 \mod p. \tag 6$

Answer 2

The idea is to use the fact that because $\mathbb{Z}/p\mathbb{Z}$ is an integral domain, for a polynomial $(x-a_1)\dots(x-a_n) \equiv 0$ (mod $p$), then we must have for some $i$ that $(x-a_i) \equiv 0$ (mod $p$), from which the desired result then follows. The fact that $\mathbb{Z}/p\mathbb{Z}$ is an integral domain follows from Euclid's lemma that if $p|ab$, then either $p|a$ or $p|b$, and a quick argument by induction gives us what we need to prove the result.