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.

$\endgroup$
6
  • 2
    $\begingroup$ 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? $\endgroup$ Commented May 25, 2011 at 17:24
  • $\begingroup$ I think the OP means: which $n$ are non-trivial powers mod $p$? $\endgroup$
    – lhf
    Commented May 25, 2011 at 17:29
  • $\begingroup$ @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}$ $\endgroup$ Commented May 25, 2011 at 17:37
  • $\begingroup$ @Thomas, the way I read the question, you're free to choose $k$. $\endgroup$
    – lhf
    Commented May 25, 2011 at 17:41
  • 2
    $\begingroup$ You really want to either also fix $x$ or also fix $k$ to get an interesting problem. $\endgroup$ Commented May 25, 2011 at 17:51

2 Answers 2

2
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – bzc
    Commented May 25, 2011 at 17:52
  • $\begingroup$ @Brandon, thanks. I knew I was missing this case! But 2 is a cube mod 3, isn't it, by Fermat. $\endgroup$
    – lhf
    Commented May 25, 2011 at 17:54
  • $\begingroup$ 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. $\endgroup$
    – Charles
    Commented May 25, 2011 at 19:07
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Charles
    Commented May 25, 2011 at 19:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .