Prove: $k^2 \equiv 1 \mod p \implies k \equiv \pm1 \mod p$

Question

I want to show that for every prime $p$ and $n \in \mathbb Z$:

$$n^2 \equiv 1 \mod p \implies n \equiv \pm 1 \mod p$$

I think I already got a solution for odd $n \,\,\,(n := 2k + 1)$:

$$ n^2 \equiv 1 \mod p \\ \implies (2k + 1)^2 \equiv 1 \mod p \\ \implies 4k(k+1) \equiv 0 \mod p \\ \implies 4k \equiv 0 \mod p \text{ or } k + 1 \equiv 0 \mod p \\ \implies k \equiv \pm 1 \mod p \\ \implies n \equiv \pm 1 \mod p $$

But I'm stuck for even $n$. Maybe this differentiation between odd and even $n$ isn't even necessary at all and there is a more simple solution. Any help is welcome.

Answer 1

The distinction between odd and even $n$ is indeed unnecessary.

$n^2\equiv 1\pmod{p}$ is by definition equivalent to $p\mid (n^2-1)=(n-1)(n+1)$. Then by definition of primality (namely $p\mid ab$ implies $p\mid a$ or $p\mid b$), we have $p\mid n-1$ or $p\mid n+1$, or $n\equiv 1\pmod{p}$ or $n\equiv -1\pmod{p}$.

Hence $n\equiv \pm 1 \pmod{p}$.

More directly, without leaving the integers mod $p$, one can note that $$n^2\equiv 1\pmod{p}$$ $$\implies (n-1)(n+1)=n^2-1\equiv 0 \pmod{p},$$ hence $$n-1\equiv 0 \quad\text{or}\quad n+1\equiv 0 \pmod{p},$$ so $$n\equiv \pm 1 \pmod{p}.$$

Answer 2

When $p$ is a prime, $\mathbb{Z}_p$ is a field for the natural operations $+$ and $\times$. A polynomial of degree $2$ has at most $2$ roots in a field.

(NB: the polynomial here is $X^2-1$ and the roots are $1$ and $-1$)