Question about the proof of the change of base formula for the discrete logarithm

Question

I was looking at the proof of a change of base formula for the discrete logarithm in this paper (page 6, 4th bullet indent).

In the intruduction, the paper states:

Let $F_q$ be a finite field of order $q$, where $q=p^n$ ($p$ prime), and let $F_q^* = F_q -\{0\}$. Given $g$, a primitive element of $F_q$, and an arbitrary $y\in F_q^*$, the discrete logarithm of $y$ base $g$ is defined as $$ \log_g y = x \iff g^x=y \text{ in } F_q \text{ and } 0\leq x\leq q-2.$$

And then the author of the paper proves the change of base formula for the discrete logarithm:

Suppose $\Gamma$ is another primitive element of $F_q$ and we know $\log_g \Gamma = \gamma$.
$\Gamma$ and $g$ both primitive $\implies \gcd(\gamma , q-1)=1$
$\implies \exists \overline\gamma$ such that $\gamma \overline\gamma \equiv 1 \pmod{q-1} \implies g=\Gamma ^{\overline\gamma}$ in $F_q$.
Therefore $\log_g y = x \iff y = g^x = \Gamma ^{\overline\gamma x}$ in $F_q \iff \log_\Gamma y \equiv \overline\gamma x \pmod{q-1}$.
Multiplying the last congruence by $\gamma$ gives $\log_g y \equiv \log_g \Gamma \cdot \log_\Gamma y \pmod{q-1}$.

My question is, why does the following holds (from the beginning of the proof): $$ g \text{ and } \Gamma \text{ both primitive element of } F_q \text{ and } \log_g \Gamma =\gamma \implies \gcd(\gamma , q-1)=1 $$

Answer 1

Prove that:

$$g \text{ and } \Gamma \text{ both primitive element of } F_q^* \text{ and } \log_g \Gamma =\gamma \implies \gcd(\gamma , q-1)=1$$

A primitive element in finite field means it is a generator, i.e. $\langle g\rangle = GF(q) = F_q^* $.

Let $g \text{ and } \Gamma$ be both primitive elements of $ GF(q)$. By using the contrapositive we will reach the opposite.

Assume that $\gcd(\gamma , q-1) = d \neq 1$ where $\log_g \Gamma =\gamma$.

We can say that $\gamma = d \cdot k$ for some non-negative integer $k$ and $q-1 = d \cdot t$. $(q-1) \cdot t = \lambda \cdot k$. Therefore; $\lambda = \frac{(q-1)\cdot t}{k}$

$\log_g \Gamma =\gamma$ means $\Gamma = g^\gamma$ now,

\begin{align} \Gamma &= g^\frac{(q-1)\cdot t}{k} && ;\text{replace } \lambda \text { with } \frac{(q-1)\cdot t}{k}\\ \Gamma^{k} &= g^{(q-1)\cdot t} && ;\text{take } kth \text{ power}\\ \Gamma^{k} &= 1^t \\ \end{align}

Clearly, $k < q-1$ but we found a power $k$ of generator $\Gamma$ such that $\Gamma^{k} = 1$ this mean $\Gamma$ is not a primitive element. This proves the statement.

Answer 2

Let $a$ be an element of a group and $o(a)$ be the order of $a$ in group. It is an easy to prove problem that $o(a^r) = \frac{o(a)}{gcd(o(a),r)}$. Therfore $a$ and $a^r$ generate same group iff $gcd(o(a),r)=1$. Now you can set the group by $F^{\ast}$ with $q-1$ element and $a$ a generator of it.