$ax^2+bx+c \equiv 0 \mod 2^k$

It is fairly easy to see that all integers are *quadratic* residues mod 2, and that 0 and 1 are both *quadratic* residues mod 2.

But what about for larger powers of 2?

For $k = 2$, that is, mod 4, the *quadratic* residues are also 0 and 1. ($0^2 \equiv 2^2 \equiv 0 \mod 4, 1^2 \equiv 3^2 = 9 \equiv 1 \mod 4$). For $k = 3$, the *quadratic* residues are 0, 1, 4; for $k = 4$, the *quadratic* residues are 0, 1, 4, 9. Do we have a pattern? Not quite.

For $k = 5$, the *quadratic* residues are 0, 1, 4, 9, 16, 25, and **17**.

For $k = 6$, the *quadratic* residues are 0, 1, 4, 9, 16, 25, 36, 49, and 17, 33, 41, 57.

For $k = 7$, we get 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, and 17, 33, 41, 57, and 65, 73, 89, 97, 105, 113, and 68.

We can surely generate the *quadratic* residues of $2^k$ from the first $2^{k-1}$ elements. But $\forall k \geq 2$, we can generate the *quadratic* residues from the first $2^{k-2}$ elements. (I cannot figure out an easy proof of this.)

According to Wikipedia, a non-zero number will be a *quadratic* residue $\mod 2^k, k > 3$ if it is in the form $4^n \times (8m+1)$ with $0 \leq n \leq \frac{k}{2}, 0 \leq m < 2^{k-3}$.

A rough sketch of a proof was offered; but my observations can confrim it (i.e., $68 = 4 \times 17 = 4 \times (2 \times 8 + 1)$).

Including the trival *quadratic* residue 0, for the given $k$, there are # residues:

$k$ = | # quadratic residues |

1 | 2 |

2 | 2 |

3 | 3 |

4 | 4 |

5 | 7 |

6 | 12 |

7 | 23 |

8 | 44 |

*edit: added "quadratic" to every instance of the word "residue" for Andy's benefit.*