Primes for which $x^k\equiv n\pmod p$ is solvable: the fixed version

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.

Solution 1:

If $p|n$, we always have solution.

So assume $p$ does not divide $n$.

In this case, we have a solution to $x^k = n \pmod p$ if and only if $n^{\frac{p-1}{k_p}}\equiv 1 \pmod p$ where $k_p = \gcd(k,p-1)$.

Proof: Choose $u,v$ so that $k_p = (p-1)u + kv$.

If $x^k = n$, then $$n^{\frac{p-1}{k_p}} \equiv x^{(p-1)\frac{k}{k_p}} \equiv 1 \pmod p$$

On the other hand, if $n^{\frac{p-1}{k_p}} \equiv 1 \pmod p$, then $n \equiv x_0^{k_p}$ for some $x_0$. But: $$n\equiv x_0 ^{p_k} = x_0^{(p-1)u + kv} \equiv (x_0^v)^k$$ So $x=x_0^v$ is a solution.

This is a generalization of the theorem that (when $p$ is odd and $(n,p)=1$), $n$ is a square modulo $p$ if and only if $n^{\frac{p-1}2} \equiv 1 \pmod p$

There have been lots of attempts to generalize quadratic reciprocity to other powers, but I don't know much about the results - I don't know if they'd be useful for real computation.