[proofplan]
We reduce the order computation to a divisibility problem in $\mathbb{Z}$. Since $g$ generates the finite group $G$ of order $n$, the element $g$ itself has order $n$. Writing $d=\gcd(n,k)$, $n=d n_1$, and $k=d k_1$, we show that a positive integer $m$ satisfies $(g^k)^m=e$ exactly when $n_1$ divides $m$. Therefore the least positive such $m$ is $n_1=n/\gcd(n,k)$.
[/proofplan]
[step:Identify the order of the chosen generator]
Let $e$ denote the identity element of $G$. Since $G=\langle g\rangle$ and $|G|=n$, the order of the generated subgroup is $n$. By [citetheorem:8236], applied to the element $g \in G$, we have
\begin{align*}
\operatorname{ord}(g)=|\langle g\rangle|=|G|=n.
\end{align*}
In particular, $n \in \mathbb{N}$ and, for every integer $r \in \mathbb{Z}$,
\begin{align*}
g^r=e \iff n \mid r.
\end{align*}
Indeed, if $r=qn+s$ with $q \in \mathbb{Z}$ and $s \in \{0,\dots,n-1\}$, then $g^r=g^s$ because $g^n=e$. If $g^r=e$, then $g^s=e$, and the minimality of $\operatorname{ord}(g)=n$ forces $s=0$, so $n \mid r$. The reverse implication follows directly from $g^n=e$.
[/step]
[step:Reduce the vanishing of $(g^k)^m$ to an integer divisibility condition]
Let $d=\gcd(n,k)$, where $d$ is the positive greatest common divisor. Define $n_1 \in \mathbb{N}$ and $k_1 \in \mathbb{Z}$ by
\begin{align*}
n_1=\frac{n}{d}
\end{align*}
and
\begin{align*}
k_1=\frac{k}{d}.
\end{align*}
Then $n=d n_1$, $k=d k_1$, and $\gcd(n_1,k_1)=1$.
For every $m \in \mathbb{N}$, the laws of integer powers in a group give
\begin{align*}
(g^k)^m=g^{km}.
\end{align*}
Using the characterization from the previous step,
\begin{align*}
(g^k)^m=e \iff n \mid km.
\end{align*}
Substituting $n=d n_1$ and $k=d k_1$, this becomes
\begin{align*}
d n_1 \mid d k_1 m \iff n_1 \mid k_1 m.
\end{align*}
Since $\gcd(n_1,k_1)=1$, Bezout's identity gives integers $a,b \in \mathbb{Z}$ such that $a n_1+b k_1=1$. If $n_1 \mid k_1m$, then $n_1$ divides $a n_1m+b k_1m=m$. Conversely, if $n_1 \mid m$, then $n_1 \mid k_1m$. Hence
\begin{align*}
n_1 \mid k_1 m \iff n_1 \mid m.
\end{align*}
Therefore, for every $m \in \mathbb{N}$,
\begin{align*}
(g^k)^m=e \iff n_1 \mid m.
\end{align*}
[guided]
The order of $g^k$ is the least positive exponent $m$ for which $(g^k)^m=e$, so we translate this group-theoretic condition into divisibility in $\mathbb{Z}$.
Let $d=\gcd(n,k)$, with $d>0$. Define $n_1 \in \mathbb{N}$ and $k_1 \in \mathbb{Z}$ by
\begin{align*}
n_1=\frac{n}{d}
\end{align*}
and
\begin{align*}
k_1=\frac{k}{d}.
\end{align*}
Then $n=d n_1$ and $k=d k_1$. By the defining property of the greatest common divisor, after dividing both $n$ and $k$ by their common divisor $d$, the remaining integers are coprime:
\begin{align*}
\gcd(n_1,k_1)=1.
\end{align*}
Now fix $m \in \mathbb{N}$. The group power law gives
\begin{align*}
(g^k)^m=g^{km}.
\end{align*}
From the previous step, $g^r=e$ holds exactly when $n \mid r$. Applying this with $r=km$, we get
\begin{align*}
(g^k)^m=e \iff n \mid km.
\end{align*}
Substitute $n=d n_1$ and $k=d k_1$:
\begin{align*}
n \mid km \iff d n_1 \mid d k_1 m.
\end{align*}
Since $d>0$, cancelling the common factor $d$ in the divisibility relation gives
\begin{align*}
d n_1 \mid d k_1 m \iff n_1 \mid k_1 m.
\end{align*}
The remaining point is where coprimality is used. Because $\gcd(n_1,k_1)=1$, Bezout's identity gives integers $a,b \in \mathbb{Z}$ such that
\begin{align*}
a n_1+b k_1=1.
\end{align*}
If $n_1 \mid k_1m$, then $n_1$ divides both $a n_1m$ and $b k_1m$, so $n_1$ divides their sum:
\begin{align*}
a n_1m+b k_1m=m.
\end{align*}
Thus $n_1 \mid m$. Conversely, if $n_1 \mid m$, then multiplying by $k_1$ gives $n_1 \mid k_1m$. Hence
\begin{align*}
n_1 \mid k_1 m \iff n_1 \mid m.
\end{align*}
Combining the equivalences, for every $m \in \mathbb{N}$,
\begin{align*}
(g^k)^m=e \iff n_1 \mid m.
\end{align*}
[/guided]
[/step]
[step:Extract the least positive exponent]
By definition, $\operatorname{ord}(g^k)$ is the least positive integer $m$ such that $(g^k)^m=e$. The previous step shows that the set of positive integers with this property is precisely
\begin{align*}
\{m \in \mathbb{N}: n_1 \mid m\}.
\end{align*}
Since $n_1 \in \mathbb{N}$, the least positive element of this set is $n_1$. Therefore
\begin{align*}
\operatorname{ord}(g^k)=n_1=\frac{n}{d}=\frac{n}{\gcd(n,k)}.
\end{align*}
This proves the desired formula.
[/step]
