Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 1 down vote accepted

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

share|improve this answer
    
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

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.

share|improve this answer
    
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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.