3
$\begingroup$

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.

  • 2
    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?2011-05-25
  • 0
    I think the OP means: which $n$ are non-trivial powers mod $p$?2011-05-25
  • 0
    @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}$2011-05-25
  • 0
    @Thomas, the way I read the question, you're free to choose $k$.2011-05-25
  • 2
    You really want to either also fix $x$ or also fix $k$ to get an interesting problem.2011-05-25
  • 0
    @Qiaochu Yuan: I had intended to do so but got mixed up in typing it out. I will repost the correct version.2011-05-25

2 Answers 2

2

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

  • 2
    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.2011-05-25
  • 0
    @Brandon, thanks. I knew I was missing this case! But 2 is a cube mod 3, isn't it, by Fermat.2011-05-25
  • 0
    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.2011-05-25
1

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

  • 0
    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.2011-05-25