Mystical relation of QR's of 7

Question

Of the integers coprime to $7$, namely $1,2,3,4,5,6$, those with $2$ binary bits are the same of the non-quadratic residues, the rest have $1$ bit.

QR: $1(1_2), 2(10_2), 4(100_2)$

NQR: $3(11_2), 5(101_2), 6(110_2)$

Can anyone explain this?

Answer 1

If $2$ is a quadratic residue, then all its powers are quadratic residues too. Since $7$ is quite small, it happens that the powers of $2$ ($1$, $2$, $4$) manage to cover all possible quadratic residues. And since everything between $1$ and $6$ has either one or two $1$ bits, the non-residues get two $1$ bits.

So pretty much a coincidence due to the fact that $7$ is small.

Answer 2

If $p$ is an odd prime let $S_p$ be the set of members of $\{1,2,...,p-1\}$ that are quadratic residues mod $p$. The number of members of $S_p$ is $(p-1)/2$. There exists at least one $g$ with $1\leq g<p$ for which the set of residues of $\{g^n :1\le n\le (p-1)2\}$ modulo $p$ is equal to the set $S_p$. I would not describe this as obvious. For some $p$ we can take $g=2$, in which case the quadratic residues mod $p$ co-incide with the quadratic residues mod $p$ of the powers of $2$. For example $p=7$ or $p=17$ or $p=23$ or $p=29$.The case $p=7$ is the only one where we can restrict it to the powers of $2$ that are less than $p$ because $p>7$ implies $2^{(p-1)/2}>p.$