Theorem 6.14

Statement:

Let $G$ be a cyclic group with $n$ elements and generated by $a$. Let $b \in G$ and let $b = a^{s}$. Then $b$ generates a cyclic subgroup $H$ of $G$ containing $n/d$ elements, where $d$ is the greatest common divisor of $n$ and $s$. Also, $\langle a ^{s} \rangle = \langle a ^{t} \rangle$ if and only if $gcd(s,n) = gcd(t,n)$.

Proof:

That $b$ generates a cyclic subgroup $H$ of $G$ is known from Theorem 5.17. We need to show only that $H$ has $n/d$ elements. Following the argument of Case II of Theorem 6.10, we see that $H$ has as many elements as the smallest positive power $m$ of $b$ that gives the identity. Now, $b = a^{s}$, and $b^{m} = e$ if and only if $n$ divides $ms$. What is the smallest positive integer $m$ such that $n$ divides $ms$? Let $d$ be the gcd of $n$ and $s$. Then there exist integers $u$ and $v$ such that

(1)
\begin{equation} d = un + vs \end{equation}

Since $d$ divides both $n$ and $s$, we may write

(2)
\begin{equation} 1 = u(n/d) + v(s/d) \end{equation}

where both $n/d$ and $s/d$ are integers. This last equation shows that $n/d$ and $s/d$ are relatively prime, for any integer dividing both of them must also divide 1. We wish to find the smallest positive $m$ such that

(3)
\begin{align} \frac{ms}{n} = \frac{m(s/d)}{(n/d)} \end{align}

is an integer.

From the boxed division property, we conclude that $n/d$ must divide $m$, so the smallest such $m$ is $n/d$. Thus the order of $H$ is $n/d$.

Taking for a moment $\mathbb{Z_{n}}$ as a model for a cyclic group of order $n$, we see that if $d$ is a divisor of $n$, then the cyclic subgroup $\langle d \rangle$ of $\mathbb{Z_{n}}$ had $n/d$ elements, and contains all the positive integers $m$ less than $n$ such that $gcd(m,\ n) = d$. Thus there is only one subgroup of $\mathbb{Z_{n}}$ of order $n/d$. Taken with the preceding paragraph, this shows at once that if $a$ is a generator of the cyclic group $G$, then $\langle a^{s} \rangle = \langle a^{t} \rangle$ if and only if $gcd(s,\ n) = gcd(t, \ n)$.