$\alpha^t$ primitive $\Leftrightarrow \gcd (t,q-1)$ 
Consider the finite field $\mathbb{F}_q^n$ and let $\alpha$ be a primitive element of $\mathbb{F}_q$. Show that $\alpha^t$ is a primitive element of $\mathbb{F}_q$ if and only if $\gcd(t, q−1)=1$.

$"\Rightarrow"$: Let $\alpha^t$ be a primitive element, we also have that $\alpha^{q-1}=1$. Suppose $\exists d>1$ such that $d=\gcd(t,q-1)$, then $d|k$ and $d|q-1$. Moreover we have that $(\alpha^t)^\frac{q-1}{d}$
contradicting the fact that $\alpha$ has order $q-1$. Hence $\gcd(t,q-1)=1$.
$"\Leftarrow"$: Suppose $\gcd(t,q-1)=1$. Then by Bezout's lemma $\exists a,b\in\mathbb{Z}$ such that $1=at+(q-1)b \Leftrightarrow \alpha^1=\alpha^{at}\alpha^{(q-1)b}=\alpha^{at}$
From the last step I don't get how should I procced to obtain that $\alpha^t$ is primitive, any suggestion?
 A: $\newcommand{ord}{\sf{ord}}$
The proof of the result you wish to prove is a little trickier than might be expected.
Let $\alpha$ denote an element of order $n$ which we will denote as $\ord(\alpha) = n$. Suppose that  $\beta = \alpha^k$ where $1 \leq k < n$.
Since both $\dfrac{n}{\gcd(n,k)}$ and $\dfrac{k}{\gcd(n,k)}$ are
integers,
\begin{align}
{\large{\beta}}^{\dfrac{n}{\gcd(n,k)}} &= {\large{(\alpha^k)}}^{\dfrac{n}{\gcd(n,k)}}\\ 
&= {\large{(\alpha)}}^{\dfrac{nk}{\gcd(n,k)}}\\
&= {\large{(\alpha^n)}}^{\dfrac{k}{\gcd(n,k)}}\\ 
&= {\large{1}}^{\dfrac{k}{\gcd(n,k)}}\\
&= 1
\end{align}
which shows that $\dfrac{n}{\gcd(n,k)}$ is a multiple of $\ord(\beta)$.
On the other hand, $\beta^{\ord(\beta)} = 1 = \alpha^{k\cdot\ord(\beta)}$
and so $\ord(\beta)$ is the smallest positive integer such that
$k\cdot\ord(\beta)$ is a multiple of $n$.  But, $k\cdot\ord(\beta)$
is also a multiple of $k$, and thus is a multiple of the least
common multiple $\operatorname{lcm}(n,k)$ of $n$ and $k$.  Therefore, $\ord(\beta)$
is the smallest positive integer such that
$k\cdot\ord(\beta)$ is a multiple of
$\operatorname{lcm}(n,k) = \dfrac{nk}{\gcd(n,k)} = k\cdot\dfrac{n}{\gcd(n,k)}$,
that is, $\ord(\beta)$ is the smallest integer that is a multiple of $\dfrac{n}{\gcd(n,k)}$
which of course is $\dfrac{n}{\gcd(n,k)}$ itself.
It follows that
$$\ord(\beta) = \ord(\alpha^k) = \frac{n}{\gcd(n,k)} = \frac{\ord(\alpha)}{\gcd(\ord(\alpha),k)}.$$
In particular, if $n$ and $k$ are relatively prime, then $\ord(\beta) = \ord(\alpha^k) = \ord(\alpha) = n$. Thus, if $\alpha$ is an element of order $q-1$ in $\mathbb F_q$, that is, is a primitive element of $\mathbb F_q$, then $\alpha^k$ is a primitive element of $\mathbb F_q$ exactly when $\gcd(k,q-1)=1$.
