Number theory lemma - $x^2 \equiv 1 \pmod p$ implies $x\equiv\pm 1\pmod p$

The proof is a follows:

Let $p$ be a prime number and $x$ in Z. If $x^2\equiv1\pmod p$ then $x\equiv\pm1\pmod p$.

Proof: By assumption, $p | x^2 - 1 = (x + 1)(x - 1)$. Thus $p | x + 1$ or $p | x - 1$. This completes the proof.

However if $p | x + 1$ then $x$ is congruent to $-1 \mod p$. However why is $p$ congruent to $1 \mod p$ ??

I'm struggling seeing this, and been sitting for some hours now trying to figure it out - please help.

Solution 1:

To show that the solutions of $x^2\equiv 1\pmod{p}$ are $x\equiv \pm 1$ actually requires that we prove two things.

We must show that (i) $x\equiv 1\pmod{p}$ is a solution, and $x\equiv -1\pmod{p}$ is a solution.

We must also show that (ii) there are no other solutions modulo $p$.

Proving (i) is easy. All we need to do is to verify that $(1)^2\equiv 1\pmod{p}$ and $(-1)^2\equiv 1 \pmod{p}$.

Note that if $p=2$ the two solutions are the same. For $1\equiv -1\pmod{2}$.

We now turn to the proof of (ii). We know that if $x^2\equiv 1\pmod{p}$, then $p$ divides $x^2-1$, and therefore $p$ divides $(x-1)(x+1)$.

Since $p$ is prime, and divides $(x-1)(x+1)$, we must have (a) $p$ divides $x-1$ or (b) $p$ divides $x+1$.

In Cae (a), we have $x\equiv 1\pmod{p}$. In Case (b), we have $x\equiv -1\pmod{p}$. There are no other possibilities.

Remark: Note that if $p$ is composite, then the result can fail. For example, the congruence $x^2\equiv 1\pmod{8}$ has four solutions modulo $8$, namely $x\equiv \pm 1\pmod{8}$, and $x\equiv \pm 3\pmod{8}$.

Solution 2:

Perhaps it is easier to view this as euqation $x^2-1=0$ over the finite field $\mathbb{F}_p$. Since $0=x^2-1=(x+1)(x-1)$, and the field has no zero divisors, we must have either $x=1$ or $x=-1$ in $\mathbb{F}_p$. This means $x\equiv 1(p)$ or $x\equiv -1(p)$.