Proof explanation: If $p$ is prime, then $x^2 \equiv 1 \:(\mathrm{mod}\:p) \Leftrightarrow x \equiv \pm1 \:(\mathrm{mod}\:p)$ 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} &amp;&amp; x^2 \equiv 1 \:(\mathrm{mod}\:p) \\ &amp;\Leftrightarrow\quad &amp;x^2 -1\equiv 0 \:(\mathrm{mod}\:p) \\ &amp;\Leftrightarrow &amp;p \mid (x^2 - 1) 
\\ &amp;\Leftrightarrow &amp;p \mid (x - 1)(x + 1) 
\\ &amp;\Leftrightarrow &amp;p \mid (x - 1) \vee p \mid(x + 1)
\\ &amp;\Leftrightarrow &amp;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?
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 &gt; 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.
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$$