Discrete Logarithm Problem

Question

Question: Discrete Logarithm Problem: Let $g$ be a primitive root for $F_{p}$. Suppose that $x = a$ and $x = b$ are both integer solutions to the congruence $g^{x} \equiv h \pmod{p}$. Prove that $a \equiv b\pmod{p-1}$.

So far, I have the following as my proof:

Proof: Let $g$ be a primitive root for $F_{p}$. Suppose that $x = a$ and $x = b$ are both integer solutions to the congruence $g^{x} \equiv h\pmod{p}$. Then, $g^{a} \equiv h\pmod{p}$ and $g^{b} \equiv h\pmod{p} \rightarrow g^{a} - h = kp$ and $g^{b} - h = kp$, for some $k \in Z$. By substitution, we have $g^{a} = g^{b} \rightarrow a \log (g) = b \log (g) \rightarrow a = b$.

It doesn't seem as if I'm going in the right direction, but I'm stumped on what other routine I can take. Any ideas?

Answer 1

The definition of a primitive root (that I learned first anyway) is that $g$ is a generator in $\pmod p$ if and only if the function $f$ :

$$f(x) \equiv g^x \pmod p$$

is a bijection over the domain $D$, for $D=\{1, 2, \dots p-1\}$. A bijection is a function that is both

• onto, that is it has every value of the domain in its output, and
• invertible, that is it doesn't output a value into the domain more than once

Your question comes down to proving that

$$g^{p - 1} \equiv 1 \pmod p \tag{B}$$

To prove it, assume the opposite for the sake of contradiction. Then $f(p-1) \ne 1$. Then because $f$ is onto (by the definition of a generator), there must be some $y$ such that $$f(y) = 1$$

So $f(y+1) = g$. But we know that $f(1) = g$ from the definition of $f$. But this contradicts the assumption that $f$ is invertible since it outputs $g$ twice. So by contradiction $$f(p-1) \equiv 1$$ $$g^{p-1} \equiv 1 \pmod p$$

Can you now use (B) to fill in the rest of the details to establish that $g^a \equiv g^b \pmod p \quad \rightarrow \quad a \equiv b \pmod {p-1}$ ?

Hint 1:

This is the same as $\forall k ~~ g^{a + (p-1)k} \equiv g^{a} \pmod p$

Hint 2:

Which is the same as $\forall k ~~ g^{a}(g^{p-1})^k \equiv g^{a} \pmod p$