Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$$

share|cite|improve this question
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
up vote 1 down vote accepted

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

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

share|cite|improve this answer

Your Answer


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.