Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer
thank you for aid! – Winnie Nov 9 '12 at 2:11

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|cite|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

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

Your Answer


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.