1
$\begingroup$

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.

3 Answers 3

1

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

  • 0
    my apologies. I figured it out. I don't know why I had a mental block there. Sorry for wasting time.2012-11-11
0

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.

  • 0
    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.2012-11-11
0

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.