Chapter status:   ✅   in good shape   ✅

TODO: some proofs missing

Groups

We cover the elementary theory of groups, one of the most fundamental algebraic structure consisting of a set with a binary operation satisfying associativity, the existence of an identity element, and the existence of an inverse for every element of the set. We focus in particular on abelian (commutative) groups and cyclic groups, which are of particular relevance for cryptography.

Contents

• Basic Definitions
• Additive/Multiplicative Notation
• Repeated Group Operation
• Direct Product
• Subgroups
• Cosets and Lagrange Theorem
• Normal Subgroups
• Quotient Groups
• Homomorphisms and Isomorphisms
• Group Generation
• Properties of Cyclic Groups
• Classification of Cyclic Groups
• Cauchy's Theorem for Abelian Groups
• Exponent of a Group
• Structure Theorem for Finite Abelian Groups
• Structure Theorem for Finitely Generated Abelian Groups

Basic Definitions

A binary operation over a set $S$ is a function $\star :S\times S\to S$ usually denoted in infix notation, meaning the image of $(a,b)\in S\times S$ is written $a\star b.$

A group is a non-empty set $\mathbb{G}$ equipped with a binary operation $\star$ satisfying the following properties:

• associativity: for every $a,b,c\in \mathbb{G},$ $$(a\star b)\star c=a\star (b\star c);$$
• identity element: there exists $e\in \mathbb{G}$ such that for every $a\in \mathbb{G},$ $$e\star a=a\star e=a;$$ such an $e$ is called the identity element of $\mathbb{G};$
• inverse element: for every $a\in \mathbb{G},$ there exists $b\in \mathbb{G}$ such that $$a\star b=b\star a=e;$$ such a $b$ is called the inverse of $a.$

The use of determiner the for the identity element and the inverse of an element $a$ is justified by the following proposition.

Proposition 5.1. Let $\mathbb{G}$ be a group. Then $\mathbb{G}$ has a unique identity element and every element $a\in \mathbb{G}$ has a unique inverse.

Proof

Assume that $\mathbb{G}$ has two identity elements $e$ and $e.$ Then $e\star e^{\prime }=e$ (because $e^{\prime }$ is an identity element) and $e\star e^{\prime }=e^{\prime }$ (because $e$ is an identity element), hence $e=e^{\prime }.$

Assume that some group element $a$ has two inverses $b$ and $b^{\prime }.$ Then $$\begin{array}{rl}b& =b\star e\\ & =b\star (a\star b^{\prime })\\ & =(b\star a)\star b^{\prime }\\ & =e\star b^{\prime }\\ & =b^{\prime }.\end{array}$$

The group consisting of a single element $e$ such that $e\star e=e$ is called the trivial group.

If the binary operation is commutative, i.e., for every $a,b\in \mathbb{G},$ $a\star b=b\star a,$ then $\mathbb{G}$ is said to be abelian.

If $\mathbb{G}$ is finite, the number of elements of $\mathbb{G}$ is called the order of $\mathbb{G}$ and denoted $\left|\mathbb{G}\right|.$ If $\mathbb{G}$ is infinite, $\mathbb{G}$ is said to have infinite order.

Additive/Multiplicative Notation

There are two standard notation types for the group operation:

• additive: the group operation is denoted $+,$ the identity element is denoted $0$ (or $0_{\mathbb{G}}$ if one wants to avoid confusion with integer $0),$ and the inverse of $a$ is denoted $-a;$
• multiplicative: the group operation is denoted $\times$ or $\cdot ,$ the identity element is denoted $1$ (or $1_{\mathbb{G}}$ if one wants to avoid confusion with integer $1),$ and the inverse of $a$ is denote $a^{-1}.$

In the case of multiplicative notation, the operation symbol might be omitted and the group law simply denoted by juxtaposition. By convention, for an "abstract" group, additive notation is restricted to abelian groups (meaning multiplicative notation is used either when the group is known to be non-abelian, or when the abelian/non-abelian character of the group is unspecified).

For the rest of this chapter, unless specified otherwise, the group operation will be denoted multiplicatively but the identity element will be denoted $e$ for clarity.

Repeated Group Operation

Give a group element $a\in \mathbb{G},$ it is possible to apply the group operation repeatedly to $a$ itself, i.e., compute $a\star a\star \cdots \star a.$

When the group operation is denoted additively, for $k\in \mathbb{Z},$ we define $$ka:=\{\begin{array}{ll}{0}_{\mathbb{G}}& \text{if }k=0\\ \underset{k\text{ terms}}{\underbrace{a+\cdots +a}}& \text{if }k>0\\ \underset{-k\text{ terms}}{\underbrace{(-a)+\cdots +(-a)}}& \text{if }k<0.\end{array}$$ This is usually called the scalar multiplication of $a$ by $k.$

When the group operation is denoted multiplicatively, for $k\in \mathbb{Z},$ we define $$a^k:=\{\begin{array}{ll}{1}_{\mathbb{G}}& \text{if }k=0\\ \underset{k\text{ terms}}{\underbrace{a\times \cdots \times a}}& \text{if }k>0\\ \underset{-k\text{ terms}}{\underbrace{a^{-1}\times \cdots \times a^{-1}}}& \text{if }k<0.\end{array}$$ This is usually called the exponentiation of $a$ by $k.$

Proposition 5.2. Let $\mathbb{G}$ be a group denoted multiplicatively. Then for every $a\in \mathbb{G}$ and every $k,\ell \in \mathbb{Z},$ one has

• $a^{k+\ell }=a^k{a}^{\ell },$
• $a^{k\ell }=(a^k{)}^{\ell }=(a^{\ell }{)}^k,$
• $(a^k{)}^{-1}=a^{-k}.$

Moreover, if $\mathbb{G}$ is abelian, then for every $a,b\in \mathbb{G}$ and every $k\in \mathbb{Z},$ $(ab{)}^k=a^k{b}^k.$

Direct Product

Let $(\mathbb{G},\star )$ and $(\mathbb{H},\bullet )$ be two groups. The direct product of $\mathbb{G}$ and $\mathbb{H}$ is the Cartesian product $$\mathbb{G}\times \mathbb{H}:=\{(a,b)\mid a\in \mathbb{G},b\in \mathbb{H}\}$$ equipped with the binary operation $\diamond$ defined component-wise: $$(a,b)\diamond (c,d)=(a\star c,b\bullet d).$$

Proposition 5.3. The direct product as defined above is a group. Its identity element is $(e_{\mathbb{G}},e_{\mathbb{H}}),$ where $e_{\mathbb{G}}$ and $e_{\mathbb{H}}$ are respectively the identity element of $\mathbb{G}$ and $\mathbb{H}.$ The inverse of $(a,b)\in \mathbb{G}\times \mathbb{H}$ is $(a^{-1},b^{-1}).$

For abelian groups, the direct product is sometimes called direct sum and denoted $\mathbb{G}\oplus \mathbb{H}.$¹

Subgroups

Let $\mathbb{G}$ be a group and $\mathbb{H}$ be a non-empty subset of $\mathbb{G}.$ The subset $\mathbb{H}$ is a subgroup of $\mathbb{G}$ if $\mathbb{H}$ equipped with the binary operation of $\mathbb{G}$ is a group.

Proposition 5.4. Let $\mathbb{G}$ be a group and $\mathbb{H}$ be subset of $\mathbb{G}.$ Then $\mathbb{H}$ is a subgroup of $\mathbb{G}$ if and only if the following three properties are satisfied:

• $e\in \mathbb{H},$
• for every $a,b\in \mathbb{H},$ $ab\in \mathbb{H},$
• for every $a\in \mathbb{H},$ $a^{-1}\in \mathbb{H}.$

The following proposition gives a slightly more compact subgroup criterion.

Proposition 5.5. Let $\mathbb{G}$ be a group and $\mathbb{H}$ be subset of $\mathbb{G}.$ Then $\mathbb{H}$ is a subgroup of $\mathbb{G}$ if and only if $e\in \mathbb{H}$ and for every $a,b\in \mathbb{H},$ $a{b}^{-1}\in \mathbb{H}.$

A subgroup of $\mathbb{G}$ is said to be proper if it is different from $\mathbb{G}.$ Any non-trivial group has at least one proper subgroup, namely $\{e\},$ called the trivial subgroup.

Proposition 5.6. The intersection of a (finite or infinite) set of subgroups is a subgroup.

Proof

Let $\mathbb{H}={\cap }_{i\in I}{\mathbb{H}}_i$ be the intersection of a collection of subgroups ${\mathbb{H}}_i,$ $i\in I.$ Then, by Proposition 5.5, $e\in {\mathbb{H}}_i$ for every $i\in I$ and hence $e\in \mathbb{H}.$ Let $a,b\in \mathbb{H}.$ Then, for every $i\in I,$ $a,b\in {\mathbb{H}}_i$ and hence $a{b}^{-1}\in {\mathbb{H}}_i$ again by Proposition 5.5. Thus, $a{b}^{-1}\in \mathbb{H}.$ It follows that $\mathbb{H}$ is a subgroup.

Cosets and Lagrange Theorem

Let $\mathbb{H}$ be a subgroup of a group $\mathbb{G}.$ Consider the relation defined by $a\sim b$ if and only if $a{b}^{-1}\in \mathbb{H}$ and the dual one defined by $a\sim b$ if and only if $b^{-1}a\in \mathbb{H}.$ The following proposition shows that these are equivalence relations.

Proposition 5.7. Let $\mathbb{G}$ be a group. Let $\mathbb{H}$ be a subgroup of $\mathbb{G}.$ Then the relation defined by $a\sim b$ if and only if $a{b}^{-1}\in \mathbb{H}$ is an equivalence relation. The proposition also holds by replacing $a{b}^{-1}\in \mathbb{H}$ by $b^{-1}a\in \mathbb{H}.$

Proof

Let $\mathbb{H}$ be a subgroup of $\mathbb{G}$ and $\sim$ be relation defined by $a\sim b$ if and only if $a{b}^{-1}\in \mathbb{H}.$ Let us show that $\sim$ is reflexive, symmetric, and transitive.

• reflexivity: $e\in \mathbb{H}$ implies that for every $a\in \mathbb{G},$ $a{a}^{-1}\in \mathbb{H}$ and hence $a\sim a;$
• symmetry: $\mathbb{H}$ being closed under under inverses implies that for every $a,b\in \mathbb{G},$ $$\begin{array}{rl}a\sim b& \Rightarrow a{b}^{-1}\in \mathbb{H}\\ & \Rightarrow (a{b}^{-1}{)}^{-1}\in \mathbb{H}\\ & \Rightarrow b{a}^{-1}\in \mathbb{H}\\ & \Rightarrow b\sim a;\end{array}$$
• transitivity: $\mathbb{H}$ being closed under the binary operation implies that for every $a,b,c\in \mathbb{G},$ $$\begin{array}{rl}(a\sim b)\wedge (b\sim c)& \Rightarrow (a{b}^{-1}\in \mathbb{H})\wedge (b{c}^{-1}\in \mathbb{H})\\ & \Rightarrow a{b}^{-1}b{c}^{-1}\in \mathbb{H}\\ & \Rightarrow a{c}^{-1}\in \mathbb{H}\\ & \Rightarrow a\sim c.\end{array}$$

The proof is similar for the relation defined by $b^{-1}a\in \mathbb{H}.$

Let $\mathbb{H}$ be a subgroup of $\mathbb{G}$ and $\sim$ be the equivalence relation $a\sim b\iff a{b}^{-1}\in \mathbb{H}.$ An equivalence class for $\sim$ is called a right coset of $\mathbb{H}.$ Being equivalence classes, right cosets form a partition of $\mathbb{G}.$ For $g\in \mathbb{G},$ the right coset to which $g$ belongs is easily seen to be $$\mathbb{H}g:=\{hg\mid h\in \mathbb{H}\}.$$ Similarly, an equivalence class for the relation relation $a\sim b\iff b^{-1}a\in \mathbb{H}$ is called a left coset of $\mathbb{H}.$ Left cosets form a partition of $\mathbb{G}$ and for $g\in \mathbb{G},$ the left coset to which $g$ belongs is $$g\mathbb{H}:=\{gh\mid h\in \mathbb{H}\}.$$

When $\mathbb{G}$ is abelian, the set of right cosets and the set of left cosets are the same, but when $\mathbb{G}$ is non-abelian this is not necessarily the case. Note that $\mathbb{H}$ itself is both a right and a left coset.

A cornerstone of group theory is Lagrange's theorem, which essentially follows from the fact that right cosets (as well as left cosets) all have the same size.

Theorem 5.1 (Lagrange's Theorem). Let $\mathbb{G}$ be a finite group. Then the order of any subgroup $\mathbb{H}$ of $\mathbb{G}$ divides the order of $\mathbb{G}.$

Proof

Let $\mathbb{H}$ be a subgroup of $\mathbb{G}.$ For every $g\in \mathbb{G},$ the mapping $h\mapsto hg$ is a bijection from $\mathbb{H}$ to the right coset $\mathbb{H}g:$ it is obviously surjective and $hg=h^{\prime }g\Rightarrow hg{g}^{-1}=h^{\prime }g{g}^{-1}\Rightarrow h=h^{\prime },$ hence it is injective. Hence, all right cosets have $|\mathbb{H}|$ elements. Since right cosets form a partition of $\mathbb{G},$ we have $$|\mathbb{G}|=n|\mathbb{H}|$$ where $n$ is the number of right cosets.

A similar reasoning with left cosets shows that the number of left cosets is equal to the number of right cosets.

The number of right (or left) cosets of $\mathbb{H}$ is called the index of $\mathbb{H}$ in $\mathbb{G}$ and denoted $[\mathbb{G}:\mathbb{H}].$ Hence, Lagrange theorem states that $$|\mathbb{G}|=[\mathbb{G}:\mathbb{H}]|\mathbb{H}|.$$

Normal Subgroups

Having defined an equivalence relation associated with a subgroup, one may ask whether the set of right (or left) cosets can be equipped with a group structure. This is where the notion of normal subgroup comes into play.

Let $\mathbb{G}$ be a group. A subgroup $\mathbb{H}$ of $\mathbb{G}$ is said to be normal if for every $g\in \mathbb{G},$ $g\mathbb{H}=\mathbb{H}g$ (i.e., left and right cosets are equal).

Normality can be characterized by a number of other equivalent conditions. The easiest to check is often the following one.

Proposition 5.8. A subgroup $\mathbb{H}$ of $\mathbb{G}$ is normal if and only if for every $g\in \mathbb{G},$ $g\mathbb{H}{g}^{-1}\subseteq \mathbb{H}.$

For abelian groups, the situation is pretty simple.

Proposition 5.9. Every subgroup of an abelian group is normal.

Proof

If $\mathbb{G}$ is abelian and $\mathbb{H}$ is a subgroup of $\mathbb{G},$ then for any $h\in \mathbb{H},$ $gh{g}^{-1}=g{g}^{-1}h=h$ and hence $g\mathbb{H}{g}^{-1}=\mathbb{H}.$ By Proposition 5.8, this implies that $\mathbb{H}$ is normal.

Let us see now how normal subgroups allow us to construct quotient groups.

Quotient Groups

Let $\mathbb{G}$ be a group and let $\sim$ be an equivalence relation on $\mathbb{G}.$ We say that $\sim$ is compatible with the group structure of $\mathbb{G}$ if $a\sim b$ and $c\sim d$ implies $ac\sim bd.$ If $\sim$ is compatible with the group structure of $\mathbb{G},$ then one can equip the quotient set $\mathbb{G}/\sim$ (the set of all equivalence classes) with a binary operation defined as $[a][b]=[ab],$ where $[a]$ denotes the equivalence class of $a\in \mathbb{G}.$ This is well defined as compatibility of $\sim$ with the group structure ensures that this binary operation does not depend on the specific representatives $a$ and $b$ of each equivalence class. The following proposition states that normal subgroups completely characterize the equivalence relations $\sim$ which are compatible with the group structure of $\mathbb{G}.$

Proposition 5.10. Let $\mathbb{G}$ be a group and $\mathbb{H}$ be a normal subgroup of $\mathbb{G}.$ Then the equivalence relation defined by $a\sim b\iff a{b}^{-1}\in \mathbb{H}$ is compatible with the group structure of $\mathbb{G}.$ Conversely, let $\sim$ be an equivalence relation compatible with the group structure of $\mathbb{G}.$ Then $\mathbb{H}:=[e]$ is a normal subgroup of $\mathbb{G}$ and $a\sim b\iff a{b}^{-1}\in \mathbb{H}.$

Proof

Let $\mathbb{H}$ be a normal subgroup of $\mathbb{G}.$ Let us show that $\sim$ defined by $a\sim b\iff a{b}^{-1}\in \mathbb{H}$ (which is an equivalence relation by Proposition 5.7) is compatible with the group structure of $\mathbb{G}.$ Let $a,b,c,d\in \mathbb{G}$ such that $a\sim b$ and $c\sim d.$ We want to show that $ac\sim bd,$ i.e., $ac(bd{)}^{-1}\in \mathbb{H}.$ Note that $$ac(bd{)}^{-1}=ac{d}^{-1}{b}^{-1}=ac{d}^{-1}{a}^{-1}a{b}^{-1}.$$ We have $c{d}^{-1}\in \mathbb{H}$ because $c\sim d,$ which implies that $g:=a(c{d}^{-1})a^{-1}\in \mathbb{H}$ because $\mathbb{H}$ is normal. We also have $a{b}^{-1}\in \mathbb{H}$ because $a\sim b,$ hence $g(a{b}^{-1})=ac{d}^{-1}{a}^{-1}a{b}^{-1}=ac(bd{)}^{-1}\in \mathbb{H}$ and $ac\sim bd.$

Conversely, assume that $\sim$ is an equivalence relation which is compatible with the group structure of $\mathbb{G}.$ Define $\mathbb{H}$ as $[e],$ the equivalence class of the identity element. Let us first show that $\mathbb{H}$ is a normal subgroup. Clearly, $e\in \mathbb{H}.$ Let $a,b\in \mathbb{H},$ i.e., $a\sim e$ and $b\sim e.$ Then, by compatibility of $\sim$ with the group structure, we have $$\begin{array}{rlrl}a\sim e& \Rightarrow a{b}^{-1}\sim e{b}^{-1}& & (b^{-1}\sim b^{-1})\\ & \Rightarrow a{b}^{-1}e\sim b^{-1}b& & (e\sim b)\\ & \Rightarrow a{b}^{-1}\sim e.& & \end{array}$$ Hence $a{b}^{-1}\in \mathbb{H}$ and by Proposition 5.5, $\mathbb{H}$ is a subgroup.

To show that $\mathbb{H}$ is normal, let us show that for every $g\in \mathbb{G},$ $g\mathbb{H}{g}^{-1}\subseteq \mathbb{H}.$ Let $g\in \mathbb{G}$ and $h\in \mathbb{H}.$ Then $$\begin{array}{rlrl}h\sim e& \Rightarrow gh\sim g& & (g\sim g)\\ & \Rightarrow gh{g}^{-1}\sim g{g}^{-1}& & (g^{-1}\sim g^{-1})\\ & \Rightarrow gh{g}^{-1}\sim e.& & \end{array}$$ Hence $gh{g}^{-1}\in \mathbb{H}$ and $\mathbb{H}$ is normal.

It remains to show $a\sim b\iff a{b}^{-1}\in \mathbb{H}.$ By compatibility of $\sim$ with the group structure, we have $a\sim b\Rightarrow a{b}^{-1}\sim b{b}^{-1}\Rightarrow a{b}^{-1}\sim e$ and $a{b}^{-1}\sim e\Rightarrow a{b}^{-1}b\sim b\Rightarrow a\sim b.$ Hence $a\sim b\iff a{b}^{-1}\sim e\iff a{b}^{-1}\in \mathbb{H},$ which concludes the proof.

Let $\mathbb{H}$ be a normal subgroup of $\mathbb{G}$ and let $\sim$ be the equivalence relation defined by $a\sim b\iff a{b}^{-1}\in \mathbb{H}.$ Then the quotient set $\mathbb{G}/\sim$ equipped with the binary operation defined by $[a][b]=[ab]$ is a group (as shown in the proposition below) called the quotient group associated with $\mathbb{H}$ and denoted $\mathbb{G}/\mathbb{H}.$ Note that the order of $\mathbb{G}/\mathbb{H}$ is $[\mathbb{G}:\mathbb{H}],$ the index of $\mathbb{H}.$

Proposition 5.11. Let $\mathbb{G}$ be a group and $\mathbb{H}$ be a normal subgroup of $\mathbb{G}.$ Then $\mathbb{G}/\mathbb{H}$ is a group. Its identity element is $[e]$ and the inverse of $[a]$ is $[a{]}^{-1}:=[a^{-1}].$ If $\mathbb{G}$ is abelian then so is $\mathbb{G}/\mathbb{H}.$

Proof

This follows straightforwardly from the definition of the binary operation $[a][b]=[ab].$

Homomorphisms and Isomorphisms

Let $\mathbb{G}$ and ${\mathbb{G}}^{\prime }$ be two groups.

• A group homomorphism is a function $f$ from $\mathbb{G}$ to ${\mathbb{G}}^{\prime }$ such that for every $a,b\in \mathbb{G},$ $f(ab)=f(a)f(b).$
• If $\mathbb{G}={\mathbb{G}}^{\prime },$ then $f$ is called a group endomorphism.
• If $f$ is bijective, then $f$ is called a group isomorphism and groups $\mathbb{G}$ and ${\mathbb{G}}^{\prime }$ are said isomorphic, denoted $\mathbb{G}\cong {\mathbb{G}}^{\prime }.$
• If $\mathbb{G}={\mathbb{G}}^{\prime }$ and $f$ is bijective, then $f$ is called a group automorphism (hence, a group automorphism is both a group endomorphism and a group isomorphism).

The following proposition gives a number of properties of group homomorphisms.

Proposition 5.12. Let $\mathbb{G}$ and ${\mathbb{G}}^{\prime }$ be two groups and $f:\mathbb{G}\to {\mathbb{G}}^{\prime }$ be a group homomorphism. Then:

• $f(e_{\mathbb{G}})=e_{{\mathbb{G}}^{\prime }};$
• for every $a\in \mathbb{G},$ $f(a^{-1})=f(a{)}^{-1};$
• for every subgroup $\mathbb{H}$ of $\mathbb{G},$ $f(\mathbb{H}):=\{f(a)\mid a\in \mathbb{H}\}$ is a subgroup of ${\mathbb{G}}^{\prime };$
• for every subgroup ${\mathbb{H}}^{\prime }$ of ${\mathbb{G}}^{\prime },$ $f^{-1}({\mathbb{H}}^{\prime }):=\{a\in \mathbb{G}\mid f(a)\in {\mathbb{H}}^{\prime }\}$ is a subgroup of $\mathbb{G};$
• if $f$ is a group isomorphism, then the inverse function $f^{-1}:{\mathbb{G}}^{\prime }\to \mathbb{G}$ is also a group isomorphism;
• if ${\mathbb{G}}^{\prime }$ is another group and $f^{\prime }:{\mathbb{G}}^{\prime }\to {\mathbb{G}}^{\prime \prime }$ is a group homomorphism, then $f^{\prime }\circ f$ is a group homomorphism from $\mathbb{G}$ to ${\mathbb{G}}^{\prime \prime }.$

Let $f:\mathbb{G}\to {\mathbb{G}}^{\prime }$ be a group homomorphism. Two sets related to $f$ are particularly important:

• The kernel of $f$ is the subset of $\mathbb{G}$ defined as $$\ker (f):=\{a\in \mathbb{G}\mid f(a)=e_{{\mathbb{G}}^{\prime }}\}.$$
• The image of $f$ is the subset of ${\mathbb{G}}^{\prime }$ defined as $$\mathrm{im}(f):=\{f(a)\mid a\in \mathbb{G}\}.$$

By Proposition 5.12, $\ker (f)$ is a subgroup of $\mathbb{G}$ since it is equal to $f^{-1}(\{e_{{\mathbb{G}}^{\prime }}\})$ and $\mathrm{im}(f)$ is a subgroup of ${\mathbb{G}}^{\prime }$ since it is equal to $f(\mathbb{G}).$

Theorem 5.2 (First Isomorphism Theorem). Let $f:\mathbb{G}\to {\mathbb{G}}^{\prime }$ be a group homomorphism. Then $\ker (f)$ is a normal subgroup of $\mathbb{G}$ and $\mathbb{G}/\ker (f)\cong \mathrm{im}(f).$

Proof

Let us first show that $\ker (f)$ is normal. Let $g\in \mathbb{G}$ and $h\in \ker (f).$ Then $$\begin{array}{rl}f(gh{g}^{-1})& =f(g)f(h)f(g^{-1})\\ & =f(g)e_{{\mathbb{G}}^{\prime }}f(g{)}^{-1}\\ & =f(g)f(g{)}^{-1}\\ & =e_{{\mathbb{G}}^{\prime }}.\end{array}$$ Hence $g\ker (f)g^{-1}\subseteq \ker (f)$ and hence $\ker (f)$ is normal.

Consider now the mapping $\bar{f}:\mathbb{G}/\ker (f)\to \mathrm{im}(f)$ defined by $\bar{f}([a])=f(a).$ It is well-defined since $$\begin{array}{rl}[a]=[b]& ⟺a{b}^{-1}\in \ker (f)\\ & ⟺f(a{b}^{-1})=e_{{\mathbb{G}}^{\prime }}\\ & ⟺f(a)=f(b).\end{array}$$ In other words, equivalence classes of $\mathbb{G}/\ker (f)$ are just subsets of elements of $\mathbb{G}$ with the same image under $f.$ Consequently, the definition of $\bar{f}$ does not depend on the representative of the equivalence class.

It is a group homomorphism since $$\begin{array}{rl}\bar{f}([a][b])& =\bar{f}([ab])\\ & =f(ab)\\ & =f(a)f(b)\\ & =\bar{f}([a])\bar{f}([b]).\end{array}$$ Moreover, it is injective since $\bar{f}([a])=\bar{f}([b])\iff f(a)=f(b)\iff [a]=[b].$ It is also surjective since any element in $h\in \mathrm{im}(f)$ is of the form $f(a)$ for some $a\in \mathbb{G}$ and hence $h=\bar{f}([a]).$ Hence, $\bar{f}$ is a group isomorphism.

There are three other isomorphism theorems but they are not as useful as the first one.

Group Generation

Let $\mathbb{G}$ be a group and $A$ be a subset of $\mathbb{G}.$ The subgroup generated by $A$, denoted $⟨A⟩,$ is the intersection of all subgroups of $\mathbb{G}$ containing $A.$ (Recall that by Proposition 5.6, an intersection of subgroups is a subgroup.) Informally, it is the "smallest" (for inclusion) subgroup of $\mathbb{G}$ which contains $A:$ any subgroup containing $A$ contains $⟨A⟩.$

The following proposition gives a more explicit characterization.

Proposition 5.13. Let $\mathbb{G}$ be a group and $A$ be a subset of $\mathbb{G}.$ Then $⟨A⟩$ is the subgroup of all elements of $\mathbb{G}$ that can be expressed as the finite product of elements of $A$ and inverse of elements of $A.$

Note in particular that $⟨\varnothing ⟩=\{e\}$ (in which case Proposition 5.13 still holds with the convention that an empty product of group elements is equal to $e).$

If $A=\{a_1,\dots ,a_k\}$ is finite, the subgroup generated by $A$ is also denoted $⟨a_1,\dots ,a_k⟩.$ When $\mathbb{G}$ is abelian, then $$⟨a_1,\dots ,a_k⟩=\left\{a_1^{z_1}\cdots a_k^{z_k}\mid z_1,\dots ,z_k\in \mathbb{Z}\right\}.$$

A group $\mathbb{G}$ is said to be finitely generated is there exists a finite number of elements $g_1,\dots g_k\in \mathbb{G}$ such that $\mathbb{G}=⟨g_1,\dots ,g_k⟩,$ in which case $\{g_1,\dots ,g_k\}$ is called a generating set of $\mathbb{G}.$

A group $\mathbb{G}$ is said cyclic (or monogenous²) if there exists $g\in \mathbb{G}$ such that $\mathbb{G}=⟨g⟩,$ in which case $g$ is called a generator of $\mathbb{G}.$

The order of an element $a\in \mathbb{G}$ is the order of the subgroup $⟨a⟩.$ If $\mathbb{G}$ has infinite order, the order of an element $a\in \mathbb{G}$ can be finite or infinite.

Below we list a number of properties of the order of an element.

Proposition 5.14. Let $\mathbb{G}$ be a group and $a\in \mathbb{G}$ be a group element. Then $a$ has finite order if and only if there exists $k\in {\mathbb{N}}^{\ast }$ such that $a^k=e.$ In that case, $a$'s order is the smallest integer $n\ge 1$ such that $a^n=e$ and one has $$⟨a⟩=\{e,a,a^2,\dots ,a^{n-1}\}.$$

Proposition 5.15. If $\mathbb{G}$ has finite order $n,$ then the order of any element $a\in \mathbb{G}$ divides $n.$ In particular, for any $a\in \mathbb{G},$ $a^n=e.$

Proof

The first part is a direct consequence of Lagrange's Theorem. For the second part, let $m$ be the order of $a$ and write $n=dm.$ Then $a^n=a^{dm}=(a^m{)}^d=e^d=e.$

Proposition 5.16. Let $\mathbb{G}$ be a group and $a\in \mathbb{G}$ be an element of order $n.$ Then for every $k\in \mathbb{Z},$ $a^k=e$ if and only if $n$ divides $k.$

Proof

If $n$ divides $k$ then $k=dn$ for some integer $d,$ which implies $a^k=a^{dn}=(a^n{)}^d=e^d=e.$ Conversely, assume that $a^k=e.$ By Euclid's division lemma, there exists $q,r\in \mathbb{Z}$ such that $k=qn+r$ and $0\le r<n.$ Then $a^k=a^{qn+r}=(a^n{)}^q{a}^r=a^r$ and consequently $a^r=e.$ This implies that $r=0$ as otherwise $a$ would have order $r<n.$ Hence, $k=qn$ and $n$ divides $k.$

Proposition 5.17. Let $\mathbb{G}$ be a group, $a\in \mathbb{G}$ be an element of order $n,$ and $k\in \mathbb{Z}.$ Then the order of $g^k$ is $n/\gcd (n,k).$

Proof

Let $d=\gcd (k,n)$ and let $\ell$ be the order of $g^k.$ Then $(g^k{)}^{\ell }=g^{k\ell }=e$ and hence by Proposition 5.16, $n\mid k\ell ,$ which implies $(\frac{n}{d})\mid (\frac{k}{d})\ell .$ Since $\gcd (\frac{n}{d},\frac{k}{d})=1,$ this implies $\frac{n}{d}\mid \ell .$

On the other hand, $(g^k{)}^{\frac{n}{d}}=(g^n{)}^{\frac{k}{d}}=e^{\frac{k}{d}}=e,$ and hence by Proposition 5.16, $\ell \mid \frac{n}{d}.$ We conclude that $\ell =n/d.$

Properties of Cyclic Groups

Proposition 5.18. Any cyclic group is abelian.

Proof

Let $\mathbb{G}$ be a cyclic group, let $g$ be a generator of $\mathbb{G},$ and let $a,b\in \mathbb{G}$ be two group elements. Then there exists $k,\ell \in \mathbb{Z}$ such that $a=g^k$ and $b=g^{\ell },$ which implies that $$ab=g^k{g}^{\ell }=g^{k+\ell }=g^{\ell }{g}^k=ba.$$

Proposition 5.19. Let $\mathbb{G}$ be a cyclic group and $\mathbb{H}$ be a subgroup of $\mathbb{G}.$ Then $\mathbb{H}$ and $\mathbb{G}/\mathbb{H}$ are cyclic.

Proof

Let $\mathbb{G}$ be a cyclic group, $g$ be a generator of $\mathbb{G},$ and $\mathbb{H}$ be a subgroup of $\mathbb{G}.$ Let us first show that $\mathbb{H}$ is cyclic. If $\mathbb{H}=\{e\}$ then $\mathbb{H}$ is clearly cyclic. Otherwise, let $n\ge 1$ be the smallest integer such that $g^n\in \mathbb{H}$ (which necessarily exists since $\mathbb{H}$ contains at least one element different from $e$ and either this element or its inverse can be written $g^m$ for some $m\ge 1).$ We will prove that $\mathbb{H}=⟨g^n⟩.$ Clearly, $⟨g^n⟩\subseteq \mathbb{H}$ since $\mathbb{H}$ is a subgroup. Conversely, let $a\in \mathbb{H}.$ Then $a=g^k$ for some $k\in \mathbb{Z}.$ By Euclid's division lemma, there exists $q,r\in \mathbb{Z}$ such that $k=qn+r$ and $0\le r<n.$ Then $a=g^k=g^{qn+r}=(g^n{)}^q{g}^r,$ and consequently $g^r\in \mathbb{H}.$ This implies that $r=0$ as otherwise this would contradict the minimality of $n.$ Hence $a=(g^n{)}^q\in ⟨g^n⟩$ and $\mathbb{H}\subseteq ⟨g^n⟩.$ Thus, $\mathbb{H}=⟨g^n⟩$ and hence $\mathbb{H}$ is cyclic.

Let us now show that $\mathbb{G}/\mathbb{H}$ is cyclic. More precisely, let us prove that $\mathbb{G}/\mathbb{H}=⟨[g]⟩.$ Let $[a]\in \mathbb{G}/\mathbb{H}$ be an element of the quotient group specified by an arbitrary representative $a\in \mathbb{G}.$ Then there exists $k\in \mathbb{Z}$ such that $a=g^k.$ Thus, $[a]=[g^k]=[g{]}^k$ and hence $[g]$ is a generator of $\mathbb{G}/\mathbb{H}.$

Proposition 5.20. Any group with prime order is cyclic and any element different from the identity element is a generator of $\mathbb{G}.$

Proof

Let $\mathbb{G}$ be a group of prime order $p.$ Let $a\in \mathbb{G}$ be an element different from the identity element and let $n$ be the order of $a.$ Since the order of an element divides the order of the group by Proposition 5.15, one has either $n=1$ or $n=p.$ Since $a\ne e,$ one cannot have $n=1,$ hence $n=p$ and $a$ generates $\mathbb{G}.$

Proposition 5.21. Let $\mathbb{G}$ be a cyclic group of order $n,$ $g$ be a generator of $\mathbb{G},$ and $k\in \mathbb{Z}.$ Then $⟨g^k⟩=\mathbb{G}$ if and only if $\gcd (n,k)=1.$ In particular, $\mathbb{G}$ has $\varphi (n)$ generators, where $\varphi$ is Euler's function.

Proof

We have $⟨g^k⟩=\mathbb{G}$ if and only if the order of $g^k$ is $n,$ which by Proposition 5.17 is equivalent to $\gcd (n,k)=1.$

For the second part of the proposition, write $\mathbb{G}=\{e,g,\dots ,g^{n-1}\}.$ Then generators of $\mathbb{G}$ are exactly elements of the form $g^k$ with $\gcd (n,k)=1$ and hence there are $\varphi (n)$ such elements.

Proposition 5.22. Let ${\mathbb{G}}_1$ and ${\mathbb{G}}_2$ be two cyclic groups of order $n_1$ and $n_2$ respectively. Then the direct product ${\mathbb{G}}_1\times {\mathbb{G}}_2$ is cyclic if and only if $\gcd (n_1,n_2)=1.$ Moreover, $(g_1,g_2)$ is a generator of ${\mathbb{G}}_1\times {\mathbb{G}}_2$ if and only if $g_1$ is a generator of ${\mathbb{G}}_1$ and $g_2$ is a generator of ${\mathbb{G}}_2.$

Proof

Let us first show the following lemma: Let $a_1\in {\mathbb{G}}_1$ be an element of order $k_1$ and $a_2\in {\mathbb{G}}_2$ be an element of order $k_2.$ Then $(a_1,a_2)$ has order $\mathrm{lcm}(k_1,k_2).$

Let $e_1$ be the identity element of ${\mathbb{G}}_1$ and $e_2$ be the identity element of $e_2.$ Then $$\begin{array}{rl}(a_1,a_2{)}^k=(e_1,e_2)& ⟺a_1^k=e_1\wedge a_2^k=e_2\\ & ⟺k_1\mid k\wedge k_2\mid k.\end{array}$$ The smallest such positive integer $k$ is by definition $\mathrm{lcm}(k_1,k_2),$ which proves the lemma.

Let us now prove the proposition. Assume that ${\mathbb{G}}_1\times {\mathbb{G}}_2$ is cyclic and let $(g_1,g_2)$ be a generator of ${\mathbb{G}}_1\times {\mathbb{G}}_2.$ Then clearly $g_1$ must be a generator of ${\mathbb{G}}_1$ and $g_2$ a generator of ${\mathbb{G}}_2.$ By the previous lemma, $(g_1,g_2)$ has order $\mathrm{lcm}(n_1,n_2).$ On the other hand, $(g_1,g_2)$ has order $\left|{\mathbb{G}}_1\times {\mathbb{G}}_2\right|=n_1{n}_2$ as it generates ${\mathbb{G}}_1\times {\mathbb{G}}_2.$ Hence, $\mathrm{lcm}(n_1,n_2)=n_1{n}_2,$ which implies $\gcd (n_1,n_2)=1.$

Conversely, assume that $\gcd (n_1,n_2)=1$ and let $g_1$ be a generator of ${\mathbb{G}}_1$ and $g_2$ be a generator of ${\mathbb{G}}_2.$ By the lemma, $(g_1,g_2)$ has order $\mathrm{lcm}(n_1,n_2)=n_1{n}_2=\left|{\mathbb{G}}_1\times {\mathbb{G}}_2\right|$ and hence generates ${\mathbb{G}}_1\times {\mathbb{G}}_2.$

Classification of Cyclic Groups

The set of integers $$\mathbb{Z}=\{\dots ,-2,-1,0,1,2,\dots \}$$ equipped with addition is a cyclic group of infinite order with identity element $0$ and generators $1$ and $-1.$

What are its subgroups? In general, a simple way to construct subgroups of any group is given by the following proposition.

Proposition 5.23. Let $\mathbb{G}$ be a group denoted additively and $n\in \mathbb{Z}$ be an integer. Then $$n\mathbb{G}:=\{na\mid a\in \mathbb{G}\}$$ is a subgroup of $\mathbb{G}.$

Proof

First, one has $0\in n\mathbb{G}$ since $0=n0.$ Second, let $a,b\in n\mathbb{G}.$ Then $a=n{a}^{\prime }$ and $b=n{b}^{\prime }$ for some $a^{\prime },b^{\prime }\in \mathbb{G}.$ Hence, $a-b=n(a^{\prime }-b^{\prime })\in n\mathbb{G}.$ Thus, by Proposition 5.5, $n\mathbb{G}$ is a subgroup of $\mathbb{G}.$

Hence, for any integer $n\in \mathbb{N},$ the set $n\mathbb{Z}:=\{nz\mid z\in \mathbb{Z}\}$ is a subgroup of $\mathbb{Z}.$ By Proposition 5.19, it is cyclic. One can easily check that it has infinite order and that it is generated by $n$ and $-n.$ These are in fact the only subgroups of $\mathbb{Z}.$

Proposition 5.24. Let $\mathbb{G}$ be a subgroup of $\mathbb{Z}.$ Then there exists a unique $n\in \mathbb{N}$ such that $\mathbb{G}=n\mathbb{Z}.$

Proof

Le us show existence first. If $\mathbb{G}=\{0\}$ then $\mathbb{G}=0\mathbb{Z}.$ Assume now that $\mathbb{G}\ne \{0\},$ implying that $\mathbb{G}$ contains at least one positive integer (it contains at least one non-zero integer $a$ and either $a$ or $-a$ is positive). Let $n$ be the smallest positive integer in $\mathbb{G}.$ Let us show that $\mathbb{G}=n\mathbb{Z}.$ Clearly, $n\mathbb{Z}\subseteq \mathbb{G}$ since $n\in \mathbb{G}.$ Conversely, let $k\in \mathbb{G}.$ By Euclid's division lemma, there exists $q,r\in \mathbb{Z}$ such that $k=qn+r$ and $0\le r<n.$ Since $n$ and $k$ are in $\mathbb{G},$ $r=k-qn$ is also in $\mathbb{G},$ which implies $r=0$ as otherwise this would contradict the minimality of $n.$ Thus, $k=qn\in n\mathbb{Z}$ and $\mathbb{G}\subseteq n\mathbb{Z}.$ Hence, $\mathbb{G}=n\mathbb{Z}$ which proves existence.

For uniqueness, assume that $\mathbb{G}=n\mathbb{Z}=n^{\prime }\mathbb{Z}$ for $n,n^{\prime }\in \mathbb{N}.$ Then $n\in n^{\prime }\mathbb{Z}$ implies $n^{\prime }\mid n$ and $n^{\prime }\in n\mathbb{Z}$ implies $n\mid n^{\prime },$ and consequently $n=n^{\prime }$ since $n$ and $n^{\prime }$ are in $\mathbb{N}.$

For any $n\in \mathbb{N},$ we can consider the quotient group $\mathbb{Z}/n\mathbb{Z}.$ The equivalence class of $a\in \mathbb{Z}$ is $[a]=\{a+nz\mid z\in \mathbb{Z}\},$ also called the residue class of $a$ modulo $n$. There are $n$ distinct classes, namely $[[0]],\dots ,[[n-1]].$ Hence, the index of $n\mathbb{Z}$ is $n$ and $\mathbb{Z}/n\mathbb{Z}$ has order $n.$ It is cyclic with generator $[1]$ (and $[-1]).$ More generally, by Proposition 5.21, the generators of $\mathbb{Z}/n\mathbb{Z}$ are $[k]$ for $k\in \mathbb{Z}$ such that $\gcd (k,n)=1.$

Another way to think of $\mathbb{Z}/n\mathbb{Z}$ is as the set $\{0,1,\dots ,n-1\}$ equipped with "modulo $n$" addition and inverses. More precisely, let ${\mathbb{Z}}_n$ be the set of symbols $\{[[0]],[[1]],\dots ,[[n-1]]\}$ equipped with the binary operation $$[[a]]+[[b]]=[[(a+b)\mathrm{mod}n]].$$ This is a group with identity $[[0]]$ and inverse $-[[a]]=[[(-a)\mathrm{mod}n]].$ One can easily see that $\mathbb{Z}/n\mathbb{Z}$ and ${\mathbb{Z}}_n$ are isomorphic, the isomorphism being $[a]\mapsto [[a\mathrm{mod}n]].$ From now on, we will work with the latter formalism.

As for $\mathbb{Z},$ let us characterize the subgroups of ${\mathbb{Z}}_n.$ By Proposition 5.23, for any integer $m\in \mathbb{Z},$ $$m{\mathbb{Z}}_n:=\{m[[u]]\mid [[u]]\in {\mathbb{Z}}_n\}$$ is a subgroup of ${\mathbb{Z}}_n.$ What does this subgroup look like? One has $$\begin{array}{rl}[[a]]\in m{\mathbb{Z}}_n& \iff \exists [[u]]\in {\mathbb{Z}}_n,[[a]]=m[[u]]\\ & \iff \exists u\in \{0,1,\dots ,n-1\},a=mu\mathrm{mod}n\\ & \iff \exists u\in \mathbb{Z},a=mu\mathrm{mod}n\\ & \iff \exists u,v\in \mathbb{Z},a=um+vn\\ & \iff \gcd (m,n)\mid a,\end{array}$$ where the last equivalence follows from Bézout's lemma.

Hence, letting $d=\gcd (m,n),$ we see that $m{\mathbb{Z}}_n$ is the subset of ${\mathbb{Z}}_n$ containing multiples of $d,$ i.e., $$m{\mathbb{Z}}_n=\{[[kd]]\mid k=0,\dots ,n/d-1\}=d{\mathbb{Z}}_n.$$ In particular, $m{\mathbb{Z}}_n$ has order $n/d$ and index $d.$ (As we will see shorty, $m{\mathbb{Z}}_n$ being cyclic, one has $m{\mathbb{Z}}_n\cong {\mathbb{Z}}_{n/d}.$)

Again, we can show that these are in fact the only subgroups of ${\mathbb{Z}}_n.$

Proposition 5.25. Let $n\in \mathbb{N}$ and $\mathbb{G}$ be a subgroup of ${\mathbb{Z}}_n.$ Then there is a unique $d\in \mathbb{N}$ such that $d\mid n$ and $\mathbb{G}=d{\mathbb{Z}}_n.$

Proof

Let $\mathbb{G}$ be a subgroup of ${\mathbb{Z}}_n.$ Let us prove existence first. Let $$\mathbb{H}:=\{a+kn\mid [[a]]\in \mathbb{G},k\in \mathbb{Z}\}.$$ Then $\mathbb{H}$ is a subgroup of $\mathbb{Z}:$ it is clearly non-empty and for $b,b^{\prime }\in \mathbb{H},$ $b=a+kn$ and $b^{\prime }=a^{\prime }+k^{\prime }n,$ one has $$\begin{array}{rlr}b-b^{\prime }& =(a-a^{\prime })+(k-k^{\prime })n& \\ & =(a-a^{\prime }\mathrm{mod}n)+k^{\prime \prime }n& \text{for some k′′∈Z},\end{array}$$ hence $b-b^{\prime }\in \mathbb{H}.$ Thus, there exists $d\in \mathbb{N}$ such that $\mathbb{H}=d\mathbb{Z}.$ Moreover, since $0\in \mathbb{G},$ $n\in \mathbb{H}$ and hence $d\mid n.$ Since $\mathbb{G}=\{[[a]]\mid a\in \mathbb{H}\cap \{0,\dots ,n-1\}\},$ it follows that $\mathbb{G}=d{\mathbb{Z}}_n.$

Let us now prove uniqueness. Assume that $\mathbb{G}=d{\mathbb{Z}}_n=d^{\prime }{\mathbb{Z}}_n$ for $d,d^{\prime }\in \mathbb{N}$ with $d$ and $d^{\prime }$ dividing $n.$ Since $[[d]]\in d{\mathbb{Z}}_n,$ this implies $[[d]]\in d^{\prime }{\mathbb{Z}}_n=\{[[k{d}^{\prime }]]\mid k=0,\dots ,n/d^{\prime }-1\}$ and hence $d^{\prime }\mid d.$ Conversely, $d\mid d^{\prime }$ and hence $d=d^{\prime }$ since $d$ and $d^{\prime }$ are in $\mathbb{N}.$

We can now prove the following two "structure theorems" stating that, up to isomorphism, $\mathbb{Z}$ and ${\mathbb{Z}}_n$ are the only cyclic groups of infinite, resp. finite order $n.$

Theorem 5.3 (Fundamental Theorem of Cyclic Groups). Let $\mathbb{G}$ be a cyclic group. Then:

• If $\mathbb{G}$ has infinite order, then it is isomorphic to $\mathbb{Z}$ and the subgroups of $\mathbb{G}$ are exactly the subsets ${\mathbb{G}}^n:=\{a^n\mid a\in \mathbb{G}\}$ for $n\in \mathbb{N};$
• If $\mathbb{G}$ has finite order $n,$ then it is isomorphic to ${\mathbb{Z}}_n$ and the subgroups of $\mathbb{G}$ are exactly the subsets ${\mathbb{G}}^d:=\{a^d\mid a\in \mathbb{G}\}$ for $d\in \mathbb{N}$ such that $d\mid n.$ In particular, $\mathbb{G}$ has exactly one subgroup of order $d$ for each divisor $d$ of $n,$ namely ${\mathbb{G}}^{n/d}.$

Proof

Let $\mathbb{G}$ be a cyclic group and $g$ be a generator of $\mathbb{G}.$ Consider the mapping $f:\mathbb{Z}\to \mathbb{G}$ defined by $f(k)=g^k.$ Then $f$ is a group homomorphism since $f(k+\ell )=g^{k+\ell }=g^k{g}^{\ell }=f(k)f(\ell ).$ It is clearly surjective since $g$ is a generator of $\mathbb{G}.$

Consider first the case where $\mathbb{G}$ has infinite order. Let us show that $f$ is injective. Assume that $f(k)=f(\ell )$ for distinct integers $k$ and $\ell$ with $k<\ell .$ Then $f(\ell -k)=g^{\ell -k}=e,$ contradicting the fact that $g$ has infinite order. Hence, $f$ is an isomorphism from $\mathbb{Z}$ to $\mathbb{G}.$ Since the subgroups of $\mathbb{Z}$ are exactly $n\mathbb{Z}$ for $n\in \mathbb{N},$ the subgroups of $\mathbb{G}$ are exactly $$\begin{array}{rl}f(n\mathbb{Z})& =\{g^k\mid k\in n\mathbb{Z}\}\\ & =\{g^{kn}\mid k\in \mathbb{Z}\}\\ & =\{a^n\mid a\in \mathbb{G}\},\end{array}$$ where the last equality follows from $g$ being a generator and hence $\mathbb{G}=\{g^k\mid k\in \mathbb{Z}\}.$

Consider now the case where $\mathbb{G}$ has finite order $n.$ Let us show that $\ker (f)=n\mathbb{Z}.$ Since $g$ has order $n,$ by Proposition 5.16, for every $k\in \mathbb{Z},$ $g^k=e\iff k\mid n,$ which exactly means that $k\in \ker (f)\iff k\in n\mathbb{Z}.$ Hence, $\ker (f)=n\mathbb{Z}.$ By the First Isomorphism Theorem, $\mathrm{im}(f)=\mathbb{G}\cong \mathbb{Z}/n\mathbb{Z}\cong {\mathbb{Z}}_n.$

Let $\bar{f}:{\mathbb{Z}}_n\to \mathbb{G}$ be the isomorphism defined by $\bar{f}([[k]])=g^k.$ Since the subgroups of ${\mathbb{Z}}_n$ are exactly $d{\mathbb{Z}}_n$ for $d\in \mathbb{N}$ such that $d\mid n,$ the subgroups of $\mathbb{G}$ are exactly $$\begin{array}{rl}\bar{f}(d{\mathbb{Z}}_n)& =\{g^k\mid [[k]]\in d{\mathbb{Z}}_n\}\\ & =\{g^{kd}\mid k=0,\dots ,n-1\}\\ & =\{a^d\mid a\in \mathbb{G}\}.\end{array}$$

Cauchy's Theorem for Abelian Groups

Lagrange's theorem states that the order of a subgroup of a finite group divides the order of the group. Conversely, given a divisor $d$ of the order of the group, does there always exist a subgroup of order $d$? A group where this property holds is called a converse Lagrange theorem (CLT) group. The answer is no in general. However, there are specific cases where the existence of a subgroup is guaranteed. Cauchy's theorem states that for every group $\mathbb{G}$ (non-necessarily abelian) of finite order and every prime divisor $p$ of $\left|\mathbb{G}\right|,$ $\mathbb{G}$ has a subgroup of order $p.$ Cauchy's theorem is a special case of Sylow's (first) theorem.

Here, we will only prove it in the easier case where $\mathbb{G}$ is abelian. Actually, a more general result (that will follow easily from the fundamental theorem of finite abelian groups) is that any finite abelian group is CLT. In other words, for a finite abelian group of order $n,$ the existence of a subgroup of order $d$ is guaranteed for any divisor $d$ of $n,$ not only for prime divisors.

Theorem 5.4 (Cauchy's Theorem, Abelian Case). Let $\mathbb{G}$ be an abelian group of finite order $n.$ Then, for every prime divisor $p$ of $n,$ there exists a subgroup of $\mathbb{G}$ of order $p$ (or, equivalently, there exists an element of $\mathbb{G}$ of order $p).$

Proof

The equivalence between the two conclusions follows from the fact that a group of prime order is necessarily cyclic.

Let $\{a_1,\dots ,a_r\}$ be a generating set of $\mathbb{G}$ and for $i\in \{1,\dots ,r\}$ let $n_i$ denote the order of $a_i.$ Consider the mapping $f:⟨a_1⟩\times \cdots \times ⟨a_r⟩\to \mathbb{G}$ defined by $f(x_1,\dots ,x_r)=x_1\cdots x_r.$ Since $\mathbb{G}$ is abelian, it is a group homomorphism. Moreover, since $\{a_1,\dots ,a_r\}$ is a generating set, $f$ is surjective (indeed, by definition of a generating set of an abelian group, any element $y\in \mathbb{G}$ can be written as $y=a_1^{k_1}\cdots a_r^{k_r}$ for some integers $k_1,\dots ,k_r\in \mathbb{Z}$ and for each $i\in \{1,\dots ,r\},$ $a_i^{k_i}\in ⟨a_i⟩).$ By the First Isomorphism Theorem, $\mathbb{G}$ is isomorphic to $(⟨a_1⟩\times \cdots \times ⟨a_r⟩)/\ker (f),$ which implies that $$\begin{array}{rl}\left|\mathbb{G}\right|\cdot \left|\ker (f)\right|& =\left|⟨a_1⟩\times \cdots \times ⟨a_r⟩\right|\\ & =n_1\cdots n_r,\end{array}$$ and hence $n=\left|\mathbb{G}\right|$ divides $n_1\cdots n_r.$

Let $p$ be a prime divisor of $n.$ Then $p$ divides $n_1\cdots n_r$ and hence $p$ divides $n_i$ for some $i\in \{1,\dots ,r\}.$ Then we can write $n_i=kp$ and by Proposition 5.17, $a_i^k$ has order $n_i/\gcd (n_i,k)=n_i/k=p,$ which concludes the proof.

Exponent of a Group

Let $\mathbb{G}$ be a group. Consider the subset of $\mathbb{Z}$ defined as $$\{k\in \mathbb{Z}\mid \forall a\in \mathbb{G},a^k=e\}.$$ One can easily check that this is a subgroup of $\mathbb{Z}.$ Hence, by Proposition 5.24, there is a unique integer $m\in \mathbb{N}$ such that this subgroup is equal to $m\mathbb{Z}.$ This integer $m$ is called the exponent of $\mathbb{G}.$ Equivalently, it is defined as the smallest positive integer $m\ge 1$ such that $\forall g\in \mathbb{G},$ $g^m=e.$ If no such integer exists, depending on the convention, $\mathbb{G}$ is said to have exponent 0 or infinite exponent. A finite group of order $n$ necessarily has finite exponent $m$ satisfying $m\mid n$ (since by Proposition 5.15, $a^n=e$ for every $a\in \mathbb{G}$ and hence $n\in m\mathbb{Z}).$ Moreover, the order of any group element divides $m$ by Proposition 5.16. Conversely, a group with infinite exponent necessarily has infinite order. However, a group with finite exponent is not necessarily finite.

In the following, we prove that an abelian group with finite exponent $m$ always contains an element of order $m.$ This will be a key lemma for proving the fundamental theorem of finite abelian groups. Note that none of the three following propositions holds for a non-abelian group.

Proposition 5.26. Let $\mathbb{G}$ be an abelian group and $a_1$ and $a_2$ be two elements of respective order $n_1$ and $n_2$ such that $\gcd (n_1,n_2)=1.$ Then the order of $a_1{a}_2$ is $n_1{n}_2.$ More generally, if $a_1,\dots ,a_r$ are $r$ group elements of respective orders $n_1,\dots ,n_r$ such that $\gcd (n_1,\dots ,n_r)=1,$ then the order of $a_1\cdots a_r$ is $n_1\cdots n_r.$

Proof

Let $n$ be the order of $a_1{a}_2.$ Since $(a_1{a}_2{)}^{n_1{n}_2}=(a_1^{n_1}{)}^{n_2}(a_2^{n_2}{)}^{n_1}=e,$ by Proposition 5.16, we have $n\mid n_1{n}_2.$

On the other hand, since $(a_1{a}_2{)}^n=e,$ one has $a_1^n=a_2^{-n}$ and hence $a_1^n\in ⟨a_2⟩.$ This implies that $(a_1^n{)}^{n_2}=a_1^{n{n}_2}=e,$ hence $n_1\mid n{n}_2.$ But since $\gcd (n_1,n_2)=1,$ $n_1\mid n.$ Symmetrically, one also has $n_2\mid n.$ Since $\gcd (n_1,n_2)=1,$ this implies $n_1{n}_2\mid n$ and hence $n=n_1{n}_2.$ The generalization can be proved by induction on $r.$

Proposition 5.27. Let $\mathbb{G}$ be an abelian group and $a_1$ and $a_2$ be two elements of respective order $n_1$ and $n_2.$ Then there exists an element of $\mathbb{G}$ of order $\mathrm{lcm}(n_1,n_2).$

Proof

Let $p_1^{r_1}\cdots p_t^{r_t}$ be the prime factor decomposition of $\mathrm{lcm}(n_1,n_2).$ For each $i\in \{1,\dots ,t\},$ $p_i^{r_i}$ divides either $n_1$ or $n_2.$ Say it divides $n_1$ (the reasoning is similar if it divides $n_2).$ Then, by Proposition 5.17, $a_1^{n_1/p_i^{r_i}}$ has order $n_1/\gcd (n_1,n_1/p_i^{r_i})=p_i^{r_i}.$ Hence, for each $i\in \{1,\dots ,t\},$ there exists an element $b_i$ of order $p_i^{r_i}.$ By Proposition 5.26, $b_1\cdots b_r$ has order $p_1^{r_1}\cdots p_t^{r_t}=\mathrm{lcm}(n_1,n_2).$

Proposition 5.28. Let $\mathbb{G}$ be an abelian group of finite exponent $m.$ Then there exists an element of $\mathbb{G}$ of order $m.$

Proof

By Proposition 5.16, the order of any group element divides $m.$ In particular, all group elements have order at most $m$ and hence there exists a group element of maximal order $m^{\prime }\le m.$ Assume towards a contradiction that $m^{\prime }<m.$ If the order of every group element divides $m^{\prime },$ then for every $a\in \mathbb{G},$ $a^{m^{\prime }}=e,$ contradicting the minimality of $m.$ Otherwise, assume that there is a group element of order $m^{\prime \prime }$ which does not divide $m^{\prime }.$ Then, by Proposition 5.27, there exists an element of order $\mathrm{lcm}(m^{\prime },m^{\prime \prime })>m^{\prime }$ contradicting the maximality of $m^{\prime }.$ Hence, it must be that $m=m^{\prime },$ which concludes the proof.

As a direct corollary, we have that a finite abelian group is cyclic if and only if its order is equal to its exponent.

Structure Theorem for Finite Abelian Groups

This section presents the fundamental theorem of finite abelian groups, sometimes called Kronecker theorem. As we will see, finite abelian groups can be "decomposed" in two ways. The equivalence between these two decompositions relies on the following theorem.

Theorem 5.5 (Chinese Remainder Theorem for Groups). Let $n_1$ and $n_2$ be two positive integers. Then $${\mathbb{Z}}_{n_1}\times {\mathbb{Z}}_{n_2}\cong {\mathbb{Z}}_{n_1{n}_2}⟺\gcd (n_1,n_2)=1.$$

Proof

Assume that $\gcd (n_1,n_2)=1.$ Consider the mapping $f:\mathbb{Z}\to {\mathbb{Z}}_{n_1}\times {\mathbb{Z}}_{n_2}$ defined by $f(z)=(z\mathrm{mod}{n}_1,z\mathrm{mod}{n}_2).$ One can easily check that $f$ is a group homomorphism. Moreover, $z\in \ker (f)\iff (n_1\mid z)\wedge (n_2\mid z)\iff n_1{n}_2\mid z,$ where the last equivalence follows from $\gcd (n_1,n_2)=1.$ Hence, $\ker (f)=n_1{n}_2\mathbb{Z}.$ By the First Isomorphism Theorem, ${\mathbb{Z}}_{n_1{n}_2}\cong \mathbb{Z}/n_1{n}_2\mathbb{Z}$ is isomorphic to $\mathrm{im}(f).$ In particular, $\left|\mathrm{im}(f)\right|=\left|{\mathbb{Z}}_{n_1{n}_2}\right|=n_1{n}_2=\left|{\mathbb{Z}}_{n_1}\times {\mathbb{Z}}_{n_2}\right|,$ hence $\mathrm{im}(f)={\mathbb{Z}}_{n_1}\times {\mathbb{Z}}_{n_2}.$ Thus, ${\mathbb{Z}}_{n_1{n}_2}\cong {\mathbb{Z}}_{n_1}\times {\mathbb{Z}}_{n_2}.$

Conversely, assume that $\gcd (n_1,n_2)=d>1.$ By Proposition 5.22, ${\mathbb{Z}}_{n_1}\times {\mathbb{Z}}_{n_2}$ is not cyclic. As ${\mathbb{Z}}_{n_1{n}_2}$ is cyclic, these two groups cannot be isomorphic.

Theorem 5.6 (Fundamental Theorem of Finite Abelian Groups). Let $\mathbb{G}$ be a non-trivial finite abelian group. Then:

• (primary decomposition): $\mathbb{G}$ is isomorphic to a direct product of cyclic groups $${\mathbb{Z}}_{p_1^{r_1}}\times \cdots \times {\mathbb{Z}}_{p_t^{r_t}},$$ where the $p_i$'s are (not necessarily distinct) primes and the $r_i$'s are positive integers. This decomposition is unique up to the order of factors. The prime powers $p_1^{r_1},\dots ,p_t^{r_t}$ are called the elementary divisors of $\mathbb{G}.$
• (invariant factor decomposition): $\mathbb{G}$ is isomorphic to a direct product of cyclic groups $${\mathbb{Z}}_{n_1}\times \cdots \times {\mathbb{Z}}_{n_{\ell }},$$ where the $n_i$'s are positive integers such that for $i=1,\dots ,\ell -1,$ $n_i\mid n_{i+1}.$ This decomposition is unique and $n_{\ell }$ is the exponent of the group. The integers $n_1,\dots ,n_{\ell }$ are called the invariant factors of $\mathbb{G}.$

Proof

TODO

Consider for example ${\mathbb{Z}}_6\times {\mathbb{Z}}_{15}.$ What are the primary and invariant factor decompositions of this group? By the Chinese remainder theorem, we have $$\begin{array}{rl}{\mathbb{Z}}_6\times {\mathbb{Z}}_{15}& ={\mathbb{Z}}_{2\times 3}\times {\mathbb{Z}}_{3\times 5}\\ & \cong {\mathbb{Z}}_2\times {\mathbb{Z}}_3\times {\mathbb{Z}}_3\times {\mathbb{Z}}_5\\ & \cong {\mathbb{Z}}_3\times {\mathbb{Z}}_{30}.\end{array}$$ The penultimate form is the primary decomposition, while the last form is the invariant factor decomposition.

The smallest abelian non-cyclic group is ${\mathbb{Z}}_2\times {\mathbb{Z}}_2$ of order 4, usually called the Klein group.

Proposition 5.29. A finite abelian group is cyclic if and only if $\ell =1$ in its invariant factor decomposition.

For an integer $n,$ one may ask how many different abelian groups of order $n$ there are, up to isomorphism. Let $\pi$ denote the partition function defined as follows: for an integer $n,$ $\pi (n)$ is the number of distinct ways of writing $n$ as a sum of positive integers, where the order of these integers does not matter. For example, $\pi (3)=3$ since $3$ has $3$ partitions: $1+1+1,$ $1+2,$ and $3.$

Proposition 5.30 (Number of Finite Abelian Groups of Fixed Order). Let $n\ge 1$ be an integer and let its decomposition in prime factors be $n=p_1^{r_1}\cdots p_k^{r_k}.$ Then the number of abelian groups of order $n,$ up to isomorphism, is $$\pi (r_1)\cdots \pi (r_k),$$ where $\pi$ is the partition function. In particular, there is a unique abelian group of order $n$ up to isomorphism (namely ${\mathbb{Z}}_n)$ if and only if $n$ is square-free, i.e., $r_1=\cdots =r_k=1.$

For example, there is a unique (up to isomorphism) abelian group of order $15=3\times 5,$ namely ${\mathbb{Z}}_3\times {\mathbb{Z}}_5\cong {\mathbb{Z}}_{15}$ (primary/invariant factor decomposition). On the other hand, there are two (up to isomorphism) abelian groups of order $12=2^2\times 3,$ namely ${\mathbb{Z}}_4\times {\mathbb{Z}}_3\cong {\mathbb{Z}}_{12}$ and ${\mathbb{Z}}_2\times {\mathbb{Z}}_2\times {\mathbb{Z}}_3\cong {\mathbb{Z}}_2\times {\mathbb{Z}}_6.$

Structure Theorem for Finitely Generated Abelian Groups

We now consider abelian groups which are finitely generated (but not necessarily of finite order).

Let $\mathbb{G}$ be an abelian group. For $n\in {\mathbb{N}}^{\ast },$ an element $a\in \mathbb{G}$ is said to be an $n$-torsion element if $a^n=e$ (or equivalently, if $a$ has finite order $k$ dividing $n).$ An element $a\in \mathbb{G}$ is said to be a torsion element if it has finite order.

Proposition 5.31. Let $\mathbb{G}$ be an abelian group. Then the set of all $n$-torsion elements of $\mathbb{G},$ denoted $\mathbb{G}[n],$ is a subgroup called the $n$-torsion subgroup of $\mathbb{G}$ and the set of all torsion elements of $\mathbb{G},$ denoted ${\mathbb{G}}_T,$ is a subgroup called the torsion subgroup of $\mathbb{G}.$

Proof

First, $e$ is clearly an $n$-torsion element. Let $a$ and $b$ be two $n$-torsion elements. Then $(a{b}^{-1}{)}^n=a^n(b^n{)}^{-1}=e{e}^{-1}=e,$ hence $a{b}^{-1}$ is an $n$-torsion element. Hence $\mathbb{G}[n]$ is a subgroup of $\mathbb{G}$ by Proposition 5.5.

Similarly, $e$ is a torsion element. Let $a$ and $b$ be two torsion elements of order respectively $k$ and $\ell .$ Then $(a{b}^{-1}{)}^{k\ell }=a^{k\ell }(b^{\ell k}{)}^{-1}=e^{\ell }(e^k{)}^{-1}=e.$ Hence $a{b}^{-1}$ has finite order, i.e., it is a torsion element. Hence ${\mathbb{G}}_T$ is a subgroup of $\mathbb{G}.$

If $\mathbb{G}={\mathbb{G}}_T$ then $\mathbb{G}$ is called a torsion group (or periodic group). If $\mathbb{G}=\{0\}$ then $\mathbb{G}$ is said torsion-free.

Theorem 5.7 (Fundamental Theorem of Finitely Generated Abelian Groups). Let $\mathbb{G}$ be a finitely generated abelian group. Let ${\mathbb{G}}_T$ be the torsion subgroup of $\mathbb{G}.$ Then ${\mathbb{G}}_T$ is finite and abelian and there exists a free abelian subgroup $\mathbb{F}$ such that $\mathbb{G}=\mathbb{F}\times {\mathbb{G}}_T.$ In particular, there exists an integer $r\in \mathbb{N}$ (called the free rank or simply rank of $\mathbb{G})$ and integers $n_1,\dots ,n_{\ell }$ with $n_1\mid \cdots \mid n_{\ell }$ such that $$\mathbb{G}\cong {\mathbb{Z}}^r\times {\mathbb{Z}}_{n_1}\times \cdots \times {\mathbb{Z}}_{n_{\ell }}.$$ Integers $r$ and $n_1,\dots ,n_{\ell }$ are unique.

Proof

TODO

---

1: While the direct sum is the same as the direct product for a finite number of groups, this is not the case for a infinite number of groups. See this StackExchange question.

2: Sometimes cyclic is used for groups which are both monogenous and finite, which makes sense since for an infinite monogenous group such as $\mathbb{Z}$ one never "cycles back" when computing $g,g^2,\dots$