This paper by NC Ankeny mentions that " S. Chowla has proved that there exist infinitely many primes $k$ where the first $c_1\log k$ residues $(\bmod k)$ are all quadratic residues".

I recently found a proof of this here.

The proof constructs such primes using this idea:

  1. Consider numbers which satisfies these condition : $n=1\bmod 8$ and $n=1\bmod r_i$ where $r_i$ are first consecutive odd primes less than $y$.
  2. Let $R:= 8\prod r_i $ , clearly $n=1\bmod R$ by Chinese remainder theorem.
  3. By Linniks there exist a prime $p$ in this arithmetic progression $\{ 1+rk_j\}$ such that $p= \mathcal{O}(R^6)$.
  4. Note that for this prime all numbers less than $y$ are quadratic residue, since p $\equiv 1 \bmod 8 \implies \big(\frac{a}{p} \big) = \big( \frac{p}{a} \big) $.
  5. By prime number theorem it is easy to see that y = $O(\log p)$

But this analysis clearly doest rule out the possibility of having least quadratic non-residue $O(\log p)$ . Infact if we write all the constants and work it out than it doesn't even rule out the possibility of least quadratic non residue less than $10\log p$.

I want to know is this just what Chowla proved or there is a better argument for this. Any refrence for the same would be of great help.

  • 1
    $\begingroup$ Graham and Ringrose proved that there are infinitely many primes $p$ such that the least quadratic nonresidue $n_p$ satisfies $n_p \gg \log p \log\log\log p$. The paper can be found here. $\endgroup$ Jul 14, 2016 at 16:13
  • $\begingroup$ @i707107 your comment gives the answer to my question. kindly write it as an answer so I can mark it. $\endgroup$
    – xyz
    Jul 15, 2016 at 5:35

1 Answer 1


Since I am writing as an answer, I will put more information than the comment.

Graham and Ringrose proved that:

There are infinitely many primes $p$ such that $$ n_p\gg \log p \log\log\log p.$$

Montgomery proved that:

If the Generalized Riemann Hypothesis(GRH) is true, then there are infinitely many primes $p$ such that $$n_p\gg \log p \log\log p.$$


You must log in to answer this question.

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