Smallest Mazur's good prime

Question

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

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.