# Least simultaneous quadratic non-residue

Suppose $p,q$ are distinct primes with least quadratic non-residues $n_p$ and $n_q$ respectively. Can one bound the least $n$ for which $\left(\frac{n}{p}\right)=\left(\frac{n}{q}\right)=-1$ in terms of $n_p$ and $n_q$?

I had originally thought this would be a consequence of quadratic reciprocity and the Chinese Remainder Theorem, and so would be bounded by $n_pn_q$, but I can't seem to work it out.

If $n_p=n_q$ then we are done, because this very number is a simultaneous quadratic nonresidue. Otherwise we can without loss of generality suppose $n_p<n_q$. Then $(n_p|p)=-1$ while $(n_p|q)=1$. Also we know $(n_q|q)=-1$. If we also have $(n_q|p)=-1$ then $n_q$ is a simultaneous quadratic nonresidue. Otherwise $(n_q|p)=1$. Then by multiplicativity we have $(n_pn_q|p)=(n_pn_q|q)=-1$, so $n_pn_q$ is a simultaneous quadratic nonresidue.
• The only fly in the ointment is if $n_p=q$ or $n_q=p$. But the OP is perhaps not interested in these pathological cases. – Lucia Nov 30 '15 at 3:26
• No, I am thinking that $p$ and $q$ are very near in size, which prohibits this obstruction. – Brando Nov 30 '15 at 3:28
• Unfortunately, this argument seems to break down when there are three primes $p,q,r$. What could happen that $n_p=n_q<n_r$. Then if $(n_r|p)=-1$ and $(n_r|q)=1$ I don't see the same trick working. – Brando Nov 30 '15 at 22:36