If p is a prime and $a^2 \equiv 1$ mod p, prove that $a \equiv \pm 1$ mod p.

Question

If p is a prime and $a^2 \equiv 1$ mod p, prove that $a \equiv \pm 1$ mod p.

I am having trouble proving this. I think I may have proved. I squared both sides because you the same rules as when you are in base 10 the only difference is that your answer stays in terms of mod m. My proof is as follows:

Let $p$ be prime and $a^2 \equiv 1$ mod p.

Then, $a^2 \equiv 1$ mod p$\Leftrightarrow$ $\sqrt{a^2 }\equiv \sqrt{1}) \Leftrightarrow a\equiv \pm1$

Answer 1

$$a^2 \equiv 1 \pmod{p}$$

$$(a-1)(a+1) \equiv 0 \pmod{p}$$

If $a-1$ is not a multiple of $p$ (hence the index of $p$ is $0$ in prime factoriation of $a-1$) and $a+1$ is not a multiple of $p$ (hence the index of $p$ is $0$ in prime factoriation of $a+1$), then their product is not a multiple of $p$ since $p$ is a prime. We can see this from the prime factorization. In the prime factorization of $(a-1)(a+1)$, index of $p$ is $0$. Hence it is not divisible by $p$.

Hence $a-1 \equiv 0 \pmod{p}$ or $a+1 \equiv 0 \pmod{p}$

Answer 2

No, that doesn't work.

For one thing, where are you using the fact that $p$ is prime?

Instead, express the congruence as a divisibility condition, work with that, and then convert back later . . .

\begin{align*} &a^2 \equiv 1\;(\text{mod}\;p)\\[4pt] \iff\;&p{\,\mid\,}(a^2-1)\\[4pt] \iff\;&p{\,\mid\,}(a+1)(a-1)\\[4pt] \iff\;&p{\,\mid\,}(a+1)\;\;\text{or}\;\;p{\,\mid\,}(a-1)\qquad \text{[since $p$ is prime]}\\[4pt] \iff\;&a+1 \equiv 0\;(\text{mod}\;p)\;\;\text{or}\;\;a-1 \equiv 0\;(\text{mod}\;p)\\[4pt] \iff\;&a \equiv -1\;(\text{mod}\;p)\;\;\text{or}\;\;a \equiv 1\;(\text{mod}\;p)\\[4pt] \iff\;&a \equiv \pm 1\;(\text{mod}\;p)\\[4pt] \end{align*}

Answer 3

Consider the quotient ring $\mathbf Z/p\mathbf Z$.

Since $p$ is prime, this is a field, and $a$ is a solution of the equation $x^2-1=0$. In a field, a polynomial of degree $n$ has at most $n$ roots, and we already have two obvious roots, $1$ and $-1$ (these are one and the same if $p=2$).