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


1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$ Commented Jan 28, 2019 at 9:50
  • 1
    $\begingroup$ 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". $\endgroup$ Commented Jan 28, 2019 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.