No canonical non-quadratic residue for primes $\equiv 1 \bmod 8$? 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$?
 A: In other words given a finite set of numbers $S$ find a prime $p$ such that for all $n\in S$,  $n$ is a quadratic residue modulo $p$.
Now from quadratic reciprocity we have that
$$\left(\frac{n}{p}\right)=1 \Leftrightarrow p\equiv a_i \text{
(mod $4n$)}$$ where $a_i$ are some numbers depending on $n$.
It then follows from Dirichlet's theorem on primes in an arithmetic progression that there are infinitely many such primes.
A: A simple consequence of quadratic reciprocity is that if $n$ is odd, then
$$p \equiv 1 \pmod{4n} \implies \left(\frac{n}{p}\right)=1.$$
Pair this together with $p \equiv 1 \pmod 8 \implies \left(\frac{-1}{p}\right)=\left(\frac{2}{p}\right)=1$, and it's easy to see that for any finite set $S$, we can take $N$ to be the lcm of all elements of $S$, and then for any prime $p \equiv 1 \pmod{8N}$ the entirety of $S$ will be quadratic residues modulo $p$.
This also helps to explain why you are having particular difficulty finding a generic non-residue for primes congruent to $1$ mod $8$.
