For fixed $n$ and $k$, how can I characterize the primes $p$ such that $x^k\equiv n\pmod p$?
Less important to me: Is there a similar characterization for composite moduli? Assume the factorization is known.
Example: the primes for which $x^4\equiv21$ is solvable are 2, 3, 5, 7, 17, 43, 47, 59, 67, 79, 83, 109, 127, 131, 151, 163, ...; is there an easier way to express this sequence?
This is the corrected version of this question where I clearly lost my train of thought while posting.