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