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.

If $p$ is a prime and $a,b$ are integers not divisible by $p$ such that $a^x \equiv b \pmod p$ with $0 ≤ x < o_p(a)$, then we define $x = L_a(b)$ and say $x$ is the discrete logarithm of $b$ with respect to $a$ (of course the discrete log also depends on $p$). Suppose $o_p(a)=r$. Prove that for any integer $b$ not divisible by $p$, the discrete log $L_a(b)$ exists if and only if $b^r \equiv 1 \pmod p$.

[ $o_p(a)$ is the (multiplicative) order or $a$ modulo $p$. ]

share|improve this question
    
yea that was a typo. thanks! –  Gabe Apr 16 '13 at 14:48
add comment

2 Answers 2

Observe the definition of Discrete Logarithm

$ord_pa=r\iff a^r\equiv1\pmod p$

$b^r\equiv(a^x)^r\equiv (a^r)^x\equiv 1^x\equiv1\pmod p$

Conversely, if $b^r\equiv1\pmod p\implies (a^x)^r\equiv1\implies a^{rx}\equiv1$

As $a,b$ are arbitrary so will be $x$ then $a^{rx}\equiv1\pmod p$ will be true iff $r=p-1$

share|improve this answer
    
No, the first $\iff$ is only true of $a$ is a primitive root, modulo $p$. For example, if $p=13,a=5,b=8$, then $a^x\equiv b\pmod p\iff x\equiv 3\pmod 4$ –  Thomas Andrews Apr 16 '13 at 15:08
    
@ThomasAndrews, the concept of discrete logarithm is based on primitive root , right? –  lab bhattacharjee Apr 16 '13 at 15:10
    
That's not how the OP defined it - it was defined over arbitrary $a$, otherwise there would be no need for $r$ - $r=p-1$ when $a$ is a primitive root. –  Thomas Andrews Apr 16 '13 at 15:11
    
The point of the "conversely" is to show that such an $x$ exists. You've just assumed it. –  Thomas Andrews Apr 16 '13 at 15:31
add comment

Hint: Consider the roots of the polynomial $f(y)=y^r-1$ modulo $p$.

Detail: If $a^x=b$ then $b^r-1\equiv a^{xr}-1 \equiv 0\pmod p$.

On the other hand, $1,a,a^2,\dots,a^{r-1}$ are $r$ distinct roots of $f(y)$ modulo $p$. Can there be more than $r$ distinct roots of $f$?

share|improve this answer
add comment

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.