2
$\begingroup$

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

  • 1
    And please don't give orders. If you have a question, **ask**, don't order us to "show" something.2011-05-11

2 Answers 2

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$