Suppose $r$ integers $n\_1, \ldots, n\_r$ are given such that $0<|n\_i|<N$ for $1 \leq i \leq r$ and for a natural number $N.$ Is it possible to find a prime number $p$ such that all numbers $n\_1, \ldots, n\_r$ are quadratic nonresidue mode $p$? Can we say $p < N^6?$ 


I think the answer to my first question is yes, but I don't know how to give an upper bound for $p$? 



Quadratic Nonresidue
I don't think this is true in general, for instance, if there exists $1\leq i <j<k<r$ such that $n\_in\_j = n\_k$, then $(n\_i/p)=(n\_j/p)=-1\implies (n\_k/p)=1$ (where $(a/p)$ is the Legendre symbol). Moreover, if $n\_i$ is a perfect square, then trivially you have that for every prime $p$, $n\_i$ is a quadratic residue. So, you must have the assumption that, for each $n\_i$, there is a prime $p\mid n\_i$, such that $p$ appears with an odd exponent in decomposition of $n\_i$.


However, if you assume that, say, $(n\_i,n\_j)=1$ for every $i \neq j$, then yes, you can construct such a prime. Here is one way. For each $n\_1,\dots,n\_r$, let us consider the sets $P\_1,P\_2,\dots,P\_r$ where $P\_i$ is the set of prime divisors of $i $, that appear with an odd exponent (assumed to be non-empty). Now, select primes $p\_j\in P\_j$ for every $j$, let $\mathcal{P}=\{p\_1,\dots,p\_r\}$, and let $\mathcal{Q}=\bigcup\_{k=1}^r P\_k \setminus \mathcal{P}$. 


We will construct a prime $q$ such that $q$ is a quadratic residue modulo $p$ for every $p\in\mathcal{P}$, and $q$ is quadratic non-residue, modulo every $p\in \bigcup\_{k=1}^r P\_k \setminus \mathcal{P}$, using the law of quadratic reciprocity. Take $q\equiv 1\pmod{8}$, and thus, $(-1)^{(p-1)/2 \cdot (q-1)/2}=1$. Now, take $q\equiv n\_p\pmod{p}$, where $n\_p$ is a quadratic residue, modulo $p$ for every $p\in\bigcup\_{k=1}^r P\_k \setminus \mathcal{P}$; and take $q\equiv n\_p'\pmod{p}$, for every $p\in \mathcal{P}$, where $n\_p'$ is a quadratic non-residue. Clearly, such a $q$ exists (from Chinese remainder theorem), and satisfies your claim.


