Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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? –  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
2  
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

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
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. –  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.)

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.