Question on logic of modular arithmetic So consider the implication:
$x^2\equiv 1 \pmod{p} \implies x \equiv \pm1 \pmod{p}$, where $p$ is an odd prime. These solutions are the only solutions, and are both present for any $p$. My question, is in a proof of this statement. 
$x^2\equiv 1 \pmod{p} \implies (x-1)(x+1) \equiv 1 \pmod{p} \implies p | (x-1)$ or $ p | (x+1)$ since $p$ is odd. Thus we know that either $x \equiv 1 \pmod{p}$ or $x \equiv -1 \pmod{p}$. I.e, both can't be true. 
How then, are they always both solutions to the original quadratic equation? Thanks for any help in clarifying this.
 A: They are both solutions since $\rm(\pm1)^2 = 1\:$ in every ring. One can prove both directions at once
$$\rm x^2\equiv 1\,\ (mod\ p)\iff p\mid(x\!-\!1)(x\!+\!1)\iff p\mid x\!-\!1\ \ or\ \ p\mid x\!+\!1 \iff x\equiv \pm1\,\ (mod\ p)$$
This is a special case of the fact that a polynomial over a field (or domain) can have no more roots that its degree, so $\rm\:x^2=1\:$ can have no more roots than the two universal  roots $\,\pm 1\:$ (which are distinct since $\rm\:p\ne 2).$ Beware that this fails in non-domains such as in $\,\Bbb Z/8 =$ integers mod $8,\:$ where, e.g. the above polynomial has two additional roots $\pm 3,\:$ since $\rm\,(\pm3)^2\equiv 1\ (mod\ 8).$
A: Both can be true if p=2. $(x+1)(x-1)=0$ (mod p) implies $(x+1)=0$ (mod p) or $(x-1)=0$ (mod p), because Zp is an integral domain.
A: They are both solutions to the congruence $x^2\equiv 1\pmod p$ for the same reason that they are both solutions to the ordinary equation $x^2=1$: if you take $x$ to be either $1$ or $-1$, the congruence and the equation are satisfied. Obviously $x$ can’t simultaneously be congruent to $1$ and $-1$ modulo an odd prime, any more than it can simultaneously be equal to $1$ and $-1$; why is that a problem? That just means that the two solutions really are distinct.
