$\bmod p\!:\ x^2\equiv 1\iff x\equiv \pm1\ $ for prime $p$ Let $p$ be a prime. Show that for all integers $x$, $x^2\equiv 1 (\text{mod} \ p) $ if and only if $x \equiv 1 (\text{mod} \ p)$ or $ x \equiv p-1 \ (\text{mod} \ p ). $

I know that I have to prove this both forward and backward. I'm not really sure where to begin
 A: One direction is clear. Now if $x^2 \equiv 1 \pmod p$, we have $$x^2 - 1 \equiv 0 \pmod p \iff (x - 1)(x + 1) \equiv 0 \pmod p \iff p | (x - 1)(x + 1)$$
But since $p$ is prime, $p$ can only divide the product if it divides one of the terms, and the result follows.
A: The proof in T. Bongers answer is perhaps the most direct way to proceed. There is however another viewpoint that it is insightful, since it relates to our prior intuition about the number of roots a polynomial may have. Recall that if $x=1$ is a root of a polynomial $f(x)$ then, by the Factor Theorem, we infer $f(x) = (x-1) g(x)$. Now suppose that $x = r \ne 1$ is a different root. Then $f(r) = (r-1) g(r)\equiv 0.$ Since $r-1\not\equiv0,\,$ we know, by Bezout, that it has an inverse $s.$ Multiplying by $s$ we infer $g(r)\equiv 0.$ Hence every other root of $f$ is a root of the lower degree polynomial $g$. Thus if $f$ is quadratic then the only other root of $f$ is the root of the linear polynomial $g$. In particular, a quadratic has at most two roots. 
By induction on the degree of $f$ the same proof shows that a nonzero polynomial has no more roots than its degree. Note that the only property of the integers mod $p$ that we employed is that nonzero elements are cancellable. Thus the proof will work in any "number system" that has this property, i.e. any integral domain. In fact, it is easy to show that this property characterizes integral domains, i.e. every nonzero polynomial has no more roots than its degree $\iff$ every nonzero element is cancellable.
