Let $p$ be an odd prime number.
- If $p \equiv 3 \bmod 8$ or $p \equiv 5 \bmod 8$, $2$ is not a square mod $p$.
- If $p \equiv 3 \bmod 8$ or $p \equiv 7 \bmod 8$, $-1$ is not a square mod $p$.
If $p \equiv 1 \bmod 8$, there seems to be no way to choose a single $n \in \mathbb{Z}$ such that $n$ is not a square mod $p$ regardless of the choice of $p$. Can one prove that this is not the case? What if we continue searching for residues mod 16?
In fact, the more general question I would like to know the answer to, is the following: Can there be a finite set of natural numbers $S$ such that that for each prime number $p$, there exists an $n \in S$ such that $n$ is not a square mod $p$?