Let $p$ be a prime. Prove that $x^2\equiv 1\mbox{ mod }p$ if and only if $x\equiv 1\mbox{ mod }p$ or $x\equiv p-1\mbox{ mod }p$.

Question

I am a little confused about how to start a proof like this. Any pointers are appreciated. Thank you.

Let $p$ be a prime. Prove that $x^2\equiv 1\mbox{ mod }p$ if and only if $x\equiv 1\mbox{ mod }p$ or $x\equiv p-1\mbox{ mod }p$. Useful note aside: $p-1\equiv -1\mbox{ mod }p. Why?$

Answer 1

$x^2\equiv1\bmod p$ means $p|x^2-1=(x-1)(x+1)$, which means $p|x-1$ or $p|x+1$,

which means $x\equiv1\bmod p$ or $x\equiv-1\bmod p$.

$-1\equiv p-1\bmod p$, because the difference of $p-1$ and $-1$ is $p$, which is divisible by $p$.

Answer 2

This will fall into your lap like magic.

The definition of $x^2 \equiv 1 \pmod p$ means that $p|x^2 -1$. And as $x^2-1 = (x+1)(x-1)$ then $p|(x+1)(x-1)$.

But $p$ is prime and we've got this thing called Euclids lemma so either $p|x+1$ or $p|x-1$.

But the definition of $x \equiv 1 \pmod p$ is $p|x-1$ and the definition of $x \equiv-1\pmod p$ is $p|x-1$.

So either $x\equiv 1\pmod p$ or $x \equiv -1\pmod p$.

Oh... okay... one more thing,not hard. $x\equiv -1 \pmod p \iff p|x+1 \iff p|x+1 -p\iff p|x-(p-1)\iff x\equiv p-1 \pmod p$.

If you blink, you'll miss it.