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?


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


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

  • $\begingroup$ 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) ... $\endgroup$ – 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}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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