Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

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

share|improve this answer
    
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$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.