Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
yea that was a typo. thanks! – Gabe Apr 16 '13 at 14:48

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|cite|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

Your Answer


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.