Skip to main content
2 of 2
fixed typo
Igor Rivin
  • 96.4k
  • 11
  • 153
  • 366

This is an elaboration on Gerry Myerson's comment. By Chebotarev's (or Frobenius') density theorem, there is a positive proportion of primes for which $x^n-q$ has no linear factor (assuming $q$ is such that this is irreducible over $\mathbb{Q}).$ In fact, this proportion is not too hard to estimate, but this will lead us too far afield. So, systematic search succeeds, and usually pretty quickly (for each $p$ use Berlekamp's algorithm, or some variant thereof, to factor).

Igor Rivin
  • 96.4k
  • 11
  • 153
  • 366