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.


Unless I'm mistaken, this is quite easy and only involves the multiplicative property of the quadratic residue.

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.

  • $\begingroup$ Aha I suspected it should be simple! $\endgroup$ – Brando Nov 30 '15 at 3:25
  • $\begingroup$ 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. $\endgroup$ – Lucia Nov 30 '15 at 3:26
  • $\begingroup$ No, I am thinking that $p$ and $q$ are very near in size, which prohibits this obstruction. $\endgroup$ – Brando Nov 30 '15 at 3:28
  • $\begingroup$ 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. $\endgroup$ – Brando Nov 30 '15 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.