# 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.

-

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).$

-
The last equivalence doesn't seem to make sense. It basically says A or B implies A and B. – user45793 Nov 11 '12 at 20:25
@Carl $\$ Above, $\rm\: x \equiv \pm1\:$ means $\rm\:x\equiv 1\ \ or\ \ x\equiv -1,\:$ just like the use of the $\pm$ sign in the formula for the roots of a quadratic equation. – Bill Dubuque Nov 11 '12 at 20:29
Ok, then this goes back to my original problem. 1 and -1 is clearly a solution in every ring. The proof only shows or. What am I missing here? – user45793 Nov 11 '12 at 20:32
my apologies. I figured it out. I don't know why I had a mental block there. Sorry for wasting time. – user45793 Nov 11 '12 at 20:39

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.

-

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.

-
if $p=2$ the problem is trivial since the only 2 residue classes mod 2 are 0, 1. The question I'm asking about is how there are always 2 distinct solutions. In mod 2, these solutions become degenerate. – user45793 Nov 11 '12 at 20:19