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
    The last equivalence doesn't seem to make sense. It basically says A _or_ B implies A _and_ B.2012-11-11
  • 0
    @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.2012-11-11
  • 0
    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?2012-11-11
  • 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.