chapter-3-cyclic-groups.tex

\documentclass[./main.tex]{subfiles}

\begin{document}

\section{Cyclic groups}
Groups are very general things, and thus we don't have much control over them.
However, there are some groups which are much easier to understand and gain
control over. These are the cyclic groups. Cyclic groups are very nice because
any element in the cyclic group must be of a certain form. We thus open with the
motivating example of the integers. 
\begin{example}[The integers]
    Let $G = \bZ$. Consider any integer $n \in \bZ$. Since $n = 1 + \cdots + 1$,
    $n$ times, we can write $n = n \cdot 1$. Every integer is of this form, a
    multiple of 1. Thus, $\bZ = \set{n \cdot 1 : n \in \bZ}$. Alternatively, we
    could say that $n = -n \cdot -1$, and so $\bZ = \set{n \cdot -1: n \in
    \bZ}$. 
\end{example}
It seems that $1$ and $-1$ \emph{generate} the entire group of integers (under
addition), and indeed this is true. 

\begin{definition}[Cyclic group]
    Let $G$ be a group. Then $G$ is \textbf{cyclic} if there is a $g \in G$ such
    that $G = \set{g^n : n \in \bZ}$. Such an element $g$ is called a
    \textbf{generator} of $G$.
\end{definition}
If $G$ is cyclic and $g$ is a generator of $G$, we denote this situation with $G =
\gen{g}$. 

\begin{example}[Cyclic subgroups]
    Let $G$ be a group and $g \in G$. Then, $\gen g$ is a subgroup of $G$.
\end{example}
\begin{exercise}
    Prove that $\gen g$ is a subgroup of $G$.
\end{exercise}

\begin{example}[Integers modulo $n$]
    Let $G = \bZ_n$. Notice that this is again a cyclic group under addition
    modulo $n$. Of course, $1$ remains a generator for $G$. However, unlike
    $\bZ$, which only has 2 generators, $\bZ_n$ could have more than one. We
    will see this in the next example.
\end{example}

\begin{example}
    Let $G = \bZ_6$. Then $G = \gen{1} = \gen{5}$. However, $2$ is not a
    generator of $G$ as $\gen{2} = \set{0, 2, 4}$ which is not all of $\bZ_6$.
\end{example}

\begin{example}[Non-example of a cyclic group]
    Let $G = U(8)$. Then, $G$ is not cyclic, as $\gen{1} = \set{1}$, $\gen{3} =
    \set{1, 3}$, $\gen{5} = \set{1,5}$ and $\gen{7} = \set{1,7}$.
\end{example}

Taking $G = \bZ_6$, we notice that $4 \cdot 2 = 1 \cdot 2$. In general, we would
like to be able to tell when $a^i$ and $a^j$ are the same element (and when they
are not). The next theorem gives necessary and sufficient conditions to be able
to determine this.

\begin{theorem}
    Let $G$ be a group and $a \in G$. If $a$ has infinite order then $a^i = a^j$
    if and only if $i=j$. If $a$ has order $n$ then $\gen{a} = \set{e, a, a^2,
    \dots, a^{n-1}}$ and $a^i = a^j$ if and only if $n$ divides $i-j$.
\end{theorem}
Before starting the proof, a remark about what the statement $\gen{a} = \set{e,
a, a^2, \dots, a^{n-1}}$ means. We are essentially saying that if $a$ has order
$n$, then the cyclic group generated by $a$ has $n$ distinct elements in it and
it is \emph{precisely} the set as written.
\begin{proof}
    Suppose $a$ has infinite order. Then $a^n = e$ if and only if $n=0$. Since
    $a^i = a^j$ if and only if $a^{i-j} = e$, $i-j=0$. Suppose $a$ has order
    $n$. It is clear that $\set{e, a, a^2, \dots, a^{n-1}} \subseteq \gen{a}$.
    Now let $a^k \in \gen{a}$. Then using the division algorithm on $k$ and $n$,
    $a^k = a^{qn + r} = a^{qn} a^r = a^r$. Keeping in mind that $0 \leq r < n$,
    $a^k \in \set{e, a, a^2, \dots, a^{n-1}}$. Now suppose $a^i = a^j$, so
    $a^{i-j} = e$. Apply the division algorithm on $i-j$ to see that $e =
    a^{i-j} = a^{qn + r} = a^r$. Since $n$ is the least positive integer for
    which $a^n = e$ and $r < n$, $r=0$. The converse direction is similar.
\end{proof}

In \cref{M-def:order-of-a-group}, we used the absolute value operation to refer to
both the order of an element and the order of a group. We promised that we will
justify that abuse of notation here. Let us now make good on our promise. Notice
that as a consequence of this theorem we have $\abs{a} = \abs{\gen{a}}$. Thus,
the order of an element $a$ is precisely the order of the cyclic (sub)group that
it generates. 

Another consequence of this theorem is the following corollary.
\begin{corollary}
\label{cor:element-power-being-identity}
    $a^k = e$ if and only if $\abs{a}$ divides $k$. 
\end{corollary}

\begin{corollary}
    If $G$ is a finite group and $a, b \in G$ where $ab=ba$, then $\abs{ab}$
    divides $\abs a \abs b$.
\end{corollary}
In general, however, there is no relationship between $\abs{ab}$ and $\abs a,
\abs b$. The next exercise shows this.

\begin{exercise}
    Let $A = \begin{bmatrix} 0 & -1\\ 1 & 0 \end{bmatrix}$ and $B =
    \begin{bmatrix} 0 & 1 \\ -1 & -1 \end{bmatrix}$ be from
    $\mbb{SL}_2(\bR)$. Compute $\abs A, \abs B$ and $\abs{AB}$.
\end{exercise}

Given cyclic subgroups $\gen{a^i}$ and $\gen{a^j}$, how do we determine whether
they are the same? Given an element $a$ and its order, can we determine
$\abs{a^k}$ for any $k$? The answers to all these questions is yes, and the
following theorem illustrates this.
\begin{theorem}
\label{thm:criterion-for-cyclic-subgrou-equivalence}
    Let $a \in G$ and $\abs a = n$. Let $k > 0$. Let $d = \gcd(n, k)$. Then, we
    have
    \begin{itemize}
        \item $\gen{a^k} = \gen{a^d}$,
        \item $\abs{a^k} = n/d$.
    \end{itemize}
\end{theorem}
\begin{proof}
    Let $k = dr$, so $a^k = a^{dr}$ which shows $\gen{a^k} \subseteq \gen{a^d}$.
    Now write $d = ns + kt$ (c.f. \cref{M-thm:gcd-is-linear-combination}), then
    \[
        a^d = a^{ns} a^{kt} = a^{kt}. 
    \]
    So $a^d \in \gen{a^k}$. Let's prove the second part. Firstly, $(a^d)^{n/d} =
    e$ so $\abs{a^d} \leq n/d$. If $i < n/d$, then $(a^d)^i \neq e$ so this
    establishes $\abs{a^d} = n/d$. The desired conclusion follows from the first
    part.
\end{proof}

The next corollary of this theorem tells us that in a finite cyclic group, the
order of an element divides the order of the group.
\begin{corollary}[Order of an element divides order of the group]
\label{cor:order-element-divides-order-group-fin-cyclic-group}
    If $G$ is a finite cyclic group and $a \in G$, then $\abs a$ divides $\abs
    G$.
\end{corollary}
It thus follows that the order of a cyclic subgroup of a finite cyclic group divides
the order of the group. In a later chapter, we shall soon this is true in
general for any finite group.

This corollary gives us a criterion for the equivalence of cyclic subgroups.
\begin{corollary}[Criterion for equivalence of cyclic subgroups]
    Suppose $a \in G$ has order $n$. Then, $\gen{a^i} = \gen{a^j}$ if and only
    if $\gcd(n,i) = \gcd(n,j)$. 
\end{corollary}
\begin{exercise}
    Prove this corollary.
\end{exercise}

We now have the tools to find all the generators of a finite cyclic group.
\begin{corollary}[Criteria for being a generator]
\label{cor:generator-of-group-criteria}
    Let $G = \gen{a}$ be a cyclic group of order $n$. Let $b$ be an element of
    order $m$. Then, $b$ generates $G$ if and only if $\gcd(m, n) = 1$.
\end{corollary}
Since $\bZ_n$ is always cyclic, we can always easily determine the generators of $\bZ_n$.

A burning question in the reader's mind is on the kind and number of subgroups a
group may contain. For example, we may be wondering if every subgroup of a
cyclic group is cyclic. Intuitively, this should feel true. 
\begin{theorem}
\label{thm:subgroups-of-cyclic-group-are-cyclic}
    Every subgroup of a cyclic group is cyclic. 
\end{theorem}
\begin{proof}
    Let $G = \gen{a}$ and $H \subseteq G$ be a subgroup. Suppose $H$ is not the
    trivial subgroup, for else it is trivially cyclic. Then there is some $t >
    0$ such that $a^t \in H$. We now attempt to find a generator for $H$. Let
    $m$ be the least positive integer such that $a^m \in H$. Obviously
    $\gen{a^m} \subseteq H$. Now let $a^k \in H$. Then write $a^k = a^{qm + r}$.
    Since $m$ is the least, $r = 0$. Thus $a^k \in \gen{a^m}$ and so $\gen{a^m}
    \supseteq H$.
\end{proof}
We remark that we make use of the well ordering principle here, so make sure you
have spotted it!

This theorem tells us exactly what the subgroups of a cyclic group are, and how
to find them. We will invoke \cref{thm:criterion-for-cyclic-subgrou-equivalence}
many times in the proof, so keep that in mind. Additionally, if $d$ divides $n$,
we note that $\gcd(d,n) = d$.
\begin{theorem}[Fundamental Theorem of Cyclic Groups]
    Let $G = \gen{a}$ be a finite cyclic group of order $n$. Then, if $d$
    divides $n$, there is \emph{exactly one} subgroup of order $d$. Moreover,
    these are the \emph{only} subgroups of $G$.
\end{theorem}
\begin{proof}
    Suppose $d$ divides $n$. It is clear that $\gen{a^{n/d}}$ is a subgroup of
    order $d$. Let $H = \gen{a^k}$ be a subgroup of order $d$, we shall show $H
    = \gen{a^{n/d}}$. Since $\gen{a^k} = \gen{a^j}$ where $j = \gcd(n, k)$ and
    $\gen{a^j}$ has order $n/j = d$ it follows that $n/d=j$ so $\gen{a^k} =
    \gen{a^{n/d}}$. The final claim follows from
    \cref{thm:subgroups-of-cyclic-group-are-cyclic} and
    \cref{cor:order-element-divides-order-group-fin-cyclic-group}.
\end{proof}

With this theorem, it is now very easy to find all the subgroups of $\bZ_n$.
\begin{exercise}
    Formulate a corollary that classifies the subgroups of $\bZ_n$.
\end{exercise}

Since cyclic groups are so nice, they should behave nicely under homomorphisms
and isomorphisms as well. 
\begin{proposition}[Properties of cyclic groups under homomorphisms]
\label{prop:cyclic-group-properties-homomorphisms}
    Let $\phi: G \to H$ be a group homomorphism, and $G$ be a cyclic group.
    Then, the following are true. 
    \begin{enumerate}
        \item If $G = \gen{g}$, then $\phi[G] = \gen{\phi(g)}$. In other words,
        $\phi$ takes generators to generators.
    \end{enumerate}
\end{proposition}

\begin{proof}
    If $\phi(x) \in \phi[G]$, then there is some integer $n$ such that $x =
    g^n$. Thus, we have $\phi(x) = \phi(g^n) = \phi(g)^n$. 
\end{proof}

\begin{proposition}[Properties of cyclic groups under isomorphisms]
    Let $\phi: G \to H$ be a group isomorphism, and let $G$ be a cyclic group.
    Then, the following are true.
    \begin{enumerate}
        \item $H$ is cyclic. 
    \end{enumerate}
\end{proposition}
\begin{proof}
    (1) follows from \cref{prop:cyclic-group-properties-homomorphisms}(1)
\end{proof}
Thus, if $G$ is a cyclic group of order $n$, it is isomorphic to $\bZ_n$.
\begin{exercise}
    Show that any cyclic group of order $n$ is isomorphic to $\bZ_n$.
\end{exercise}
We can thus say that there is only one cyclic group of order $n$ up to
isomorphism, which means precisely that any cyclic group of order $n$ is
isomorphic to any other cyclic group of order $n$. This means that any question
about finite cyclic groups can be answered by studying $\bZ_n$ instead.

\subsection{Exercises and Problems}

\begin{exercise}[Criterion for element to be identity]
    Prove that if $a^k = e$, then $k$ divides $\abs{a}$.
\end{exercise}

\begin{exercise}
    Show that if $G$ has order 3, then it must be cyclic.
\end{exercise}

\begin{exercise}
    Show that if $a \in G$, then $\gen{a}$ is a subgroup of $C(a)$.
\end{exercise}

\begin{exercise}
    Let $G$ be a group and $a \in G$. Show that $\gen{a} = \gen{a\inv}$.
\end{exercise}

\begin{exercise}
    Let $G = \bZ$ and let $m, n \in \bZ$. Consider $\gen{m}$ and $\gen n$ as
    subgroups of $G$. Find a generator of $\gen m \cap \gen n$.
\end{exercise}

\begin{exercise}
    Show that $\bQ$ under multiplication is not cyclic.
\end{exercise}

\begin{exercise}
    Let $G$ be a cyclic group of order 15 and let $x \in G$. Suppose that
    \emph{exactly two} of $x^3$, $x^5$ and $x^9$ are equal. Determine
    $\abs{x^{13}}$.
\end{exercise}

\begin{exercise}
    Prove that an infinite group has infinitely many subgroups.
    \textit{Warning: Do not assume that an infinite group must have an element of infinite order.}
\end{exercise}

\begin{exercise}
    Let $n$ be an natural number. Find a group that has exactly $n$ subgroups.
\end{exercise}

\begin{prob}
    Let $G$ be a group with more than one element, and suppose that $G$ has no
    proper nontrivial subgroups. Show that $G$ is a finite group and $\abs G$ is
    prime.
\end{prob}

\begin{prob}
    Let $G$ be a finite group. Prove that $G$ is the union of proper subgroups if
    and only if $G$ is not cyclic.
\end{prob}

Given a cyclic group, a question is to determine how many generators it has. We
already have \cref{cor:generator-of-group-criteria}, which gives us necessary
and sufficient conditions for an element to be a generator. At this point, the
reader should recall the definition of $U(n)$. It appears that every element of
$U(n)$ is a generator of $\bZ_n$, and these are the only generators. Is this
true? 

\begin{proposition}[Number of generators]
    Let $G$ be a cyclic group of order $n$. Then, $G$ has exactly $\abs{U(n)}$
    generators.
\end{proposition}
\begin{proof}
    Let $g \in G$ and $m = \abs g$. Notice that $g$ generates $G$ if and only if
    $\gcd(m, n) = 1$, which is true if and only if $m \in U(n)$. 
\end{proof}

\section{Euler totient function}
We have spent a large amount of time working with $\bZ_n$. This feels very
number theoretic, and the reader may very well be wondering\footnote{If you're
not wondering about it, you might try to skip this section. Heed the warning,
and do not skip it.} about the connection between group theory and number
theory. We shall scratch the surface of this connection by using group theory to
prove some facts about a common function used in number theory, the Euler
totient function.
\begin{warning}
Do not think about skipping this section. There are important theorems in here.
\end{warning}
\begin{definition}[Euler totient function]
    We define the Euler totient function $\varphi(n)$ to be the number of
    natural numbers less than or equal to $n$ that are coprime to $n$.
\end{definition}
It is immediate, by definition, that $\varphi(n) = \abs{U(n)}$. 

Those who have had number theory may be familiar with the following proposition.
You might also recall how much of a pain these are to prove with number theory.
Are we going to subject you to the same pain as you have previously experienced? 
No. We are going to show how we can use group theory to deal with these facts.
\begin{proposition}
    Let $\varphi$ denote the Euler totient function. Then, 

    \begin{enumerate}
        \item If $a$ is coprime to $b$, $\varphi(ab) = \varphi(a) \varphi(b)$
        \item Let $p$ be a prime. Then, $\varphi(p^n) = p^n - p^{n-1}$.
    \end{enumerate}
\end{proposition}
\begin{proof}
    (1) will follow from the more general statement that $U(ab) \cong U(a)
    \times U(b)$. (2) will follow from the more general statement that $U(p^n)
    \cong \bZ_{p^n - p^{n-1}}$ for an odd prime, and $U(2^n) \cong \bZ_2 \times
    \bZ_{2^{n-2}}$ when $p=2$. Thus we shall prove the more general statements
    instead.
\end{proof}

A common theme in algebra is trying to break down larger structures into
smaller, more understandable structures. We began with number theory, by
factorizing numbers into primes and studying the primes to gain control over all
numbers. In group theory, we can try to understand a group in terms of its
subgroups. We shall now prove a theorem that lets us "factorize" $U(n)$. 
\begin{theorem}[Structure of $U(n)$]
    Let $a, b$ be coprime. Then, $U(ab) \cong U(a) \times U(b)$.
\end{theorem}
\begin{proof}
    Notice that the mapping $n \mapsto (n \operatorname{mod} a, n
    \operatorname{mod} b)$ is an isomorphism from $U(ab)$ to $U(a) \times U(b)$.
\end{proof}
The reader should find that the choice of the isomorphism very natural. This
choice is natural in part because we didn't really have any other good options
to choose. 
\begin{exercise}
    Check that the mapping which is claimed to be isomorphisms are indeed isomorphisms.
\end{exercise}

\subsection{Problems and Exercises}
\begin{exercise}[Automorphisms on finite cyclic groups]
\label{ex:automorphisms-on-zn}
    Prove that $\operatorname{Aut}(\bZ_n)$ is isomorphic to $U(n)$.
    \textit{Hint: Consider the mapping $\varphi \mapsto \varphi(1)$. Here,
    $\varphi$ is an automorphism on $\bZ_n$.}
\end{exercise}


\section{Group presentations and generators}

\subfile{chapter-group-presentations-and-generators.tex}

\end{document}