# Find $r$ from $x_1\equiv r^a \pmod{p}, x_2\equiv r^b \pmod{p}$ and gcd$(b, p-1)=1$

$r$ is a primitive root for the prime $p$

$x_1\equiv r^a \pmod{p}$

$x_2\equiv r^b \pmod{p}$

If $gcd(b, p-1)=1$, how can I determine $r$ if $p$, $x_2$, and $b$ are known?

-
What is the use of $x_1$ then? – Aryabhata Oct 16 '10 at 2:55
@Moron: To amuse your friends and confound your enemies? – Arturo Magidin Oct 16 '10 at 3:03
That's the problem as it was assigned :) – Steven Oct 16 '10 at 3:25

HINT: If gcd$(b,p-1)=1$, then we can write $1 = tb + s(p-1)$. So $tb\equiv 1 \pmod{p-1}$.

-
So I guess I find $t$, then I take ${x_2}^t$? – Steven Oct 16 '10 at 3:56
@Steven: I would recommend thinking about it rather than guessing... What will that achieve? If the answer is 'nothing', then don't do it. If the answer begin with 'aha!...', then go for it. But think about where you are trying to go and whether this takes you there. – Arturo Magidin Oct 16 '10 at 5:19
Alright I'm stuck. Any other hints? – Steven Oct 16 '10 at 16:07
What happens if you take $x_2^t$? Since $x_2\equiv r^b\pmod{p}$, the result will be congruent to..., which in turn is congruent to... (why?). – Arturo Magidin Oct 16 '10 at 16:08

HINT $\$The isomorphism $\rm n\to r^n\:$ from the additive group $\rm \mathbb Z/(p-1)$ to the multiplicative group $\rm \mathbb Z/p^*\:$

maps $\rm\ b\to x,\ 2b\to x^2,\: \cdots\:,\: nb\to x^n$. You seek $\rm 1\to r\$ so you need $\rm\ nb\equiv 1\$ so $\rm\ n\equiv \:\ldots$

-
I think $n=1/b$? Then I take ${x_2}^{1/b}\pmod{p}$? – Steven Oct 16 '10 at 3:51
Yes, $1/b \in \mathbb Z/(p-1)$, i.e. $1/b$ mod $p-1$. Note how understanding the isomorphism makes the way to the solution obvious. – Bill Dubuque Oct 16 '10 at 3:54