# Smallest Mazur's good prime

Let $$p$$ and $$\ell$$ be primes $$\geq 5$$ such that $$\ell$$ divides $$p-1$$. Following Mazur, we say that a prime $$q$$ is a $$\textit{good prime}$$ if $$\ell$$ does not divide $$q-1$$ and $$q$$ is not a $$\ell$$th power modulo $$p$$. There exists (infinitely many) good primes by Dirichlet theorem. Note that $$\ell$$ may a good prime (we don't exclude this possibility).

Which upper bound can we give for the smallest good prime $$q$$, in terms of $$\ell$$ and $$p$$? I would be particularly happy if an upper bound in $$o(p)$$ could be proved.

Just for recalling the motivation behind this definition, Mazur proved that $$q$$ is a good prime if and only if the Hecke operator $$T_q-q-1$$ generates locally the $$\ell$$-Eisenstein ideal of level $$\Gamma_0(p)$$.

The good primes (not counting $$\ell$$ itself, if that's allowed to be a good prime) are precisely those that lie both in one of $$\ell-2$$ reduced residue classes (mod $$\ell$$) and one of $$(p-1)(1-1/\ell)$$ reduced residue classes (mod $$p$$) (in particular, their relative density in the primes is $$1-2/\ell$$). So the good primes are those that avoid $$(\ell-1)(p-1)2/\ell$$ of the residue classes (mod $$p\ell$$).
By the Brun–Titchmarsh theorem, the number of primes up to $$x$$ in any one of those bad residue classes (mod $$p\ell$$) is at most $$2x/\{ \phi(p\ell)\log(x/p\ell) \}$$; thus together, those bad residue classes contain at most $$4x/\{ \ell\log(x/p\ell) \}$$ primes up to $$x$$. On the other hand, the overall number of primes up to $$x$$ is $$\gtrsim x/\log x$$ by the prime number theorem. Therefore there must certainly be good primes less than $$x$$ as soon as $$x/\log x$$ is significantly larger than $$4x/\{ \ell\log(x/p\ell) \}$$, or equivalently as soon as $$\log(x/p\ell)$$ is significantly larger than $$(4/\ell)\log x$$.
In short, solving for $$x$$, this argument shows that there exists a good prime that is $$\ll_\varepsilon (p\ell)^{\ell/(\ell-4)+\varepsilon}$$, which can be simplified to $$\ll_\varepsilon p^{\ell/(\ell-4)+\varepsilon}\ell^{1+\varepsilon}$$.
I wouldn't be surprised if a character-sum-based argument could achieve a much better result, perhaps even $$\ll_\varepsilon p^{1/4\sqrt e+\varepsilon}$$. One nice thing about your situation is that you're looking at the intersection of two sets of primes each with a relative density in the primes, and those two relative densities add to a number greater than $$1$$; therefore you can simply establish a good lower bound for the number of such primes separately, and conclude that a good prime exists simply by intersecting the two large sets.
• Thanks! I was looking for a more precise bound, at most linear in $p$. For instance, if $p\geq 37$ then I expect that the smallest good prime is $\leq \frac{p-1}{12}$ (for any choice of $\ell$). Do you have a reference for the kind of arguments you alluded to at the end of your answer? Jan 28, 2019 at 9:50
• You can search the literature for "least quadratic nonresidue" (the $\ell=2$ case, which is a good model for the structure of such arguments) and then "least character nonresidue". Jan 28, 2019 at 17:57