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