Abstract Algebra/Group Theory/Cyclic groups

• A cyclic group generated by g is

• $\langle g\rangle =\lbrace g^{n}\;|\;n\in \mathbb {Z} \rbrace$

• where $g^{n}={\begin{cases}\underbrace {g\ast g\cdots \ast g} _{n},&n\in \mathbb {Z} ,n\geq 0\\\underbrace {g^{-1}\ast g^{-1}\cdots \ast g^{-1}} _{-n},&n\in \mathbb {Z} ,n<0\end{cases}}$

• Induction shows: $g^{m+n}=g^{m}\ast g^{n}{\text{ and }}g^{mn}=[g^{m}]^{n}$

Theorem

Let C_m be a cyclic group of order m generated by g with $\ast$

Let $(\mathbb {Z} /m,+)$ be the group of integers modulo m with addition

C_m is isomorphic to $(\mathbb {Z} /m,+)$

Lemma

Let n be the minimal positive integer such that gⁿ = e

$g^{i}=g^{j}\leftrightarrow i=j~{\text{mod}}~n$

Proof of Lemma

Let i > j. Let i - j = sn + r where 0 ≤ r < n and s,r,n are all integers.

1. $g^{i}=g^{j}\;$
2. $e=g^{i-j}=g^{sn+r}=[g^{n}]^{s}\ast g^{r}=[e]^{s}\ast g^{r}=g^{r}$	as i - j = sn + r, and gn = e
3. $g^{r}=e$
4. $r=0$	as n is the minimal positive integer such that gn = e and 0 ≤ r < n
5. $i-j=sn$	0. and 7.
6. $i=j~{\text{mod}}~n$

Proof

0. Define   ${\begin{aligned}f\colon C_{m}&\to \mathbb {Z} /m\\g^{i}&\mapsto i~{\text{mod}}~m\end{aligned}}$

Lemma shows f is well defined (only has one output for each input).

f is homomorphism:

$f(g^{i})+f(g^{j})=i+j~{\text{mod}}~m=f(g^{i+j})=f(g^{i}\ast g^{j})$

f is injective by lemma

f is surjective as both $\mathbb {Z} /m$ and $C_{m}$ have m elements and f is injective

Cyclic groups

In the previous section about subgroups we saw that if $G$ is a group with $g\in G$, then the set of powers of $g$, $\langle g\rangle =\{g^{n}\mid n\in \mathbb {Z} \}$ constituted a subgroup of $G$, called the cyclic subgroup generated by $g$. In this section, we will generalize this concept, and in the process, obtain an important family of groups which is very rich in structure.

Definition 1: Let $G$ be a group with an element $g\in G$ such that $\langle g\rangle =G$. Then $G$ is called a cyclic group, and $g$ is called a generator of $G$. Alternatively, $g$ is said to generate $G$. If there exists an integer $n$ such that $g^{n}=e$, and $n$ is the smallest positive such integer, $G$ is denoted $C_{n}$, the cyclic group of order $n$. If no such integer exists, $G$ is denoted $C_{\infty }$, the infinite cyclic group.

The infinite cyclic group can also be denoted $F_{\{g\}}$, the free group with one generator. This is foreshadowing for a future section and can be ignored for now.

Theorem 2: Any cyclic group is abelian.

Proof: Let $G$ be a cyclic group with generator $g$. Then if $h,k\in G$, then $h=g^{n}$ and $k=g^{m}$ for some $n,m\in \mathbb {Z}$. To show commutativity, observe that $hk=g^{n}g^{m}=g^{n+m}=g^{m+n}=g^{m}g^{n}=kh$ and we are done. ∎

Theorem 3: Any subgroup of a cyclic group is cyclic.

Proof: Let $G$ be a cyclic group with generator $g$, and let $H\leq G$. Since $G=\langle g\rangle$, in particular every element of $H$ equals $g^{n}$ for some $n\in \mathbb {Z}$. We claim that if $a$ the lowest positive integer such that $g^{a}\in H$, then $H=\langle g^{a}\rangle$. To see this, let $g^{n}\in H$. Then $n=qa+r$ and $0\leq r<a$ for unique $q,r\in \mathbb {Z}$. Since $H$ is a subgroup and $g^{a}\in H$, we must have $g^{n}(g^{a})^{-q}=g^{qa+r}g^{-qa}=g^{r}\in H$. Now, assume that $r>0$. Then $g^{r}\in H$ contradicts our assumption that $a$ is the least positive integer such that $g^{a}\in H$. Therefore, $r=0$. Consequently, $g^{n}\in H$ only if $n=qa$, and $H=\langle g^{a}\rangle$ and is cyclic, as was to be shown. ∎

As the alert reader will have noticed, the preceding proof invoked the notion of division with remainder which should be familiar from number theory. Our treatment of cyclic groups will have close ties with notions from number theory. This is no coincidence, as the next few statements will show. Indeed, an alternative title for this section could have been "Modular arithmetic and integer ideals". The notion of an ideal may not yet be familiar to the reader, who is asked to wait patiently until the chapter about rings.

Theorem 4: Let $\mathbb {Z} _{n}=\{0,1,2,...,n-1\}$ with addition defined modulo $n$. That is $a+b\equiv r\,\mathrm {mod} \,n$, where $a+b=qn+r$. We denote this operation by $a+_{n}b=r$. Then $(\mathbb {Z} _{n},+_{n})$ is a cyclic group.

Proof: We must first show that $(\mathbb {Z} _{n},+_{n})$ is a group, then find a generator. We verify the group axioms. Associativity is inherited from the integers. The element $0\in Z_{n}$ is an identity element with respect to $+_{n}$. An inverse of $a\in Z_{n}$ is an element $b$ such that $a+_{n}b=0$. Thus $b+a|n$. Then, $b\equiv n-a\equiv -a\,\mathrm {mod} \,n$, and so $b=n-a=-a$, and $(\mathbb {Z} _{n},+_{n})$ is a group. Now, since $a=a\cdot 1=\underbrace {1+...+1} _{a\,\mathrm {terms} }$, $1$ generates $\mathbb {Z} _{n}$ and so $(\mathbb {Z} _{n},+_{n})$ is cyclic. ∎

Unless we explicitly state otherwise, by $\mathbb {Z} _{n}$ we will always refer to the cyclic group $(\mathbb {Z} _{n},+_{n})$. Since the argument for the generator of $\mathbb {Z} _{n}$ can be made valid for any integer $a$, this shows that also $\mathbb {Z}$ is cyclic with the generator $1$.

Theorem 5: An element $a\in \mathbb {Z} _{n}$ is a generator if and only if $\gcd(a,n)=1$.

Proof: We will need the following theorem from number theory: If $m,n$ are integers, then there exists integers $r,s$ such that $rm+sn=1$, if and only if $\gcd(m,n)=1$. We will not prove this here. A proof can be found in the number theory section.

For the right implication, assume that $\langle a\rangle =\mathbb {Z} _{n}$. Then for all $b\in \mathbb {Z} _{n}$, $b\equiv pa\,\mathrm {mod} \,n$ for some integer $p$. In particular, there exists an integer $s$ such that $sa\equiv 1\,\mathrm {mod} \,n$. This implies that there exists another integer $r$ such that $sa-rn=1$. By the above-mentioned theorem from number theory, we then have $\gcd(a,n)=1$. For the left implication, assume $\gcd(a,n)=1$. Then there exists integers $s,r$ such that $sa-rn=1\,\Rightarrow \,sa\equiv 1\,\mathrm {mod} \,n$, implying that $sa=1$ in $\mathbb {Z} _{n}$. Since $1$ generates $\mathbb {Z} _{n}$, it must be true that $a$ is also a generator, proving the theorem. ∎

We can generalize Theorem 5 a bit by looking at the orders of the elements in cyclic groups.

Theorem 6: Let $H=\langle g\rangle \leq \mathbb {Z} _{n}$. Then, $|H|=|a|={\frac {n}{\gcd(a,n)}}$.

Proof: Recall that the order of $a\in \mathbb {Z} _{n}$ is defined as the lowest positive integer $r$ such that $ra=0$ in $\mathbb {Z} _{n}$. Since $\langle g\rangle$ is cyclic, there exists an integer $s$ such that $ra=sn$ is minimal and positive. This is the definition of the least common multiple; $\mathrm {lcm} (a,n)=ra=|a|a$. Recall from number theory that $\mathrm {lcm} (a,n)\cdot \gcd(a,n)=an$. Thus, $|a|={\frac {\mathrm {lcm} (a,n)}{a}}={\frac {an}{a\cdot \gcd(a,n)}}={\frac {n}{\gcd(a,n)}}$, as was to be proven. ∎

Theorem 7: Every subgroup of $\mathbb {Z}$ is of the form $n\mathbb {Z} =\{na\mid a\in \mathbb {Z} \}$.

Proof: The fact that any subgroup of $\mathbb {Z}$ is cyclic follows from Theorem 3. Therefore, let $n$ generate $H\leq \mathbb {Z}$. Then we see immediately that $H=n\mathbb {Z}$. ∎

Theorem 8: Let $a,b\in \mathbb {Z}$ be fixed, and let $H=\{ra+sb|r,s\in \mathbb {Z} \}$. Then $H$ is a subgroup of $\mathbb {Z}$ generated by $\gcd(a,b)$.

Proof: We msut first show that $H$ is a subgroup. This is immediate since $(ra+sb)-(r^{\prime }a+s^{\prime }b)=(r-r^{\prime })a+(s-s^{\prime })b\in H$. From the proof of Theorem 3, we see that any subgroup of $\mathbb {Z}$ is generated by its lowest positive element. It is a theorem of number theory that the lowest positive integer $d$ such that $d=ra+sb$ for fixed integers $a,b$ and $r,s\in \mathbb {Z}$ equals the greatest common divisor of $a$ and $b$ or $\gcd(a,b)$. Thus $\gcd(a,b)$ generates $H$. ∎

Theorem 9: Let $n\mathbb {Z}$ and $m\mathbb {Z}$ be subgroups of $\mathbb {Z}$. Then $n\mathbb {Z} \cap m\mathbb {Z}$ is the subgroup generated by $\mathrm {lcm} (n,m)$.

Proof: The fact that $n\mathbb {Z} \cap m\mathbb {Z}$ is a subgroup is obvious since $n\mathbb {Z}$ and $m\mathbb {Z}$ are subgroups. To find a generator of $n\mathbb {Z} \cap m\mathbb {Z}$, we must find its lowest positive element. That is, the lowest positive integer $p$ such that $p$ is both a multiple of $n$ and of $m$. This is the definition of the least common multiple of $n$ and $m$, or $\mathrm {lcm} (n,m)$, and the result follows. ∎

It should be obvious by now that $C_{n}$ and $\mathbb {Z} _{n}$, and $C_{\infty }$ and $\mathbb {Z}$ are the same groups. This will be made precise in a later section but can be visualized by denoting any generator of $C_{n}$ or $C_{\infty }$ by $1$.

We will have more to say about cyclic groups later, when we have more tools at our disposal.