# Quadratic congruence

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?

## 3 Answers

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

• 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}$$