# Smallest prime that is a quadratic residue modulo a fixed prime

Let $P$ denote the set of positive primes and let $p$ be a fixed prime. Then define $q_{p}:=\min{q\in P:p<q,(q/p)=1}$ where $(⋅/p)$ is the Legendre symbol. So for instance $q_{3}=7$, $q_{3}=7$, and $q_{5} = 11$. Is there anything known about $q_{p}$ and specifically are there known bounds on $q_{p}$ as a function of $p$? I am ultimately interested in investigating $\inf\{q_{p}/p:p\in P \}$.

I understand there are some things known about the smallest prime that is a quadratic residue modulo a prime, i.e. least quadratic residue and nonresidue, but this seems to be a different, albeit related, question.

• Based on recent results concerning bounded gaps between primes, I would expect the prime pair (p, p+4k^2) to occur infinitely often for a value of k less than 10, and existing technology might show the existence of a k less than some effective constant C. So your infimum should be 1. Gerhard "Paging Any Nearby Number Theorists" Paseman, 2017.02.28. – Gerhard Paseman Feb 28 '17 at 21:10
• @GHfromMO, yes the poster is looking for $q_p$ given $p$. I suspect eventually $q_p \lt Cp$ to hold for a given $C \gt 1$ and all but finitely many primes $p$, but I am too ignorant to provide a heuristic to that. The poster said that the infimum of $q_p/p$ as $p$ ranges over primes is of interest. I think current technology can show that infimum is 1. What do you think? Gerhard "Has Faith In Current Technology" Paseman, 2017.02.28. – Gerhard Paseman Feb 28 '17 at 21:40
• @GerhardPaseman: I missed the OP's ultimate interest. Once I realized that, I deleted my comment. – GH from MO Feb 28 '17 at 21:42

Elaborating on Gerhard Paseman's idea, under a generalized Elliott-Halberstam conjecture the Polymath8b paper shows that there are infinitely many $n$'s such that at least two elements of $\{n,n+36,n+100\}$ are primes. In other words, assuming this conjecture, there are infinitely many prime pairs $(p,q)$ such that $q-p\in\{36,64,100\}$ is a bounded square, and hence $$\inf\{q/p:\ \text{q>p are primes such that (q/p)=1}\}=1.$$
• Thank you for following up. Using Nicely's gap tables, there is a prime P of 27 decimal digits with P + 44*44 also prime, so unconditionally the infimum is within $10^{-20}$ of 1. Hopefully the poster can use this information. Gerhard "Thank You For Your Expertise" Paseman, 2017.02.28. – Gerhard Paseman Feb 28 '17 at 22:52
From this discussion least prime in a arithmetic progression after considering only $q \equiv 1 \mod p$ we can trivially get bounds $q_p \leq cp^{5.2}$ and, under GRH, $q_p\leq p(\log p)^2$.
• Under GRH one can even get $q_p = O(\log(p)^2)$ by applying chebotarev density to ${\bf Q}(\sqrt{\pm p})$. – M.D. Mar 27 at 22:57