Question about the proof of the change of base formula for the discrete logarithm
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.