After relating the size of a cyclic group to the order of its generator, we now ask which powers of a generator are also generators. This is a precise arithmetic question. If $G=\langle a\rangle$ has order $n$, then $a^r$ generates $G$ exactly when $r$ is relatively prime to $n$. This test is one of the most useful facts about finite cyclic groups. In this lesson, students will prove the greatest common divisor criterion and apply it to find all generators of a finite cyclic group. :::theorem Let $(G,\circ)$ be a finite group and let $a\in G$ such that $$\begin{equation*} G=\langle a\rangle \end{equation*}$$ and $$\begin{equation*} |G|=n>1. \end{equation*}$$ If $r$ is a positive integer with $1\leq r<n$, then $$\begin{equation*} G=\langle a^r\rangle \iff \operatorname{gcd}(r,n)=1. \end{equation*}$$ ::: :::proof Given that $(G,\circ)$ is a finite group, $a\in G$, $G=\langle a\rangle$, and $|G|=n>1$. Let $r\in\mathbb{N}$ such that $1\leq r<n$. To prove that $$\begin{equation*} G=\langle a^r\rangle \iff \operatorname{gcd}(r,n)=1. \end{equation*}$$ Since $G=\langle a\rangle$ and $|G|=n$, we get $$\begin{equation*} o(a)=n. \end{equation*}$$ Using the formula for the order of a power, $$\begin{equation*} o(a^r)=\frac{n}{\operatorname{gcd}(r,n)}. \end{equation*}$$ [1] To prove that $G=\langle a^r\rangle \implies \operatorname{gcd}(r,n)=1$. Let $$\begin{equation*} G=\langle a^r\rangle. \end{equation*}$$ Then $a^r$ is a generator of $G$, so $$\begin{equation*} o(a^r)=|G|=n. \end{equation*}$$ Therefore $$\begin{align*} \frac{n}{\operatorname{gcd}(r,n)}=n &\implies \operatorname{gcd}(r,n)=1. \end{align*}$$ [2] To prove that $\operatorname{gcd}(r,n)=1 \implies G=\langle a^r\rangle$. Let $$\begin{equation*} \operatorname{gcd}(r,n)=1. \end{equation*}$$ Then $$\begin{align*} o(a^r) &=\frac{n}{\operatorname{gcd}(r,n)}\\ &=\frac{n}{1}\\ &=n. \end{align*}$$ Thus $$\begin{equation*} |\langle a^r\rangle|=n. \end{equation*}$$ Since $\langle a^r\rangle\subseteq G$ and $|G|=n$, we get $$\begin{equation*} G=\langle a^r\rangle. \end{equation*}$$ Hence, $$\begin{equation*} G=\langle a^r\rangle \iff \operatorname{gcd}(r,n)=1. \end{equation*}$$ $\square$ ::: The theorem gives a quick test for generators. In a cyclic group of order $n$, the powers $a^r$ with $\operatorname{gcd}(r,n)=1$ are exactly the generators. Powers with a common factor with $n$ generate a smaller cyclic subgroup. This explains why $\overline{1}$ and $\overline{5}$ generate $\mathbb{Z}_6$, but $\overline{2}$ does not. The generator criterion is controlled by the greatest common divisor. Choose an order $n$ and the preview marks each exponent $1\leq r<n$ according to whether $\operatorname{gcd}(r,n)=1$. Marked exponents give generators $a^r$ of the whole cyclic group, while unmarked exponents generate smaller cyclic subgroups. :::scientific-preview[Generator Exponent Grid] ::: :::example Let $G=\langle a\rangle$ and $|G|=8$. The integers $r$ with $1\leq r<8$ and $\operatorname{gcd}(r,8)=1$ are $$\begin{equation*} 1,3,5,7. \end{equation*}$$ Therefore the generators of $G$ are $$\begin{equation*} a,\;a^3,\;a^5,\;a^7. \end{equation*}$$ ::: :::example Let $G=\langle a\rangle$ and $|G|=12$. The integers $r$ with $1\leq r<12$ and $\operatorname{gcd}(r,12)=1$ are $$\begin{equation*} 1,5,7,11. \end{equation*}$$ Thus the generators of $G$ are $$\begin{equation*} a,\;a^5,\;a^7,\;a^{11}. \end{equation*}$$ ::: :::solved-problem Let $G=\langle a\rangle$ be a cyclic group of order $15$. Find all generators of $G$. ::: :::solution Let $G=\langle a\rangle$ be a cyclic group of order $15$. To find all generators of $G$. The element $a^r$ is a generator of $G$ if and only if $$\begin{equation*} \operatorname{gcd}(r,15)=1. \end{equation*}$$ For $1\leq r<15$, the integers relatively prime to $15$ are $$\begin{equation*} 1,2,4,7,8,11,13,14. \end{equation*}$$ Therefore the generators are $$\begin{equation*} a,\;a^2,\;a^4,\;a^7,\;a^8,\;a^{11},\;a^{13},\;a^{14}. \end{equation*}$$ Hence, these are all generators of $G$. $\square$ ::: :::solved-problem Let $G=\langle a\rangle$ be a cyclic group of order $18$. Determine whether $a^6$ is a generator of $G$. ::: :::solution Let $G=\langle a\rangle$ be a cyclic group of order $18$. To determine whether $a^6$ is a generator of $G$. By the generator criterion, $a^6$ is a generator if and only if $$\begin{equation*} \operatorname{gcd}(6,18)=1. \end{equation*}$$ But $$\begin{equation*} \operatorname{gcd}(6,18)=6. \end{equation*}$$ Therefore $a^6$ is not a generator of $G$. Also, $$\begin{align*} o(a^6) &=\frac{18}{\operatorname{gcd}(6,18)}\\ &=\frac{18}{6}\\ &=3. \end{align*}$$ Hence, $a^6$ is not a generator of $G$. $\square$ ::: Use the calculator below to find all exponents $r$ such that $a^r$ generates a cyclic group of order $n$. Enter $n$. The calculator lists all $r$ with $1\leq r<n$ and $\operatorname{gcd}(r,n)=1$. These exponents give all generators of the form $a^r$. :::calculator[Generator Exponents Calculator] ::: :::exercise [1] State the generator criterion for $a^r$ in a cyclic group of order $n$. [2] Find all generators of a cyclic group of order $10$. [3] Determine whether $a^4$ is a generator when $o(a)=14$. [4] Determine the order of $a^4$ when $o(a)=14$. [5] How many generators does a cyclic group of order $9$ have? ::: :::answer [1] $a^r$ is a generator if and only if $\operatorname{gcd}(r,n)=1$. [2] The generators are $a,a^3,a^7,a^9$. [3] No, because $\operatorname{gcd}(4,14)=2$. [4] $o(a^4)=14/\operatorname{gcd}(4,14)=7$. [5] The generators are $a,a^2,a^4,a^5,a^7,a^8$, so there are $6$ generators. ::: :::faq Q: When does $a^r$ generate a finite cyclic group of order $n$? A: Exactly when $\operatorname{gcd}(r,n)=1$. Q: What happens when $\operatorname{gcd}(r,n)>1$? A: Then $a^r$ generates a proper cyclic subgroup. Q: Does $a^{-1}$ generate when $a$ generates? A: Yes. It corresponds to the exponent $n-1$, which is relatively prime to $n$. Q: How is the number of generators related to number theory? A: It equals the number of integers between $1$ and $n$ that are relatively prime to $n$. ::: :::call-to-action[Prime Order Cyclic Groups] subtitle: Continue to cyclic groups of prime order, where every non-identity element is a generator. button: Next Lesson | /abstract-algebra/introduction-to-groups/cyclic-groups/prime-order-cyclic-groups button-ghost: Previous Lesson | /abstract-algebra/introduction-to-groups/cyclic-groups/finite-and-infinite-cyclic-groups :::