# Chowla's Construction of prime having least quadratic non-residue $\gg \log p$

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.

• I found this paper by Graham and Ringrose which 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$. But still now my question is does it removes the possibility of proving n(p) = O(\log p \log \log \log p) – xyz Jul 14 '16 at 18:19
• Under GRH $n(p) = O((\log p)^2)$ and, conjecturally $n(p) = O((\log p)^{1+\epsilon}), \forall \epsilon > 0$. – Felipe Voloch Jul 14 '16 at 18:31
• @FelipeVoloch can you give any reference for the conjecture $n(p)=O((\log p)^{1+\epsilon})$. – xyz Jul 14 '16 at 19:10
• There is a somewhat vague discussion in Bach and Sorensen, Math Comp 65 (1996) bottom of pg 1718. I've seen it in other places too, but I don't recall a specific reference. – Felipe Voloch Jul 14 '16 at 20:31
• Montgomery showed that conditional on GRH there are infinitely many primes $p$ such that $n(p)\gg \log p \log \log p$. – Thomas Bloom Jul 16 '16 at 15:38