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}$$
Power equivalence in a prime modulus
2
$\begingroup$
elementary-number-theory
prime-numbers
modular-arithmetic
-
3Why did you delete this question then post it again under a different name? – 2011-05-11
-
1And please don't give orders. If you have a question, **ask**, don't order us to "show" something. – 2011-05-11
2 Answers
1
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$.
-
1@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. – 2011-05-11
-
0@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. – 2011-05-11
-
0@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." – 2011-05-11
-
0@user6312, you are correct the intent was to say "show there exists", and not assume it. – 2011-05-11
-
0@lhf, Still somewhat confused, not seeing how the intitial congruence to 1 mod p is used? – 2011-05-11
-
0@user10766: you use it to prove that $c$ divides $k$. I've edited my answer. – 2011-05-11
-
0@lhf, I see it now, thanks! – 2011-05-11
1
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$