## Algebra - Group Theory

### 5. Cyclic Groups

• Definition 5.1: A group $G$ is said to be cyclic group if it is generated by an element $a \in G$ and is denoted by $G=<a>=\{a^n/n \in \mathbb{Z}\}$ or $G=(a)$.

• Remarks:
(1.) If $G$ is an infinite cyclic group generated by $a$, then $G=\{a^n/n \in \mathbb{Z}\}=\{a,a^2,a^3,...,a^n,a^{n+1},....\}$
(2.) Finite cyclic group generated by $a$ is of the form $\{a,a^2,a^3,....,a^{n-1},a^n=e\}$
(3.) Cyclic group may have more than one generator.
(4.) If the binary operation defined on a cyclic group $G=<a>$ is + then every element of $G$ is of the form $na$ for some $n \in \mathbb{Z}$.
(5.) If the binary operation defined on a cyclic group $G=<a>$ is $\times$ then every element of $G$ is of the form $a^n$ for some $n \in \mathbb{Z}$.

• Example: Consider the multiplicative group of fourth roots of unity, $G=\{1,-1,i,-i\}$. Then $G$ is cyclic. For $G=<i>$ because $i^1=i$, $i^2=-1$, $i^3=-i$, $i^4=1$.

• Theorem 5.1: Every cyclic group is abelian. Converse may not be true.
Proof: Let $G$ be a group with $a$ as generator $\Rightarrow$ $G=<a>=\{a^n/n \in \mathbb{Z}\}$
Let $x,y \in G$ $\Rightarrow$ $x=a^m$ and $y=a^n$ where $m,n \in \mathbb{Z}$.
Consider $xy=a^ma^n=a^{m+n}=a^{n+m}=a^na^m=yx$
Thus $xy=yx$ $\forall$ $x,y \in G$.
Converse of the above theorem may not be true. i.e., Every abelian group may not be cyclic.
For example, Consider Klien four group, $K_4=\{1,3,5,7\}$ with binary operation $\otimes_8$.

Clearly $K_4$ is an abelian group but not cyclic. (How!) $\blacksquare$

• Theorem 5.2: If $a$ is a generator of an infinite cyclic group $G$ then $a^{-1}$ is also a generator.
Proof: Let $G$ be a infinite cyclic group generated by element $a$
$\Rightarrow$ $G=<a>=\{a^n/n \in \mathbb{Z}\}$
Let $g \in G$ $\Rightarrow$ $g=a^n$ for some $n \in \mathbb{Z}$
Now $g=(a^{-1})^{-n}=(a^{-1})^m$ where $m=-n$.
Hence $g=(a^{-1})^m$ $\forall$ $g \in G$
$\Rightarrow$ Every element of $G$ is some integral power of $a^{-1}$
$\Rightarrow$ $a^{-1}$ is also a generator of $G$. $\blacksquare$

• Theorem 5.3: If $a$ is a generator of a cyclic group $G$, then $O(a)=O(G)$.
Proof: Let $G$ be a cyclic group generated by $a$ $\Rightarrow$ $G=\{a^n/n \in \mathbb{Z}\}$
Let $O(a)=n$ $\Rightarrow$ $a^n=e$ where $n$ is the least positive integer and $e$ is the identity of $G$.
Conisder a subgroup $H$ of $G$ generated by $a$, i.e., $H=\{a,a^2,a^3,....,a^{n-1},a^n=e\}$
Claim: Elements of $H$ are distinct. For if $a^r=a^s$ where $0<r>s\leq n$. Then $a^r=a^s$ $\Rightarrow$ $a^{r-s}=e$ with $0<r-s<n$ which is a contradiction to the fact that $n$ is the least positive integer such that $a^n=e$. Hence the elements of $H$ are distinct and so $O(H)=n$
Let $g \in G$ $\Rightarrow$ $g=a^m$ for some $m \in \mathbb{Z}$
By division algorithm $\exists$ $q,r$ such that $m=nq+r$ with $0\leq r < n$.
Now $g=a^m$
$\Rightarrow$ $g=a^{nq+r}$
$\Rightarrow$ $g=a^{nq}a^r$
$\Rightarrow$ $g=(a^n)^qa^r$
$\Rightarrow$ $g=e^qa^r$
$\Rightarrow$ $g=a^r$
Since $r<n$, $a^r \in H$ $\Rightarrow$ $g \in H$
Hence, $G\subseteq H$ $......(1)$
Since H is a subgroup of G $\Rightarrow$ $H\subseteq G$ $......(2)$
From (1) and (2), $H=G$ $\Rightarrow$ $O(H)=O(G)=n$
$\Rightarrow$ $O(a)=n=O(G)$ $\blacksquare$

• Theorem 5.4: If $G$ is a finite group of order $n$, containing an element of order $n$, then $G$ is cyclic.
Proof: $G$ is a finite group of order $n$ $\Rightarrow$ $O(G)=n$. Let $a \in G$ of order $n$ $\Rightarrow$ $O(a)=n$.
Let $H$ be a cyclic subgroup of $G$ generated by $a$. Since $O(a)=n$ and $H$ is cyclic generated by $a$, we have $O(a)=O(H)=n=O(G)$
Thus $H=G$ $\Rightarrow$ $G$ is cyclic. $\blacksquare$

• Theorem 5.5: Let $G$ be a cyclic group of order $d$ and $a$ be the generator of $G$. If $a^m=a^n$ with $m\neq n$ then $m\equiv n ($mod$d)$.
Proof: Given, $O(G)=d$ and $G=<a>$. Then $O(a)=d$ (How!)
$O(a)=d$ $\Rightarrow$ $a^d=e$ where, $d$ is the least positive integer.
Now $a^m=a^n$
$\Leftrightarrow$ $a^ma^{-n}=a^na^{-n}$
$\Leftrightarrow$ $a^{m-n}=a^{n-n}$
$\Leftrightarrow$ $a^{m-n}=e$
$\Leftrightarrow$ $d|m-n$
$\Leftrightarrow$ $m\equiv n($mod$d)$ $\blacksquare$

• Theorem 5.6: Let $G$ be a cyclic group of order $d$ generated by the element $a$. Then $a^k$ is also a generator of $G$ if and only if $(k,d)=1$ where $k<d$.
Proof: Given $O(G)=d$ and $G=<a>=\{a^n/ n \in \mathbb{Z}\}$.
Thus $O(a)=d$ $\Rightarrow$ $a^d=e$ where $d$ is the least positive integer.
To prove: $a^k$ is a generator of $G$ $\Leftrightarrow$ $(k,d)=1$
Now let $a^k$ be the generator of $G$ with $k<d$
$\Rightarrow$ $a=(a^k)^s$ for some integer $s$
$\Rightarrow$ $aa^{-1}=(a^k)^sa^{-1}$
$\Rightarrow$ $e=a^{ks-1}$
$\Rightarrow$ $d|ks-1$
$\Rightarrow$ $ks-1=qd$ for some integer $q$
$\Rightarrow$ $ks-qd=1$
$\Rightarrow$ $ks+(-q)d=1$
$\Rightarrow$ $(k,d)=1$ [By Bezout's identity]
Conversely: Suppose $(k,d)=1$ then $\exists$ $s,q \in \mathbb{Z}$ such that $ks+qd=1$
Now, $a=a^1$ $\Rightarrow$ $a=a^{ks+qd}$
$\Rightarrow$ $a=a^{ks}a^{qd}$
$\Rightarrow$ $a=a^{ks}(a^d)^q$
$\Rightarrow$ $a=a^{ks}e$
$\Rightarrow$ $a=(a^k)^s$
Let $g \in G$ $\Rightarrow$ $g=a^n$ for some integer $n$
$\Rightarrow$ $g=(a^{ks})^n$ $\Rightarrow$ $g=(a^k)^{sn}$
$\Rightarrow$ Every element $g \in G$ can be expressed as some integral power of $a^k$.
$\Rightarrow$ $a^k$ is also a generator of $G$. $\blacksquare$

• Lemma 5.1: If $S$ is a subgroup of $(\mathbb{Z},+)$ then $S=\{0\}$ or there exists a positive integer $p$ such that $S=\{mp/m \in \mathbb{Z}\}$

• Theorem 5.7: Every subgroup of a cyclic group is cyclic.
Proof: Let $G=<a>$ and $H$ be a subgroup of $G$.
To prove: $H$ is cyclic.
Let $S=\{m \in \mathbb{Z}/ a^m \in H\}$
Since $H$ is a subgroup of $G$ $\Rightarrow$ $e \in H$ where, $e$ is the identity of $G$.
$\Rightarrow$ $e=a^0 \in H$ $\Rightarrow$ $0 \in S$
$\therefore$ $S$ is non empty.
Let $m,n \in S$ $\Rightarrow$ $a^m,a^n \in H$
Since $H$ is a subgroup $a^m(a^n)^{-1} \in H$ $\Rightarrow$ $a^ma^{-n}=a^{m-n} \in H$
$\Rightarrow$ $m-n \in S$
Hence $S$ is a subgroup of $(\mathbb{Z},+)$.
$\therefore$ $\exists$ a positive integer, $p$ such that $S=\{kp/k \in \mathbb{Z}\}$ or $S=\{0\}$ (by lemma 5.1)
If $S=\{0\}$ then $H=\{e\}=<e>$
If $S=\{kp/k \in \mathbb{Z}\}$ then $H=\{a^{kp}/k \in \mathbb{Z}\}$ $\Rightarrow$ $H=\{(a^{k})^p/k \in \mathbb{Z}\}$
Thus $H=<a^p>$ $\blacksquare$

• Definition 5.2: Euler $\phi$ function, $\phi(n)$ is the number of positive integers not exceeding $n$ that are relatively prime to $n$.

• Definition 5.3: By fundamental theorem of arithmetic for $n>1$ can be expressed uniquely as $n=p^{a_1}_1p^{a_2}_2p_3^{a_3}.....p^{a_k}_k$ where $p_1,p_2,...,p_k$ are primes. Then Euler's product formula is given by, $\phi(n)=n\Big(1-\frac{1}{p_1}\Big)\Big(1-\frac{1}{p_2}\Big)......\Big(1-\frac{1}{p_k}\Big)$

• Examples:
(1.) For $n=10$ we have $10=2\times 5$ So $\phi(10)$ $=10\Big(1-\frac{1}{2}\Big)\Big(1-\frac{1}{5}\Big)$ $=10\Big(\frac{1}{2}\Big)\Big(\frac{4}{5}\Big)=4$
(2.) For $n=18$ we have $18=2\times 3^2$ So $\phi(18)$ $=18\Big(1-\frac{1}{2}\Big)\Big(1-\frac{1}{3}\Big)$ $=18\Big(\frac{1}{2}\Big)\Big(\frac{2}{3}\Big)=6$

• Theorem 5.8: Cyclic group of order $d$ has $\phi(d)$ generators.
Proof: Let $G=<a>$ and $O(G)=n$ and so $O(a)=n$. (Why!)
$\therefore$ $G=\{a,a^2,a^3,...,a^{n-1},a^n=e\}$
Also $G$ has $n$ distinct elements.
Since the generators of $G$ are of the form $a^k$ with $(k,n)=1$
$\Rightarrow$ The number of generators of $G$ is the number of positive integers less than $n$ and relatively prime to $n$.
$\Rightarrow$ The number of generators for the cyclic group $G$ is $\phi(n)$ $\blacksquare$

• Problem 5.1: Show that $\{1,-1,i,-i\}$ is a cyclic group.
Solution: Let $G=\{1,-1,i,-i\}$
Consider $i^1=i$, $i^2=-1$, $i^3=-i$, $i^4=1$
$\therefore$ $G=<i>$ $\Rightarrow$ $G$ is cyclic. $\spadesuit$

• Problem 5.2: Show that the set of cube roots of unity is a cyclic group.
Solution: Consider the set of cube roots of unity, $G=\{1,\omega, \omega^2 \}$.
Consider $\omega^1=\omega$, $\omega^2=\omega^2$, $\omega^3=1$
$\therefore$ $G=<\omega>$ $\Rightarrow$ $G$ is cyclic. $\spadesuit$

• Problem 5.3: Show that $(\mathbb{Z}_5,\oplus_5)$ is a cyclic group. Find all its generators.
Solution: Consider $\mathbb{Z}_5=\{0,1,2,3,4\}$ Consider $4=4$
$4\oplus_54=8\equiv 3$
$4\oplus_54\oplus_54=12\equiv 2$
$4\oplus_54\oplus_54\oplus_54=16\equiv 1$
$4\oplus_54\oplus_54\oplus_54\oplus_54=20\equiv 0$
$\therefore$ $G=<4>$ $\Rightarrow$ $G$ is cyclic.
4 is the generator of $\mathbb{Z}_5$ and $k4$ will be the generator of $\mathbb{Z}_5$ if and only if $(k,5)=1$
$\Rightarrow$ $1,2,3,4$ are the generators of $\mathbb{Z}_5$. $\spadesuit$

• Problem 5.4: Find the number of generators of the cyclic group of order 60.
Solution: Since cyclic group of order $d$ has $\phi(d)$ number of generators, we have cyclic group of order 60 has $\phi(60)$ number of generators.
Consider $60=30\times 2=15\times 2 \times 2=5\times 3\times 2 \times 2=2^2\times 3 \times 5$
$\phi(60)=60\Big(1-\frac{1}{2}\Big)\Big(1-\frac{1}{3}\Big)\Big(1-\frac{1}{5}\Big)=60\Big(\frac{1}{2}\Big)\Big(\frac{2}{3}\Big)\Big(\frac{4}{5}\Big)=16$
$\therefore$ Group of order 60 has 16 generators. $\spadesuit$

• Problem 5.5: Find the number of generators of the cyclic group of order 8.
Solution: Consider $8=2^3$
$\phi(8)=8\Big(1-\frac{1}{2}\Big)=8\Big(\frac{1}{2}\Big)=4$
$\therefore$ Group of order 8 has 4 generators.\hfill $\spadesuit$

• Problem 5.6: Find all the generators of the cyclic group of order 12.
Solution: Let $G$ be a group with $O(G)=12$
Consider $12=2^2\times 3$
$\phi(12)=12\Big(1-\frac{1}{2}\Big)\Big(1-\frac{1}{3}\Big)=12\Big(\frac{1}{2}\Big)\Big(\frac{2}{3}\Big)=4$
$\therefore$ Group of order 12 has 4 generators.
Let $a$ be the generator of $G$. Then $a^k$ is also a generator of $G$ if and only if $(k,12)=1$
$1,5,7,11$ are relatively prime to 12. Hence $a,a^5,a^7,a^{11}$ are the generators of $G$. $\spadesuit$

• Problem 5.7: Find all the generators of the cyclic group of order 8.
Solution: Let $G$ be a group with $O(G)=8$
Consider $8=2^3$
$\phi(8)=8\Big(1-\frac{1}{2}\Big)=8\Big(\frac{1}{2}\Big)=4$
$\therefore$ Group of order 8 has 4 generators.
Let $a$ be the generator of $G$. Then $a^k$ is also a generator of $G$ if and only if $(k,8)=1$
$1,3,5,7$ are relatively prime to 8. Hence $a,a^3,a^5,a^7$ are the generators of $G$. $\spadesuit$

• Problem 5.8: Find all the generators of the cyclic group of order 6.
Solution: Let $G$ be a group with $O(G)=6$
Consider $6=2\times 3$
$\phi(6)=6\Big(1-\frac{1}{2}\Big)\Big(1-\frac{1}{3}\Big)=6\Big(\frac{1}{2}\Big)\Big(\frac{2}{3}\Big)=2$
$\therefore$ Group of order 6 has 2 generators.
Let $a$ be the generator of $G$. Then $a^k$ is also a generator of $G$ if and only if $(k,6)=1$
$1,5$ are relatively prime to 6. Hence $a,a^5$ are the generators of $G$. $\spadesuit$

• Problem 5.9: Find the number of generators of the cyclic group $G$ of order 10. If $a$ is a generator of $G$, What are the other generators of $G$?
Solution: $G$ is a group of order $10$.
Consider $10=2\times 5$
$\phi(10)=10\Big(1-\frac{1}{2}\Big)\Big(1-\frac{1}{5}\Big)=10\Big(\frac{1}{2}\Big)\Big(\frac{4}{5}\Big)=4$
$\therefore$ Group of order 10 has 4 generators.
If $a$ be the generator of $G$. Then $a^k$ is also a generator of $G$ if and only if $(k,10)=1$
$1,3,7,9$ are relatively prime to 6. Hence $a,a^3,a^7,a^9$ are the generators of $G$. $\spadesuit$

• Problem 5.10: Is the multiplicative group $\{1,2,3,4,5,6,7,8\}($mod$9)$ cyclic? If so find all its generators.
Solution:} Let $\mathbb{Z}_9=\{1,2,3,4,5,6,7,8\}$.
$\mathbb{Z}_9$ is not a group with respect to binary operation $\otimes_9$.
For $3 \otimes_9 3 =0 \notin \mathbb{Z}_9$ So closure law does not hold in $G$.
So $\mathbb{Z}_9$ is not cyclic. $\spadesuit$

• Problem 5.11: Is the multiplicative group $\mathbb{Z}_9$ cyclic? If so find all its generators.
Solution: Consider $\mathbb{Z}_9=\{1,2,3,4,5,6,7,8\}$.
$\mathbb{Z}_9$ is not a group with respect to binary operation $\otimes_9$.
For $3 \otimes_9 3 =0 \notin \mathbb{Z}_9$ So closure law does not hold in $\mathbb{Z}_9$.
So $\mathbb{Z}_9$ is not cyclic. $\spadesuit$

• Problem 5.12: Find the number of generators of the cyclic group $(\mathbb{Z}_{18},\oplus_{18})$ and write all its generators.
Solution: Consider $\mathbb{Z}_{18}=\{0,1,2,.....,16,17\}$
$(\mathbb{Z}_{18},\oplus_{18})$ is a group.
Clearly 1 is the generator of $\mathbb{Z}_{18}$.
1 is the generator of $\mathbb{Z}_{18}$ then $k1$ is the generator of $\mathbb{Z}_{18}$ if and only if $(k,18)=1$
$5,7,11,13,17$ are relatively prime to 18.
So $1,5,7,11,13,17$ are the generators of $\mathbb{Z}_{18}$. $\spadesuit$

• Problem 5.13: Is the multiplicative group $\{1,2,3,4,5,6,7,8,9,10\}($mod$11)$ cyclic? If so find all its generators.
Solution: $\mathbb{Z}_{11}=\{1,2,3,4,5,6,7,8,9,10\}$
$(\mathbb{Z}_{11},\otimes_{11})$ is a group since 11 is prime.
2 is the generator of $\mathbb{Z}_{11}$ and $2^k$ is also a generator of $\mathbb{Z}_{11}$ if and only if $(k,10)=1$
$1,3,7,9$ are relatively prime to 10 and so $2^1,2^3,2^7,2^9$ are the generators of $\mathbb{Z}_{11}$ i.e., $2,6,7,8$ are the generators of $\mathbb{Z}_{11}$. $\spadesuit$

• Problem 5.14: Is the multiplicative group $\{1,2,3,4,5,6\}($mod$7)$ cyclic? If so find all its generators.
Solution: $\mathbb{Z}_7=\{1,2,3,4,5,6\}$
$(\mathbb{Z}_7,\otimes_7)$ is a group.
3 is the generator of $\mathbb{Z}_7$ and $3^k$ is also a generator of $\mathbb{Z}_7$ if and only if $(k,6)=1$
$1,5$ are relatively prime to 10 and so $3,3^5$ are the generators of $\mathbb{Z}_7$. i.e., $3,5$ are the generators of $\mathbb{Z}_7$. $\spadesuit$

• Problem 5.15: Show that the multiplicative group $\{1,2,4,5,7,8\}$ mod 9 is cyclic. Find all its generators.
Solution: Let $G=\{1,2,4,5,7,8\}$

Clearly $G$ is a group of order 6 with idenity 1.
2 is the generator of group $G$ and $2^k$ is also a generator of $G$ if and only if $(k,6)=1$.
$1,5$ are relatively prime to 6 and so $2,2^5$ are the generators. i.e., $2,5$ are the generators of $G$. $\spadesuit$

• Problem 5.16: Show that $(\mathbb{Q},+)$ is not a cyclic group.
Solution: Suppose if $(\mathbb{Q},+)$ is cyclic generated by $a \in \mathbb{Q}$. Clearly $a \neq 0$.
Let $a=\frac{p}{q}$ where $p,q \in \mathbb{Z}$ and $q \neq 0$
Now $\frac{1}{2q} \in \mathbb{Q}$ $\Rightarrow$ $\frac{1}{2q}=na$ for some $n \in \mathbb{Z}$
$\Rightarrow$ $\frac{1}{2q}=\frac{np}{q}$ $\Rightarrow$ $\frac{1}{2}=np$ which is not possible.
Hence $(\mathbb{Q},+)$ is not a cyclic group. $\spadesuit$

• Exercise 5.1: Show that the multiplicative group $\{1,3,4,5,9\}$ mod 11 is cyclic. Find all its generators.

• Exercise 5.2: Is the multiplicative group $\{1,5,8,12\}$mod13 cyclic? Find all its generators.

• Exercise 5.3: If $a$ is a generator of cyclic group of order 24, find all its other generators.

• Exercise 5.4: Find all generators of a cyclic group of order 18.