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$ – Sungjin Kim Jul 14 '16 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 '16 at 5:35

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.$$


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.