7
$\begingroup$

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?

$\endgroup$

3 Answers 3

4
$\begingroup$

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

$\endgroup$
1
  • $\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, 2012 at 19:25
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Why is it $(x-1)(x+1)\equiv1\text{ (mod }2^a)$ and not $(x-1)(x+1)\equiv0\text{ (mod }2^a)$? Isn't the reasoning $x^2\equiv1\text{ (mod }2^a)$ becomes $x^2-1\equiv0\text{ (mod }2^a)$? $\endgroup$
    – user711703
    Jul 9, 2021 at 20:29
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .