# Power equivalence in a prime modulus

Given, $p,q$ primes, $x$, $c$, $(p-1)/c$ integers and $$x^{(p-1)/c} \equiv 1\pmod{p}$$ how can I show there exists a $q$ such that $$q^c \equiv x\pmod{p}$$

-
Why did you delete this question then post it again under a different name? –  quanta May 11 '11 at 13:04
And please don't give orders. If you have a question, ask, don't order us to "show" something. –  Arturo Magidin May 11 '11 at 15:37

If you know about primitive roots, then write $x=g^k$ for a primitive root $g$. Then take $q=g^t$, where $t=k/c$. You should prove that $c$ divides $k$.

Here are the details. Let $m=(p-1)/c$. Then $1 \equiv x^m \equiv g^{km}$ and so $p-1$ divides $km$. Write $(p-1)t=km=k(p-1)/c$. Then $t=k/c$.

-
@lhf: The question is not completely clear on this, but it looks as if it is specified that $q$ must be prime. If that is the case, after noting that $g^t$ satisfies the congruence, one could appeal to Dirichlet's Theorem on primes in arithmetic progressions. –  André Nicolas May 11 '11 at 13:15
@user6312, it did not seem to me that $q$ was to be a prime but it's nice to know it can be chosen a prime. –  lhf May 11 '11 at 13:18
@user10766: Perhaps you can clarify the intent. In any case, $q$ should not have been mentioned in the first line, it is not given. Instead, if you wanted $q$ to be prime, the line below the first displayed formula should have read "show that there exists a prime $q$ such that." –  André Nicolas May 11 '11 at 13:27
@user6312, you are correct the intent was to say "show there exists", and not assume it. –  user10766 May 11 '11 at 13:50
@lhf, Still somewhat confused, not seeing how the intitial congruence to 1 mod p is used? –  user10766 May 11 '11 at 15:16

Noting $r=(p-1)/c$, so that $x^r = 1$ and p-1 = rc, look at the roots of $X^p - X = (X^{p-1}-1)X$

$= ((X^c)^r - x^r)X = (X^c - x)(X^{c(r-1)} + X^{c(r-2)}x + \ldots + X^cx^{r-2} + x^{r-1})X$

-