mjhjmtu

Let $p$ and $ell$ be primes $geq 5$ such that $ell$ divides $p-1$. Following Mazur, we say that a prime $q$ is a $textitgood 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 $pell$).

By the Brun–Titchmarsh theorem, the number of primes up to $x$ in any one of those bad residue classes (mod $pell$) is at most $2x/ phi(pell)log(x/pell) $; thus together, those bad residue classes contain at most $4x/ elllog(x/pell) $ 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/ elllog(x/pell) $, or equivalently as soon as $log(x/pell)$ 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 (pell)^ell/(ell-4)+varepsilon$, which can be simplified to $ll_varepsilon p^ell/(ell-4)+varepsilonell^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/4sqrt 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.