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.

There is question

For each of prime $p$, show that the congruence $x^2 \equiv1 \pmod {p^a}$ has precisely two solutions.

Continue and show that the congruence $x^2 \equiv 1 \pmod {2^a} $ has one solution if $a=1$, two solutions if $a=2$, and four solutions if $a \ge 3$.

I don't know how to do. Help please?

share|improve this question
add comment

3 Answers 3

up vote 1 down vote accepted

A hint has been given already for odd primes. So let us deal with $2^a$. If $a=1$ or $a=2$, you should be able to verify the assertion, by just calculating.

For practice, we can also do an explicit computation for $a=3$. It is easy to verify that $1^2\equiv 1\pmod{8}$, that $3^2\equiv 1\pmod{8}$, that $5^2\equiv 1\pmod{8}$, and that $7^2\equiv 1\pmod{8}$. And of course if $x$ is even then we cannot have $x^2\equiv 1\pmod{8}$, so there are $4$ solutions modulo $8$.

Now let us look at general $a\ge 3$. Suppose that $x^2\equiv 1\pmod{2^a}$. This can be rewritten as $$(x-1)(x+1)\equiv 1\pmod{2^a}.$$ Note that $x$ must be odd, so both $x-1$ and $x+1$ are even. If $x-1$ is congruent to $0\pmod{4}$, then $x+1\equiv 2\pmod{4}$. And if $x-1\equiv 2\pmod{4}$, then $x+1\equiv 0\pmod{4}$.

So if $x$ is odd, one of $x-1$ or $x+1$ is divisible by $4$, and the other is divisible by $2$ but by no higher power of $2$.

If $2^a$ divides $(x-1)(x+1)$, where $a\ge 3$, there are $4$ possibilities:

(i) $2^a$ divides $x-1$, that is, $x\equiv 1\pmod{2^a}$. Informally, $x-1$ all by itself contributes enough $2$'s.

(ii) $2^a$ divides $x+1$, that is, $x\equiv -1\pmod{2^a}$. Informally, $x+1$ contributes enough $2$'s.

(iii) $2^{a-1}$ divides $x-1$, but $2^a$ doesn't. Informally, $x-1$ does not quite have enough $2$'s, but $x+1$ chips in with the only $2$ it has. Then $x-1\equiv 2^{a-1}\pmod{2^a}$, that is, $x\equiv 1+2^{a-1}\pmod{2^a}$.

(iv) $2^{a-1}$ divides $x+1$, but $2^a$ doesn't. That gives $x\equiv -1+2^{a-1}\pmod{2^a}$.

It is almost obvious that if $a\ge 3$, these $4$ solutions are incongruent modulo $2^a$.

share|improve this answer
    
thank you for aid! –  Winnie Nov 9 '12 at 2:11
add comment

Hint $\ $ Any common divisor of $\rm\:x+1,\ x-1\:$ divides their difference $= 2.\:$ Thus if $\rm\:p\:$ is an odd prime and $\rm\:p^n|\:(x+1)(x-1)\:$ then $\rm\:p^n|\:x+1\:$ or $\rm\:p^n|\:x-1,\:$ so, $\rm\:mod\ p^n\!:\ x^2\equiv 1\:\Rightarrow\:x\equiv \pm1.$

share|improve this answer
    
thank you for aid! –  Winnie Nov 9 '12 at 2:09
    
to clarify. if $p^n$|(x+1) _and_ $p^n$|(x+1), then $p^n$|2. Hence if $p^n$ is odd, it can't divide 2 and hence can't be a common divisor of (x+1), (x-1). Thus, if $p^n$|(x+1)(x-1) ... –  user45793 Nov 11 '12 at 19:25
add comment

If $a\ge 3,$ and $2^a\mid (x-1)(x+1), x$ must be odd,

So, $$2^{a-2}\mid \left(\frac{x-1}2\right)\left(\frac{x+1}2\right)$$

Now, $$\frac{x+1}2-\frac{x-1}2=1$$ So, $$\left(\frac{x-1}2,\frac{x+1}2\right)=1$$

Now, either $$2^{a-2}\mid \left(\frac{x-1}2\right)$$ or $$2^{a-2}\mid \left(\frac{x+1}2\right)$$

If $$2^{a-2}\mid \left(\frac{x-1}2\right)\implies 2^{a-1}\mid(x-1)\implies x\equiv 1\pmod {2^{a-1}}\equiv 1,1+2^{a-1}\pmod {2^a}$$

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.