Primes for which $x^k \equiv n \pmod{p}$ is solvable For a fixed $n$, how can I characterize the primes $p$ such that there is a $k$ with $x^k\equiv n\pmod p$?
Edit: This wasn't actually what I meant... the question I intended is here.
 A: Every $n$ is a non-trivial power mod $p$ for every $p$. Indeed, by Fermat's little theorem, every $n$ is a $p$-th power mod $p$ for every $p$.
If you insist on $1<k<p$, then the following argument works (with exactly one exception noted below): If $p$ divides $n$, you can take $x=0$ and any $k$. Now assume that $p$ does not divide $n$. Take $g$ a primitive root mod $p$ that is not congruent to $n$ mod $p$.  You can choose $g$ like that because there are $\phi(p-1)$ primitive roots mod $p$. Then $n$ is a non-trivial power of $g$ mod $p$. The exception is 2, which is not a small power mod 3. (The argument above fails because $\phi(3-1)=1$.)
A: To repeat from my comments above, if we allow $k$ such that $\gcd(k,p-1)=1$, then we can find an $l$ so that $lk\equiv 1 \pmod {p-1}$, and then if $x=n^l$, then $x^k = n^{lk}\equiv n \pmod {p}$
So if we allow such $k$, then it is true for all $p$.
On the other hand, if we restrict to $k$ such that $\gcd(k,p-1)>1$, then we cannot find a solution if $n$ is of order $p-1$ in the multiplicative group modulo $p$.  It is a "hard problem" to deterime if $n$ is a generator modulo a particular prime $p$.  It is not even fully resolved yet whether, if $n$ is not a square and $n\neq -1$, there is always a prime $p$ such that $n$ is a generator $\mod p$, which I recently learned is a conjecture of Artin.  (This is mostly resolved - it is know that there are at most two counter-examples $n$, and any counter-example has to be prime.)
