Question about the proof of the change of base formula for the discrete logarithm 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  $$
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 &amp;= g^\frac{(q-1)\cdot t}{k} &amp;&amp; ;\text{replace } \lambda \text { with } \frac{(q-1)\cdot t}{k}\\
\Gamma^{k} &amp;= g^{(q-1)\cdot t}  &amp;&amp; ;\text{take } kth \text{ power}\\
\Gamma^{k} &amp;= 1^t \\
\end{align}
Clearly, $k &lt; 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.