CommeUnJeu · L2 MP

Further group theory

⌚ ~67 min ▢ 8 blocks ✓ 14 exercises ➣ Prerequisites : Algebraic structures, Arithmetic in $\mathbb{Z}$

The MPSI chapter Structures algébriques usuelles built the language of groups: a set with one well-behaved law, its subgroups, and the morphisms between groups. This chapter is its direct continuation. It answers three questions left open there.
First: given a few elements of a group, what is the smallest subgroup that contains them --- the subgroup they generate? Second: two groups are especially simple, the integers $(\mathbb{Z}, +)$ and the clock-arithmetic groups $(\mathbb{Z}/n\mathbb{Z}, +)$; we describe every subgroup of $\mathbb{Z}$, and we promote $\mathbb{Z}/n\mathbb{Z}$ --- met in Arithmétique dans $\mathbb{Z}$ only as a set of residue classes --- to a genuine group. Third: to each element we attach a number, its order, measuring how long its powers take to come back to the neutral element.
The chapter has four sections. The two headline results are the classification of monogenic groups --- a group generated by a single element is, up to isomorphism, either $(\mathbb{Z}, +)$ or one $(\mathbb{Z}/n\mathbb{Z}, +)$ --- and the fact that, in a finite group, the order of every element divides the cardinal of the group.
Standing notation. $G$ denotes a group, written multiplicatively unless stated otherwise, with neutral element $1_G$; the inverse of $x$ is $x^{-1}$ and $x^n$ is its $n$-th power for $n \in \mathbb{Z}$. In additive notation the neutral is $0_G$ and $x^n$ becomes the multiple $n x$. We write $H \leq G$ for « $H$ is a subgroup of $G$ ». For $a, b \in \mathbb{Z}$, $a \wedge b$ denotes their gcd. The notions of subgroup, morphism, kernel, image and isomorphism are exactly those of Structures algébriques usuelles.

I The subgroup generated by a subset

I.1 The generated subgroup

In Structures algébriques usuelles we proved that an intersection of subgroups of $G$ --- of any family, even infinite --- is again a subgroup of $G$. That single fact lets us attach to any subset of $G$ a canonical subgroup: the smallest one that contains it. This subsection defines that subgroup; the next one describes it concretely.

Definition — Subgroup generated by a subset

Let $G$ be a group and $A \subset G$ a subset. The subgroup generated by $A$, denoted $\langle A \rangle$, is the intersection of all subgroups of $G$ containing $A$: $$ \langle A \rangle = \bigcap_{\substack{H \leq G \\ A \subset H}} H. $$ When $A = \{a_1, \dots, a_p\}$ is finite, we write $\langle a_1, \dots, a_p \rangle$; for a single element, $\langle a \rangle$.

Proposition — The generated subgroup is the smallest one

Let $G$ be a group and $A \subset G$. Then $\langle A \rangle$ is a subgroup of $G$, it contains $A$, and it is contained in every subgroup of $G$ containing $A$. In other words, $\textcolor{colorprop}{\langle A \rangle}$ \textcolor{colorprop}{is the smallest subgroup of $G$ containing $A$}, for inclusion.

Proof

Let $\mathcal{S} = \{H : H \leq G,\ A \subset H\}$ be the family of subgroups of $G$ containing $A$.

$\mathcal{S}$ is non-empty, since $G$ itself is a subgroup of $G$ containing $A$, so $G \in \mathcal{S}$. The intersection $\langle A \rangle = \bigcap_{H \in \mathcal{S}} H$ is therefore well-defined, and by the result on intersections of subgroups (Structures algébriques usuelles) it is a subgroup of $G$.
Each $H \in \mathcal{S}$ contains $A$, so the intersection contains $A$: $A \subset \langle A \rangle$.
Let $K \leq G$ with $A \subset K$. Then $K \in \mathcal{S}$, hence $\langle A \rangle = \bigcap_{H \in \mathcal{S}} H \subset K$. So $\langle A \rangle$ is contained in every subgroup containing $A$.

A subgroup containing $A$, contained in every subgroup containing $A$: $\langle A \rangle$ is the smallest one.

Example — Extreme cases

The smallest subgroup containing the empty set is $\langle \emptyset \rangle = \{1_G\}$: every subgroup contains $1_G$, and $\{1_G\}$ is itself a subgroup containing $\emptyset$, so the intersection of all subgroups containing $\emptyset$ is $\{1_G\}$. At the other extreme, $\langle G \rangle = G$, since $G$ is the only subgroup of $G$ containing $G$.

Example — The subgroup generated by one element

For a single element $a \in G$, $\langle a \rangle$ is the smallest subgroup containing $a$. In $(\mathbb{Z}, +)$, the subgroup $\langle 2 \rangle$ must contain $2$, hence $2 + 2 = 4$, the neutral $0$, the opposite $-2$, and more generally every multiple of $2$; and the set $2\mathbb{Z}$ of all multiples of $2$ is already a subgroup. So $\langle 2 \rangle = 2\mathbb{Z}$. The general description of $\langle a \rangle$ is the subject of the next subsection.

Skills to practice

Computing a generated subgroup

I.2 Description and generating subsets

The definition of $\langle A \rangle$ as an intersection is abstract: it does not say what the elements of $\langle A \rangle$ look like. The next proposition gives the concrete description --- powers of $a$ for a single element, finite products for a general subset --- and we then name the subsets large enough to fill the whole group.

Proposition — Description of the generated subgroup

Let $G$ be a group.

For $a \in G$, $\quad \textcolor{colorprop}{\langle a \rangle = \{a^k : k \in \mathbb{Z}\}}$.
For any subset $A \subset G$, $\langle A \rangle$ is the set of all finite products $x_1 x_2 \cdots x_n$ ($n \in \mathbb{N}$) where each $x_i$ is an element of $A$ or the inverse of an element of $A$; the empty product ($n = 0$) is $1_G$. In particular $\langle \emptyset \rangle = \{1_G\}$.

Proof

Each part exhibits a set, shows it is a subgroup containing the data, and shows it is contained in every subgroup containing the data; the previous Proposition then identifies it with $\langle \cdot \rangle$.

(1) Let $P = \{a^k : k \in \mathbb{Z}\}$. By the characterization of subgroups (Structures algébriques usuelles): $1_G = a^0 \in P$; and for $a^k, a^\ell \in P$, $a^k (a^\ell)^{-1} = a^{k - \ell} \in P$. So $P \leq G$, and $P$ contains $a = a^1$. Conversely, any subgroup $H$ containing $a$ is stable by product and inverse, hence contains $a^k$ for every $k \in \mathbb{Z}$, so $P \subset H$. Thus $P$ is a subgroup containing $a$ and contained in every subgroup containing $a$: $P = \langle a \rangle$.
(2) Let $W$ be the set of finite products described. $W$ is a subgroup: the empty product gives $1_G \in W$; the concatenation of two words is a word, so $W$ is stable by product; and $(x_1 \cdots x_n)^{-1} = x_n^{-1} \cdots x_1^{-1}$ is again a word in elements of $A$ and their inverses, so $W$ is stable by inversion. $W$ contains $A$ (a single element $x \in A$ is the word $x$). Conversely any subgroup $H$ containing $A$ contains every such product by stability, so $W \subset H$. Thus $W = \langle A \rangle$. When $A = \emptyset$, the only word is the empty product, so $\langle \emptyset \rangle = \{1_G\}$.

When the powers of $a$ are pairwise distinct, $\langle a \rangle$ is an unbounded two-sided chain --- a faithful copy of $\mathbb{Z}$ laid along $a$:

When instead some power of $a$ repeats an earlier one, the chain closes into a loop --- the closed-loop picture met later with the cyclic groups.

Definition — Generating subset

Let $G$ be a group. A subset $A \subset G$ generates $G$ --- and is called a generating subset of $G$ --- if $\langle A \rangle = G$, that is, if every element of $G$ is a finite product of elements of $A$ and of their inverses.

Example — Generating subsets of $\mathbb{Z}$

In $(\mathbb{Z}, +)$ --- additive notation, so « product » means « sum » and « power » means « multiple » --- the subset $\{1\}$ generates $\mathbb{Z}$: $\langle 1 \rangle = \{k \cdot 1 : k \in \mathbb{Z}\} = \mathbb{Z}$, since every integer is a multiple of $1$. Likewise $\{-1\}$ generates $\mathbb{Z}$.
The subset $\{1, 2\}$ also generates $\mathbb{Z}$, since it already contains the generating element $1$. But it is not minimal: $1$ alone suffices, so $2$ is redundant. A generating subset need not have the fewest possible elements.

Example — A group generated by a single element

Recall from Structures algébriques usuelles that $\mathbb{U}_n = \{z \in \mathbb{C}^* : z^n = 1\}$ is a subgroup of $(\mathbb{U}, \times)$, with exactly $n$ elements. Set $\omega = e^{2 i \pi / n}$. Its powers $\omega^0, \omega^1, \dots, \omega^{n-1}$ are $n$ distinct elements of $\mathbb{U}_n$, so they are all of $\mathbb{U}_n$. Hence $\langle \omega \rangle = \mathbb{U}_n$: the single element $\omega$ generates the whole group $\mathbb{U}_n$.

Method — Show that a subset generates a group

To prove that $A$ generates $G$, the standard pattern is one of:

take an arbitrary $g \in G$ and exhibit it explicitly as a finite product of elements of $A$ and of their inverses;
or show that $\langle A \rangle$ contains a subset already known to generate $G$ --- then $\langle A \rangle = G$ by the « smallest subgroup » property.

To prove instead that $A$ does not generate $G$, exhibit one subgroup of $G$ that contains $A$ but is not all of $G$: it contains $\langle A \rangle$, so $\langle A \rangle \neq G$.

Skills to practice

Identifying a generating subset

II Subgroups of $\mathbb{Z}$ and the group $\mathbb{Z}/n\mathbb{Z}$

II.1 The subgroups of $\mathbb{Z}$

In Structures algébriques usuelles, each set $n\mathbb{Z}$ of multiples of $n$ was shown to be a subgroup of $(\mathbb{Z}, +)$. We now prove the converse: there are no others. Every subgroup of $\mathbb{Z}$ is one of the $n\mathbb{Z}$. This complete description of the subgroups of $\mathbb{Z}$ is used throughout the chapter, notably in the classification of monogenic groups.

Theorem — Subgroups of $\mathbb{Z}$

For every subgroup $H$ of $(\mathbb{Z}, +)$, there exists a \textcolor{colorprop}{unique} $n \in \mathbb{N}$ such that $\textcolor{colorprop}{H = n\mathbb{Z}}$. Conversely, every $n\mathbb{Z}$ ($n \in \mathbb{N}$) is a subgroup of $(\mathbb{Z}, +)$.

Proof

The converse is the recalled MPSI fact. For the direct statement, let $H \leq (\mathbb{Z}, +)$.

Case $H = \{0\}$. Then $H = 0\mathbb{Z}$, with $n = 0$.
Case $H \neq \{0\}$. $H$ contains some $x \neq 0$; since $H$ is a subgroup it also contains $-x$, and one of $x, -x$ is positive. So $H \cap \mathbb{N}^*$ is a non-empty subset of $\mathbb{N}$; let $n$ be its smallest element. Since $n \in H$ and $H$ is a subgroup, every multiple of $n$ lies in $H$, so $n\mathbb{Z} \subset H$. Conversely, let $m \in H$. Euclidean division of $m$ by $n$ gives $m = q n + r$ with $0 \leq r < n$. Then $r = m - q n \in H$, because $m \in H$ and $q n \in n\mathbb{Z} \subset H$. If $r > 0$, then $r \in H \cap \mathbb{N}^*$ with $r < n$, contradicting the minimality of $n$. So $r = 0$ and $m = q n \in n\mathbb{Z}$. Hence $H \subset n\mathbb{Z}$, and finally $H = n\mathbb{Z}$.

Uniqueness. If $n\mathbb{Z} = n'\mathbb{Z}$ with $n, n' \in \mathbb{N}$, then $n \in n'\mathbb{Z}$ and $n' \in n\mathbb{Z}$, so $n' \mid n$ and $n \mid n'$, which forces $n = n'$ for natural numbers.

Example — The first subgroups of $\mathbb{Z}$

The smallest subgroup of $(\mathbb{Z}, +)$ is $\{0\} = 0\mathbb{Z}$; the largest is $\mathbb{Z} = 1\mathbb{Z}$. Between them, $2\mathbb{Z}$ is the subgroup of even integers, $3\mathbb{Z}$ the multiples of $3$, and so on --- and the Theorem says the list $0\mathbb{Z}, 1\mathbb{Z}, 2\mathbb{Z}, 3\mathbb{Z}, \dots$ is exhaustive.

Proposition — Inclusion of the $n\mathbb{Z}$

For $m, n \in \mathbb{N}$, $$ \textcolor{colorprop}{n\mathbb{Z} \subset m\mathbb{Z} \iff m \mid n,} $$ with the standard divisibility convention ($0 \mid n$ means $n = 0$, and every integer divides $0$).

Proof

If $n\mathbb{Z} \subset m\mathbb{Z}$, then in particular $n \in n\mathbb{Z} \subset m\mathbb{Z}$, so $n$ is a multiple of $m$, i.e. $m \mid n$. Conversely, if $m \mid n$, write $n = m k$ with $k \in \mathbb{Z}$; then any $n j \in n\mathbb{Z}$ equals $m (k j) \in m\mathbb{Z}$, so $n\mathbb{Z} \subset m\mathbb{Z}$.
The boundary cases agree with the convention: for $m = 0$, $m\mathbb{Z} = \{0\}$, and $n\mathbb{Z} \subset \{0\}$ holds exactly when $n = 0$, i.e. when $0 \mid n$; for $n = 0$, $0\mathbb{Z} = \{0\} \subset m\mathbb{Z}$ always, and indeed $m \mid 0$ always.

Example — Reading an inclusion as a divisibility

Since $2 \mid 6$ and $3 \mid 6$, we have $6\mathbb{Z} \subset 2\mathbb{Z}$ and $6\mathbb{Z} \subset 3\mathbb{Z}$: the multiples of $6$ are in particular even and divisible by $3$. On the other hand $2 \nmid 3$, so $3\mathbb{Z} \not\subset 2\mathbb{Z}$ --- indeed $3 \in 3\mathbb{Z}$ is not even.

Skills to practice

Determining the subgroups of $\mathbb{Z}$

II.2 The group $\mathbb{Z}/n\mathbb{Z}$ and its generators

In Arithmétique dans $\mathbb{Z}$, $\mathbb{Z}/n\mathbb{Z}$ appeared only as a set: the $n$ residue classes $\bar 0, \bar 1, \dots, \overline{n-1}$ modulo $n$, with the explicit note that arithmetic was done on representatives, not on classes. We now equip this set with an addition of classes and obtain a genuine group. Throughout this subsection, $n \in \mathbb{N}^*$, and $\bar a$ denotes the class of $a \in \mathbb{Z}$ modulo $n$.

Proposition — The addition of classes is well-defined

For $\bar a, \bar b \in \mathbb{Z}/n\mathbb{Z}$, the formula $\bar a + \bar b := \overline{a + b}$ does not depend on the chosen representatives: it defines an internal law on $\mathbb{Z}/n\mathbb{Z}$.

Proof

Suppose $\bar a = \overline{a'}$ and $\bar b = \overline{b'}$, i.e. $a \equiv a' \pmod n$ and $b \equiv b' \pmod n$. By the compatibility of congruence with addition (Arithmétique dans $\mathbb{Z}$), $a + b \equiv a' + b' \pmod n$, that is $\overline{a + b} = \overline{a' + b'}$. So the class $\overline{a + b}$ depends only on the classes $\bar a$ and $\bar b$, not on the representatives.

Theorem — The group $\mathbb{Z}/n\mathbb{Z}$

For every $n \in \mathbb{N}^*$, the set $\mathbb{Z}/n\mathbb{Z}$ equipped with the addition of classes is an \textcolor{colorprop}{abelian group of cardinal $n$}, with neutral element $\bar 0$ and with $-\bar a = \overline{-a}$.

Proof

The addition is well-defined by the previous Proposition. Each axiom is checked on representatives, transporting the corresponding property of $(\mathbb{Z}, +)$. For all $a, b, c \in \mathbb{Z}$: $$ \begin{aligned} (\bar a + \bar b) + \bar c &= \overline{a + b} + \bar c = \overline{(a + b) + c} && \text{(definition of the addition)} \\ &= \overline{a + (b + c)} && \text{(associativity in } \mathbb{Z}) \\ &= \bar a + \overline{b + c} = \bar a + (\bar b + \bar c) && \text{(definition of the addition).} \end{aligned} $$ So the addition is associative. It is also commutative: $\bar a + \bar b = \overline{a + b} = \overline{b + a} = \bar b + \bar a$. By that commutativity, the neutral and the inverse need only be checked on one side: $\bar 0$ is neutral, since $\bar a + \bar 0 = \overline{a + 0} = \bar a$; and $\overline{-a}$ is the inverse of $\bar a$, since $\bar a + \overline{-a} = \overline{a + (-a)} = \bar 0$. So $(\mathbb{Z}/n\mathbb{Z}, +)$ is an abelian group. Its cardinal is $n$, the number of residue classes modulo $n$ (Arithmétique dans $\mathbb{Z}$).

Because $(\mathbb{Z}/n\mathbb{Z}, +)$ is the additive group of $n$ classes, it is natural to picture it as $n$ equally spaced points on a circle, addition being a rotation by one step per unit. Here is the case $n = 6$:

Definition — Generator of $\mathbb{Z}/n\mathbb{Z}$

A class $\bar k \in \mathbb{Z}/n\mathbb{Z}$ is a generator of $\mathbb{Z}/n\mathbb{Z}$ if $\langle \bar k \rangle = \mathbb{Z}/n\mathbb{Z}$, that is, if every class is a multiple of $\bar k$ in $(\mathbb{Z}/n\mathbb{Z}, +)$.

Theorem — Generators of $\mathbb{Z}/n\mathbb{Z}$

For $n \in \mathbb{N}^*$ and $k \in \mathbb{Z}$, $$ \textcolor{colorprop}{\bar k \text{ generates } \mathbb{Z}/n\mathbb{Z} \iff k \wedge n = 1.} $$

Proof

The class $\bar 1$ generates $\mathbb{Z}/n\mathbb{Z}$, since every class $\bar a$ is the multiple $a \cdot \bar 1$. So $\langle \bar k \rangle = \mathbb{Z}/n\mathbb{Z}$ if and only if $\bar 1 \in \langle \bar k \rangle$ (then $\langle \bar k \rangle \supset \langle \bar 1 \rangle = \mathbb{Z}/n\mathbb{Z}$). Now $\langle \bar k \rangle = \{u \cdot \bar k : u \in \mathbb{Z}\} = \{\overline{u k} : u \in \mathbb{Z}\}$, so: $$ \begin{aligned} \bar k \text{ generates } \mathbb{Z}/n\mathbb{Z} &\iff \exists\, u \in \mathbb{Z},\ \overline{u k} = \bar 1 && \text{($\bar 1 \in \langle \bar k\rangle$)} \\ &\iff \exists\, u \in \mathbb{Z},\ u k \equiv 1 \pmod n && \text{(equality of classes)} \\ &\iff \exists\, u, v \in \mathbb{Z},\ u k + v n = 1 && \text{(definition of congruence)} \\ &\iff k \wedge n = 1 && \text{(Bézout's theorem).} \end{aligned} $$ The last equivalence is Bézout's theorem, recalled from Arithmétique dans $\mathbb{Z}$.

Example — Generators of $\mathbb{Z}/6\mathbb{Z}$

The generators of $\mathbb{Z}/6\mathbb{Z}$ are the classes $\bar k$ with $k \wedge 6 = 1$ for $k \in \{0, 1, 2, 3, 4, 5\}$: only $k = 1$ and $k = 5$ qualify. So $\bar 1$ and $\bar 5$ are the two generators of $\mathbb{Z}/6\mathbb{Z}$. For instance the successive multiples of $\bar 5$ are $\bar 5, \overline{10} = \bar 4, \overline{15} = \bar 3, \bar 2, \bar 1, \bar 0$ --- every class appears.

Example — Generators of $\mathbb{Z}/5\mathbb{Z}$

Since $5$ is prime, $k \wedge 5 = 1$ for every $k \in \{1, 2, 3, 4\}$, and only $\bar 0$ is left out. So every non-zero class of $\mathbb{Z}/5\mathbb{Z}$ is a generator. This is a general feature of $\mathbb{Z}/p\mathbb{Z}$ for $p$ prime.

Method — Find the generators of $\mathbb{Z}/n\mathbb{Z}$

To list the generators of $\mathbb{Z}/n\mathbb{Z}$: run through $k \in \{0, 1, \dots, n-1\}$ and keep those with $k \wedge n = 1$ --- the gcd is computed by Euclid's algorithm or read off the prime factorization of $n$. The class $\bar k$ is a generator exactly for those $k$. The count of generators is therefore the number of integers of $\{1, \dots, n\}$ coprime to $n$. The degenerate case $n = 1$ fits in: $\mathbb{Z}/1\mathbb{Z} = \{\bar 0\}$ and $0 \wedge 1 = 1$, so $\bar 0$ is its generator.

The number of generators of $\mathbb{Z}/n\mathbb{Z}$ --- the number of integers of $\{1, \dots, n\}$ coprime to $n$ --- is denoted $\varphi(n)$ and called Euler's indicator. The function $\varphi$ and its properties are studied in the next chapter, Anneaux, arithmétique et algèbres, once $\mathbb{Z}/n\mathbb{Z}$ carries its ring structure.

Skills to practice

Computing in $\mathbb{Z}/n\mathbb{Z}$ and listing its generators

III Monogenic and cyclic groups

III.1 Definition and examples

The simplest groups are those produced by a single element: every element is a power of one fixed generator. Two of the groups already met --- $(\mathbb{Z}, +)$ and $(\mathbb{Z}/n\mathbb{Z}, +)$ --- are of this kind. This subsection names them and adds the geometric example of the roots of unity; the next one shows there are no others, up to isomorphism.

Definition — Monogenic group$\virgule$ cyclic group

A group $G$ is monogenic if it is generated by a single element: there exists $a \in G$ with $G = \langle a \rangle = \{a^k : k \in \mathbb{Z}\}$; such an $a$ is a generator of $G$. A cyclic group is a monogenic group that is finite.

Proposition — A monogenic group is abelian

Every monogenic group is abelian.

Proof

Let $G = \langle a \rangle$ be monogenic. Any two elements of $G$ are powers of $a$, say $a^k$ and $a^\ell$ with $k, \ell \in \mathbb{Z}$. Then $a^k a^\ell = a^{k + \ell} = a^{\ell + k} = a^\ell a^k$. So any two elements of $G$ commute, and $G$ is abelian.

Example — The two basic monogenic groups

$(\mathbb{Z}, +)$ is monogenic and infinite: $\mathbb{Z} = \langle 1 \rangle$. For each $n \in \mathbb{N}^*$, $(\mathbb{Z}/n\mathbb{Z}, +)$ is monogenic and finite of cardinal $n$: $\mathbb{Z}/n\mathbb{Z} = \langle \bar 1 \rangle$. So $(\mathbb{Z}/n\mathbb{Z}, +)$ is cyclic, while $(\mathbb{Z}, +)$ is monogenic but not cyclic.

Proposition — The group of $n$-th roots of unity

For $n \in \mathbb{N}^*$, the group of $n$-th roots of unity $(\mathbb{U}_n, \times)$, where $\mathbb{U}_n = \{z \in \mathbb{C}^* : z^n = 1\}$, is \textcolor{colorprop}{cyclic of cardinal $n$}, generated by $e^{2 i \pi / n}$.

Proof

Set $\omega = e^{2 i \pi / n}$. For $k \in \mathbb{Z}$, $(\omega^k)^n = (\omega^n)^k = 1^k = 1$, so $\omega^k \in \mathbb{U}_n$; thus $\langle \omega \rangle \subset \mathbb{U}_n$. The $n$ elements $\omega^0, \omega^1, \dots, \omega^{n-1}$ are pairwise distinct (their arguments $2 k \pi / n$ for $0 \leq k < n$ are pairwise distinct modulo $2\pi$), and $\mathbb{U}_n$ has exactly $n$ elements (Structures algébriques usuelles). Hence $\{\omega^0, \dots, \omega^{n-1}\} = \mathbb{U}_n$, so $\langle \omega \rangle = \mathbb{U}_n$. Therefore $\mathbb{U}_n$ is monogenic and finite, i.e. cyclic, of cardinal $n$, generated by $\omega$.

Geometrically, $\mathbb{U}_n$ is the set of vertices of a regular $n$-gon inscribed in the unit circle, the generator $\omega = e^{2 i \pi / n}$ being the first vertex after $1$. Here is $\mathbb{U}_6$:

Skills to practice

Recognising a monogenic or cyclic group

III.2 Classification of monogenic groups

Every monogenic group is, up to isomorphism, a group already known: $(\mathbb{Z}, +)$ when infinite, $(\mathbb{Z}/n\mathbb{Z}, +)$ when finite of cardinal $n$. The proof builds a single morphism out of the generator and reads its kernel through the description of the subgroups of $\mathbb{Z}$ established above.

Theorem — Classification of monogenic groups

Let $G$ be a monogenic group.

If $G$ is infinite, then $\textcolor{colorprop}{G \cong (\mathbb{Z}, +)}$.
If $G$ is finite of cardinal $n$, then $\textcolor{colorprop}{G \cong (\mathbb{Z}/n\mathbb{Z}, +)}$.

Proof

Write $G = \langle a \rangle$ and consider the map $\varphi_a : \mathbb{Z} \to G,\ k \mapsto a^k$. It is a group morphism from $(\mathbb{Z}, +)$ to $G$, since $\varphi_a(k + \ell) = a^{k + \ell} = a^k a^\ell = \varphi_a(k) \varphi_a(\ell)$, and it is surjective because $G = \langle a \rangle = \{a^k : k \in \mathbb{Z}\}$. Its kernel $\operatorname{Ker} \varphi_a = \{k \in \mathbb{Z} : a^k = 1_G\}$ is a subgroup of $(\mathbb{Z}, +)$ (Structures algébriques usuelles), hence equals $m\mathbb{Z}$ for a unique $m \in \mathbb{N}$, by the Theorem on subgroups of $\mathbb{Z}$ proved above.

Case $m = 0$. Then $\operatorname{Ker} \varphi_a = \{0\}$, so $\varphi_a$ is injective (injectivity criterion, Structures algébriques usuelles). Being also surjective, $\varphi_a$ is a bijective morphism, hence an isomorphism: $G \cong (\mathbb{Z}, +)$. In particular $G$ is infinite.
Case $m \geq 1$. Define $\psi : \mathbb{Z}/m\mathbb{Z} \to G,\ \bar k \mapsto a^k$. It is well-defined: if $\bar k = \overline{k'}$, then $k - k' \in m\mathbb{Z} = \operatorname{Ker} \varphi_a$, so $a^{k - k'} = 1_G$, hence $a^k = a^{k'}$. It is a morphism: $\psi(\bar k + \overline{\ell}) = \psi(\overline{k + \ell}) = a^{k + \ell} = a^k a^\ell = \psi(\bar k) \psi(\overline{\ell})$. It is surjective, since $\varphi_a$ already is and $\psi$ has the same image. It is injective: if $\psi(\bar k) = 1_G$, then $a^k = 1_G$, so $k \in \operatorname{Ker} \varphi_a = m\mathbb{Z}$, i.e. $\bar k = \bar 0$. So $\psi$ is an isomorphism: $G \cong (\mathbb{Z}/m\mathbb{Z}, +)$, and $G$ is finite of cardinal $m$.

The two cases are exclusive: $m = 0$ gives an infinite $G$, $m \geq 1$ a finite one. So if $G$ is infinite then $m = 0$ and $G \cong (\mathbb{Z}, +)$; if $G$ is finite of cardinal $n$ then $m \geq 1$ and $n = \operatorname{card} G = m$, hence $G \cong (\mathbb{Z}/n\mathbb{Z}, +)$.

Example — The roots of unity are a copy of $\mathbb{Z}/n\mathbb{Z}$

$(\mathbb{U}_n, \times)$ is cyclic of cardinal $n$, so by the classification $(\mathbb{U}_n, \times) \cong (\mathbb{Z}/n\mathbb{Z}, +)$. An explicit isomorphism is $\bar k \mapsto e^{2 i k \pi / n}$: it turns the addition of classes into the multiplication of roots of unity.

Method — Use the classification

Faced with a monogenic group $G$, fix a generator $a$ so that $G = \langle a \rangle$; the classification then reduces every structural question to the two model groups. Decide first whether $G$ is infinite or finite. If finite of cardinal $n$, transport the question to $(\mathbb{Z}/n\mathbb{Z}, +)$ via the isomorphism $\bar k \mapsto a^k$; if infinite, transport it to $(\mathbb{Z}, +)$ via $k \mapsto a^k$. For instance, the generators of $G$ correspond exactly to the generators of the model --- $\pm 1$ for $\mathbb{Z}$, the classes $\bar k$ with $k \wedge n = 1$ for $\mathbb{Z}/n\mathbb{Z}$.

The classification has a vivid geometric reading. An infinite monogenic group is an unbounded chain --- a copy of $\mathbb{Z}$; a finite one of cardinal $n$ is a closed cycle of $n$ steps --- a copy of $\mathbb{Z}/n\mathbb{Z}$. The two models, for $n = 6$:

Skills to practice

Applying the classification

IV The order of an element

IV.1 Definition and characterisation

To each element of a group we now attach a number that measures it: the order. The word « order » already appeared in MPSI for the cardinal of a finite group (the order of $\mathfrak{S}_n$ is $n!$); here it is the order of an element, a different notion --- though the two are linked, as the next subsection shows. The order of $a$ counts the steps its powers take to return to the neutral.

Definition — Order of an element

Let $G$ be a group and $a \in G$. The element $a$ has finite order if there exists $n \in \mathbb{N}^*$ with $a^n = 1_G$; the order of $a$ is then the smallest such integer, denoted $\operatorname{ord}(a)$. Otherwise $a$ has infinite order. In additive notation, the defining condition $a^n = 1_G$ reads $n a = 0_G$.

Proposition — Order and the generated subgroup

Let $G$ be a group and $a \in G$. Then $a$ has finite order if and only if $\langle a \rangle$ is finite, and in that case $$ \textcolor{colorprop}{\operatorname{ord}(a) = \operatorname{card} \langle a \rangle.} $$ If $a$ has infinite order, $\langle a \rangle$ is infinite.

Proof

$a$ of finite order $d$. For any $k \in \mathbb{Z}$, Euclidean division gives $k = q d + r$ with $0 \leq r < d$, so $a^k = (a^d)^q a^r = a^r$. Hence $\langle a \rangle = \{a^k : k \in \mathbb{Z}\} = \{1_G, a, \dots, a^{d-1}\}$. These $d$ elements are pairwise distinct: if $a^i = a^j$ with $0 \leq i \leq j < d$, then $a^{j - i} = 1_G$ with $0 \leq j - i < d$, and the minimality of $d$ forces $j - i = 0$. So $\langle a \rangle$ is finite with $\operatorname{card} \langle a \rangle = d = \operatorname{ord}(a)$.
$a$ of infinite order. The powers $a^k$ ($k \in \mathbb{Z}$) are pairwise distinct: if $a^i = a^j$ with $i < j$, then $a^{j - i} = 1_G$ with $j - i \in \mathbb{N}^*$, so $a$ would have finite order --- a contradiction. So $\langle a \rangle$ is infinite.

The two cases are exhaustive, so $a$ has finite order if and only if $\langle a \rangle$ is finite.

Example — Orders in standard groups

In $(\mathbb{C}^*, \times)$, take $j = e^{2 i \pi / 3}$. Then $j^3 = 1$, while $j^1 = j \neq 1$ and $j^2 \neq 1$; so $\operatorname{ord}(j) = 3$. A transposition $\tau \in \mathfrak{S}_n$ satisfies $\tau^2 = \operatorname{id}$ and $\tau \neq \operatorname{id}$, so $\operatorname{ord}(\tau) = 2$. The neutral element of any group has order $1$, and it is the only element of order $1$.

Example — A finite order and an infinite order

In $(\mathbb{Z}/6\mathbb{Z}, +)$, the successive multiples of $\bar 2$ are $\bar 2$, $\bar 2 + \bar 2 = \bar 4$, $\bar 4 + \bar 2 = \bar 6 = \bar 0$. So $3 \cdot \bar 2 = \bar 0$ while $1 \cdot \bar 2 = \bar 2 \neq \bar 0$ and $2 \cdot \bar 2 = \bar 4 \neq \bar 0$: thus $\operatorname{ord}(\bar 2) = 3$. By contrast, in $(\mathbb{Z}, +)$ every $k \neq 0$ has infinite order, since $n k \neq 0$ for all $n \in \mathbb{N}^*$.

Proposition — Powers equal to the neutral

Let $a \in G$ have finite order $d$. Then for every $n \in \mathbb{Z}$, $$ \textcolor{colorprop}{a^n = 1_G \iff d \mid n.} $$

Proof

Euclidean division of $n$ by $d$ gives $n = q d + r$ with $0 \leq r < d$, so $$ a^n = a^{q d + r} = (a^d)^q\, a^r = 1_G^q\, a^r = a^r. $$ Hence $a^n = 1_G \iff a^r = 1_G$. Since $0 \leq r < d$ and $d$ is the smallest positive integer with $a^d = 1_G$, the equality $a^r = 1_G$ holds if and only if $r = 0$, i.e. if and only if $d \mid n$.

Method — Compute the order of an element

To find $\operatorname{ord}(a)$:

when $a$ is known to have finite order --- for instance when $a$ lies in a finite group --- compute the successive powers $a, a^2, a^3, \dots$; they eventually reach $1_G$, and the first exponent giving $1_G$ is the order;
or, if some power $a^k = 1_G$ is already known, the order divides $k$ by the previous Proposition --- so it is enough to test the divisors of $k$, from smallest to largest, and keep the first $d$ with $a^d = 1_G$.

Skills to practice

Computing the order of an element

IV.2 The order divides the cardinal of the group

In a finite group, the order of an element cannot be arbitrary: it is constrained by the cardinal of the group. This is the link, announced earlier, between the two meanings of the word « order ».

Theorem — The order divides the cardinal

Let $G$ be a finite group. Then the order of every element of $G$ divides $\operatorname{card} G$. Two regimes. When $G$ is commutative, the result is proved below. When $G$ is non-commutative, the result still holds but is admitted here --- its proof is not required by the program. The Proposition and the Example that follow rely on this admitted general form.

Proof

Assume $G$ commutative, and let $N = \operatorname{card} G$ and $a \in G$. Since $G$ is commutative, the product of all the elements of $G$ does not depend on the order of the factors. The map $g \mapsto a g$ is a bijection of $G$ (its inverse is $g \mapsto a^{-1} g$), so it permutes the elements of $G$, and that product is therefore unchanged when each factor $g$ is replaced by $a g$: $$ \begin{aligned} \prod_{g \in G} g &= \prod_{g \in G} (a g) && \text{($g \mapsto a g$ permutes } G) \\ &= a^{N} \prod_{g \in G} g && \text{($G$ commutative, } N \text{ factors } a). \end{aligned} $$ The element $\prod_{g \in G} g$ belongs to the group $G$, hence is invertible; cancelling it gives $a^{N} = 1_G$. Since $\langle a \rangle \subset G$ is finite, $a$ has finite order, so the Proposition « powers equal to the neutral » applies: $a^N = 1_G$ means $\operatorname{ord}(a) \mid N$, that is $\operatorname{ord}(a) \mid \operatorname{card} G$.
The non-commutative case is not proved here --- its proof is not required by the program --- but the statement itself remains a valid result, usable freely.

Proposition — Power equal to the neutral in a finite group

In a finite group $G$ of cardinal $n$, $a^n = 1_G$ for every $a \in G$.

Proof

Let $a \in G$ and $d = \operatorname{ord}(a)$ (finite, since $\langle a \rangle \subset G$ is finite). By the Theorem, $d \mid n$, so $n = d e$ for some $e \in \mathbb{N}$. Then $a^n = (a^d)^e = 1_G^e = 1_G$. This uses the Theorem in its general form, hence --- when $G$ is not known to be commutative --- the admitted non-commutative case.

Example — A group of prime cardinal is cyclic

Let $G$ be a group of prime cardinal $p$. Since $p \geq 2$, pick $a \in G$ with $a \neq 1_G$. The order of $a$ divides $p$ (Theorem, general form), so $\operatorname{ord}(a) \in \{1, p\}$; and $\operatorname{ord}(a) \neq 1$ since $a \neq 1_G$. Hence $\operatorname{ord}(a) = p$, so $\langle a \rangle$ has $p$ elements, i.e. $\langle a \rangle = G$. Therefore $G$ is monogenic and finite: $G$ is cyclic.

Going further

The Proposition $a^n = 1_G$ in a group of cardinal $n$ is the gateway to two classical arithmetic results. Once $\mathbb{Z}/n\mathbb{Z}$ is given its ring structure --- the subject of the next chapter, Anneaux, arithmétique et algèbres --- its invertible elements form a finite group of cardinal $\varphi(n)$, and applying the Proposition there yields Euler's theorem $a^{\varphi(n)} \equiv 1 \pmod n$ for $a \wedge n = 1$, of which Fermat's little theorem is the case $n$ prime.

Skills to practice

Exploiting the order-cardinal link