<s>[INST] $1+8k$ is a quadratic residue modulo $2^n$ 
Prove that $1+8k$, for all nonnegative integers $k$, is a quadratic residue modulo $2^n$, where $n$ is a positive integer.

For $n = 5$, we have $0,1,9,17,25$, which are all quadratic residues modulo $2^5$. How do we prove this in general?
 [/INST] We can assume $n\ge 4$, because otherwise it is trivial.

Fact 1: Two odd numbers have the same square modulo $2^n$ if and only if they are equal or opposite modulo $2^{n-1}$.

Proof: If $(2s+1)^2\equiv (2t+1)^2\pmod {2^n}$ then $s^2+s\equiv t^2+t\pmod {2^{n-2}}$ and
$$(s-t)(s+t+1)\equiv 0\pmod{2^{n-2}}$$
Only one of these factors is even, so we have $s\equiv t$ or $s+t\equiv -1 \pmod{2^{n-2}}$ and the fact follows.
An immediate consequence is that each odd square modulo $2^n$ has exactly four square roots.
Then there are exactly $2^{n-3}$ odd quadratic residues modulo $2^n$, a fourth of the odd residues.
On the other hand,

Fact 2: If $r$ is odd and $m\not\equiv 1\pmod 8$ then $r$ is not a quadratic residue modulo $2^n$.

Proof: Suppose the contrary. If $r\equiv m^2\pmod{2^n}$, we have that $2^n$ divides $(m^2-1)-(r-1)$. Since $8$ divides $m^2-1$, it also divides $r-1$, a contradiction.
To finish the proof, note that the set of odd numbers from $0$ to $2^n$ can be divided in $2^{n-2}$ packs of $4$ numbers each. These packs can be of the form $\{8k+1,8k+3,8k+5, 8k+7\}$. Among these four numbers only $8k+1$ can be a square. Since a fourth of the odd residues are quadratic, $8k+1$ must be a square for each $k$.
</s>