1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .