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. 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), 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, hence also that $$a(n). 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.
• 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 ? Jul 20, 2022 at 12:10
• 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. Jul 21, 2022 at 3:36