1

Okay, so I've been trying for hours to try prove this

Let $n \geqslant 3$. Show that the equation $x^2 \equiv 1 \pmod{2^n}$ has exactly $4$ solutions modulo $2^n$.

I tried using induction but I just can't work it out, I think I'm just missing something simple. however, I know how to find the $4$ solutions, such as when $n=3$, the $4$ solutions $1,3,5,7$, and when $n=4$ the $4$ solutions are $1,7,9,15$, and when $n=5$ the $4$ solutions are $1,15,17,31$ etc. … so how do i prove for all $n \geqslant 3$ that there are exactly $4$ solutions $\mod 2^n$? Using induction?

Thanks for any help in advance.

Daniel Fischer
  • 206,697
Madmarkshero
  • 47

1 Answers1

2

Hint: A solution modulo $2^{k+1}$ is also a solution modulo $2^k$. So if you know that modulo $2^k$ the only possibilities are $a_1,a_2,a_3$ and $a_4$, then modulo $2^{k+1}$ the only possibilities are $a_1,a_2,a_3,a_4$ and $a_1+2^k,a_2+2^k,a_3+2^k,a_4+2^k$. Just check which of those work.

In other words, yes, you have found the correct scheme, and can prove it by induction.

Jyrki Lahtonen
  • 133,153