For a positive integer $n$, let $a(n)$ the smallest number $k>0$ such that $-n$ is not a quadratic residue modulo $k$.

Using CRT, we can prove that all values of $a(n)$ are prime powers, and every prime power except $2$ appears in the sequence.

See OEIS A354597 .

It's easy to prove that $a(n)\leqslant4n-1$ (take a prime factor $p$ of $4n-1$ such that $p\equiv-1\,(\text{mod }4)$, then $-n$ is not a square modulo $p$).

But according to the figure below, it seems that we can improve the previous inequality !

How to proceed ?

Thanks !

Remark : This question has been asked previouly on math.SE but no response was given.

enter image description here


1 Answer 1


This question is closely related to Linnik's problem on the least quadratic nonresidue for a given prime modulus.

Let us consider the quadratic Dirichlet character $\chi(m):=\left(\frac{-n}{m}\right)$ whose conductor divides $4n$. Assuming the Riemann hypothesis for $L(s,\chi)$, it follows from a result of Ankeny (see Theorems 1-2 here) that there is a prime $p=O((\log n)^2)$ such that $\chi(p)=-1$. That is, $-n$ is a quadratic non-residue modulo $p$, whence $a(n)\leq p$. We conclude that $a(n)=O((\log n)^2)$. The implied constants can be determined explicitly. The weaker Lindelöf hypothesis leads to the bound $a(n)<n^{o(1)}$, which is the analogue of Linnik's conjecture for the least quadratic nonresidue.

If we don't assume any unproven hypothesis for $L(s,\chi)$, the Pólya-Vinogradov inequality still ensures that $p<n^{\frac{1}{2\sqrt{e}}+o(1)}$, hence also that $a(n)<n^{\frac{1}{2\sqrt{e}}+o(1)}$. See Theorem 9.18 and Corollary 9.19 in Montgomery-Vaughan: Multiplicative number theory I. Furthermore, using Burgess's bound (see Theorem 2 here), the fraction $\frac{1}{2\sqrt{e}}$ in the exponent can be improved to $\frac{1}{4\sqrt{e}}$. Compare with Theorem 9.27 in the quoted book.

  • 1
    $\begingroup$ Thank you very much for your explanations ! I will study this. Do you think we can establish a more modest inequality (like $a(n)=O(\sqrt{n})$) by elementary ways ? $\endgroup$
    – uvdose
    Jul 20, 2022 at 12:10
  • 2
    $\begingroup$ @uvdose This might depend on what you call "elementary". The proofs of Theorem 9.18 and Corollary 9.19 in the book by Montgomery-Vaughan are elementary in the sense that they are short and they don't use more than what an undergraduate math major is supposed to know. $\endgroup$
    – GH from MO
    Jul 20, 2022 at 12:13
  • $\begingroup$ Ok, I will read this in detail. Thank you for giving your time ! $\endgroup$
    – uvdose
    Jul 20, 2022 at 12:19
  • 1
    $\begingroup$ One could also mention Erdös's result (link to original Hungarian paper) that 50% of primes have $2$ as their least (positive) quadratic nonresidue, 25% of primes have $3$, 12.5% have $5$, 6.25% have $7$, and so on. The same result would hold if we considered the greatest negative quadratic nonresidue. $\endgroup$ Jul 21, 2022 at 3: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.