# 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.

-
Any condition on $k$? If you can choose $k=1$, or more generally $k\equiv 1 \pmod {p-1}$, then this always has a solution with $x=n$. Or is $x$ fixed? –  Thomas Andrews May 25 '11 at 17:24
I think the OP means: which $n$ are non-trivial powers mod $p$? –  lhf May 25 '11 at 17:29
@lhf: So we really need to restrict $k$ to have a common factor with $p-1$? If $\gcd(k,p-1)=1$, then we can find an $l$ so that $kl\equiv 1 \pmod {p-1}$ and if $x=n^l$, then $x^k = n^{kl} \equiv n \pmod {p}$ –  Thomas Andrews May 25 '11 at 17:37
@Thomas, the way I read the question, you're free to choose $k$. –  lhf May 25 '11 at 17:41
You really want to either also fix $x$ or also fix $k$ to get an interesting problem. –  Qiaochu Yuan May 25 '11 at 17:51

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$.)

-
The only exception is 2 mod 3. Since 2 is the only primitive root mod 3, it is not a non-trivial power mod 3. –  Brandon Carter May 25 '11 at 17:52
@Brandon, thanks. I knew I was missing this case! But 2 is a cube mod 3, isn't it, by Fermat. –  lhf May 25 '11 at 17:54
This is the correct answer to the question I asked, but unfortunately not to the question I intended! I will accept and post a new question. –  Charles May 25 '11 at 19:07

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.)

-
Thanks, +1. I had meant to ask a slightly different -- and more interesting -- question, but an apparent lack of coffee left my question in the present state. –  Charles May 25 '11 at 19:08