Proof explanation: If $p$ is prime, then $x^2 \equiv 1 \:(\mathrm{mod}\:p) \Leftrightarrow x \equiv \pm1 \:(\mathrm{mod}\:p)$

Question

I was asked to prove the following theorem:

Let $p$ be prime. Then for any $x$, the following holds true: $x^2 \equiv 1 \:(\mathrm{mod}\:p) \Leftrightarrow x \equiv \pm 1 \:(\mathrm{mod}\:p)$

My proof is as follows:

$\begin{alignat}{2} && x^2 \equiv 1 \:(\mathrm{mod}\:p) \\ &\Leftrightarrow\quad &x^2 -1\equiv 0 \:(\mathrm{mod}\:p) \\ &\Leftrightarrow &p \mid (x^2 - 1) \\ &\Leftrightarrow &p \mid (x - 1)(x + 1) \\ &\Leftrightarrow &p \mid (x - 1) \vee p \mid(x + 1) \\ &\Leftrightarrow &x \equiv 1 \:(\mathrm{mod}\:p)\vee x\equiv -1 \:(\mathrm{mod}\:p) \end{alignat}$

My problem: I didn't (actively) use the fact that $p$ is prime, which is suspicious to me, because it means that either my proof is wrong, or that I used it somewhere in an implicit way without realizing it.

Can somebody point out where I used the fact that $p$ is prime?

Answer 1

The step $$p \mid (x-1)(x+1) \iff p\mid (x-1) \lor p\mid (x+1)\tag{$\ast$}$$ uses that $p$ is prime.

Actually not quite, because the equivalence $x^2 \equiv 1 \pmod{m} \iff x \equiv \pm 1 \pmod{m}$ also holds for some composite moduli (and it trivially holds for $\lvert m\rvert \leqslant 1$). It holds whenever the group of units modulo $m$ is cyclic, and for composite $m > 1$ that happens when $m = 4$, $m = p^k$, or $m = 2p^k$ for an odd prime $p$ and $k \geqslant 1$.

So the specific case $(\ast)$ of $$p \mid ab \iff p\mid a \lor p \mid b$$ does not characterise primes (or units or $0$) like the general case does.

Answer 2

For $p\ge2$, We have either $p|x-1$ or $p|x+1$. So $x+1 \equiv 0 \mod p$ or $x-1 \equiv 0 \mod p$. Implying $$x\equiv \pm 1 \mod p$$