Prove $8k+1$ is a quadratic residue mod $2^m$ for all $m\ge 1$.

Question

Prove $8k+1$ is a quadratic residue mod $2^m$ for all $m\ge 1$.

Wikipedia claims this without a proof. I haven't found any proofs on the Internet. If you've found one, please share the link with us.

---

Edit: so I've written a proof:

$8k+1$ is always a quadratic residue mod $2,4,8$. Use induction.

Suppose $x_m^2\equiv 8k+1\pmod{2^m}$ for some $m\ge 3$.

Then find a $x_{m+1}$ such that $x_{m+1}^2\equiv 8k+1\pmod{2^{m+1}}$.

If $\frac{x_m^2-(8k+1)}{2^m}$ is odd, let $x_{m+1}=x_m+2^{m-1}$.

Then $\frac{x_{m+1}^2-(8k+1)}{2^m}=\frac{x_m^2-(8k+1)}{2^m}+x_m+2^{m-2}$ is even.

If $\frac{x_m^2-(8k+1)}{2^m}$ is even, let $x_{m+1}=x_m$.

---

If you have any other proofs, please let us know.

Answer 1

Wikipedia does source this claim to to article 103 of Disquisitiones Arithmeticæ, available in Latin here (p. 79-80). The proof there is quite short and looks like a simple counting argument, which I imagine (without bothering to chew through the Latin word by word) must go something like this:

The cases for $m\le 3$ can be checked by hand. For larger $m$:

First, every odd square has the form $8k+1$, because $(2n+1)^2=4n^2+4n+1=4n(n+1)+1$ and one of $n$ and $n+1$ is even.

Second, if we have odd numbers $a$ and $b$ such that $a^2\equiv b^2\pmod{2^m}$, then $b\equiv ad$ where $d^2\equiv 1\pmod{2^m}$.

The only $d$ with this property are $\pm1$ and $2^{m-1}\pm 1$. Thus each odd residue can be the square of at most four different numbers.

Since there are $2^{m-1}$ odd residues to square, and exactly $2^{m-3}=2^{m-1}/4$ residues of the form $8k+1$, each of them has to be hit.