1
$\begingroup$

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

  • 0
    What is the use of $x_1$ then?2010-10-16
  • 0
    @Moron: To amuse your friends and confound your enemies?2010-10-16
  • 0
    That's the problem as it was assigned :)2010-10-16

2 Answers 2

5

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

  • 0
    So I guess I find $t$, then I take ${x_2}^t$?2010-10-16
  • 0
    @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.2010-10-16
  • 0
    Alright I'm stuck. Any other hints?2010-10-16
  • 0
    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?).2010-10-16
2

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$

  • 0
    I think $n=1/b$? Then I take ${x_2}^{1/b}\pmod{p}$?2010-10-16
  • 0
    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.2010-10-16