HT2026 Groups & Group Actions Lecture Notes

Remaining TODOs: 4

1. Groups

Definition 1.1

Let $𝑆$ be a set. A binary operation on $𝑆$ is a function $* : 𝑆 \times 𝑆 \to 𝑆$ .

We define $𝑎 * 𝑏 ≔ * (𝑎, 𝑏)$ .

Remark 1.2

*

is understood implicitly, we often write

𝑎 𝑏

for

𝑎 * 𝑏

Definition 1.3

*

admits an identity element if

\exists 𝑒 \in 𝑆

s.t.

𝑎 * 𝑒 = 𝑎 = 𝑒 * 𝑎

\forall 𝑎 \in 𝑆

Definition 1.4

Suppose that

𝑒

is an identity element, then inverses exist for

(𝑆, *)

\forall 𝑎 \in 𝑆

\exists 𝑏 \in 𝑆

s.t.

𝑎 * 𝑏 = 𝑒 = 𝑏 * 𝑎

Definition 1.5

A group is a pair

(𝐺, *)

where

* : 𝐺 \times 𝐺 \to 𝐺

is a binary operation which is associative, admits an identity, and for which inverses exist.

Definition 1.6

𝐺

is an abelian group if

*

is commutative.

Lemma 1.7

Let $*$ be a binary operation on $𝑆$ .

If $𝑒_{1}, 𝑒_{2}$ are identity elements, then $𝑒_{1} = 𝑒_{2}$ .
If $𝑒 \in 𝑆$ is an identity element, $𝑎 \in 𝑆$ , $*$ is associative, and $𝑏_{1}, 𝑏_{2}$ are inverses of $𝑎$ under $*$ , then $𝑏_{1} = 𝑏_{2}$ .

Proof.

$𝑒_{1} = 𝑒_{1} * 𝑒_{2} = 𝑒_{2}$
$\begin{aligned} 𝑏_{1} & \overset{(id)}{=} & 𝑏_{1} * 𝑒 \\ \overset{(inv)}{=} & 𝑏_{1} * (𝑎 * 𝑏_{2}) \\ \overset{(assoc)}{=} & (𝑏_{1} * 𝑎) * 𝑏_{2} \\ \overset{(inv)}{=} & 𝑒 * 𝑏_{2} \\ \overset{(id)}{=} & 𝑏_{2} \end{aligned}$

⁠ $□$

Definition 1.8

Let

(𝑆, *)

be a set with a binary operation, which admits inverses, then

\forall 𝑎 \in 𝑆

, we write

𝑎^{- 1}

to mean the inverse of

𝑎

Remark 1.9

- 𝑎

is also commonly used to denote the inverse of

𝑎

(𝑆, +)

is an abelian group.

Example 1.10 (symmetry group)

Definition 1.11

Let

Sym (𝑋)

≔{𝑓:𝑋→𝑋|𝑓bijective}.

Proposition 1.12

$(Sym (𝑋), \circ)$ is a group.

Proof. Suppose $𝑓, 𝑔$ are bijections. Then:

$𝑓 \circ 𝑔$ is injective:
$\begin{aligned} (𝑓 \circ 𝑔) (𝑥) = (𝑓 \circ 𝑔) (𝑦) \\ ⟹ & 𝑓 (𝑔 (𝑥)) = 𝑓 (𝑔 (𝑦)) \\ ⟹ & 𝑔 (𝑥) = 𝑔 (𝑦) \\ ⟹ 𝑥 = 𝑦 \end{aligned}$
$𝑓 \circ 𝑔$ is surjective:
$\begin{aligned} \forall 𝑥 \in 𝑋, & \exists 𝑦 \in 𝑋 s.t. 𝑧 = 𝑓 (𝑦) \\ \exists 𝑥 \in 𝑋 s.t. 𝑦 = 𝑔 (𝑥) \\ ⟹ & 𝑧 = 𝑓 (𝑔 (𝑥)) = (𝑓 \circ 𝑔) (𝑥) . \end{aligned}$

So $𝑓 \circ 𝑔$ is a bijection, and $𝑓 \circ 𝑔$ is a binary operation on $Sym (𝑥)$ .

Composition is associative.

We have an identity, ${id}_{𝑋} : 𝑋 \to 𝑋; 𝑥 \mapsto 𝑥$ , which satisfies $𝑓 \circ {id}_{𝑥} = 𝑓 = {id}_{𝑋} \circ 𝑓$ , $\forall 𝑓 \in Sym (𝑓)$ .

We have inverses: $𝑓 \circ 𝑓^{- 1} = 𝑓^{- 1} \circ 𝑓 = {id}_{𝑋}$ .⁠ $□$

Definition 1.13

𝑋 = {1, 2, \dots, 𝑛}

𝑆_{𝑛}

≔Sym(𝑋) is the

𝑛

th symmetric group.

Remark 1.14

Sym (𝑋)

can also be interpreted as the permutations of

𝑋

Example 1.15 (fields)

Let $(𝐹, +, \times)$ be a field.

Then $(𝐹, +)$ is an abelian group, with identity element $0_{𝐹}$ , whereas $(𝐹 \ {0_{𝐹}}, \times)$ (sometimes denoted $𝐹^{*}$ ) is also an abelian group with identity element $1_{𝐹}$ .

For example, $ℚ \subset ℝ \subset ℂ$ all form groups under addition, or under multiplication when zero is excluded.

Also $ℤ_{𝑝}^{*} ≔$ non-zero integers mod p, for prime $𝑝$ , is a group under multiplication.

Example 1.16 (matrices)

$(𝑀_{𝑛} (𝐹), +)$ is an abelian group (where $𝑀_{𝑛} (𝐹)$ is the set of $𝑛 \times 𝑛$ matrices over $𝐹$ ).

Definition 1.17

Define

{GL}_{𝑛} (𝐹)

≔{𝐴∈𝑀𝑛(𝐹)|det𝐴≠0};

({GL}_{𝑛} (𝐹), \cdot)

is the

𝑛

th general linear group over

𝐹

Definition 1.18

Let

{SL}_{𝑛} (𝐹)

≔{𝐴∈GL𝑛(𝐹)|det𝐴=1}; this is the

𝑛

th standard linear group over

𝐹

under matrix multiplication.

Example 1.19

Definition 1.20

Let $𝑋$ be a set, let $𝑌 \subseteq 𝑋$ .

Let $Stab (𝑌)$ ≔{𝑓∈Sym(𝑋):𝑓(𝑌)=𝑌}; that is, $Stab (𝑌)$ is the set of permutations that map $𝑌$ to itself.

Proposition 1.21

$(Stab (𝑌), \circ)$ is a group.

Proof. Necessary to prove: $\forall 𝑓, 𝑔 \in Stab (𝑌), 𝑓 \circ 𝑔 \in Stab (𝑌)$ : $(𝑓 \circ 𝑔) (𝑌) = 𝑓 (𝑔 (𝑌)) = 𝑓 (𝑌) = 𝑌$ .

Associativity is inherited from the symmetric group.

${id}_{𝑋} (𝑌) = 𝑌 ⟹ {id}_{𝑋} \in Stab (𝑌)$ .

Let $𝑓 \in Stab (𝑌)$ , then $𝑓 (𝑌) = 𝑌$ . Hence $𝑓^{- 1} (𝑓 (𝑌)) = 𝑌$ , and $𝑓^{- 1} (𝑓 (𝑌)) = 𝑓^{- 1} (𝑌)$ , so $𝑓^{- 1} = 𝑌$ , so $𝑓^{- 1} \in Stab (𝑌)$ .⁠ $□$

Definition 1.22

(Stab (𝑌), \circ)

is the stabiliser subgroup of

𝑌

Definition 1.23

Let

𝐺

be a group, with binary operation

*

. A subset

𝐻 \subseteq 𝐺

is a subgroup if

*

restricts to a map

* : 𝐻 \times 𝐻 \to 𝐻

which then makes

(𝐻, *_{/ 𝐻})

into a group. We write

𝐻 \leq 𝐺

Example 1.24

(ℝ, +) \leq (ℂ, +)

Proposition 1.25 (Subgroup Test)

Let $𝐺$ be a group. A subset $𝐻$ of $𝐺$ is a subgroup iff :

$𝑒 \in 𝐻$
$\forall 𝑥, 𝑦 \in 𝐻, 𝑥 𝑦^{- 1} \in 𝐻$

Proof.

“ $⟹$ ”:

Assume $𝐻$ is a subgroup of $𝐺$ . Then $𝐻$ is closed under multiplication and inversion. Therefore $\forall 𝑥, 𝑦 \in 𝐻, 𝑥 𝑦^{- 1} \in 𝐻$ and also $𝑒 \in 𝐻$ .

“ $⟸$ ”: Associativity on $𝐻$ is inherited from $𝐺$ .

(i) $⟹ 𝑒 \in 𝐻$ .

Apply (ii) with $𝑥 = 𝑒$ , giving $\forall 𝑦 \in 𝐻, 𝑦^{- 1} \in 𝐻$ .

So $(𝐻, *_{/ 𝐻})$ is a group.⁠ $□$

Example 1.26

Let $𝐺 = {GL}_{𝑛} (ℝ)$ .

Let $O (𝑛) = {𝐀 \in 𝐺 | 𝐀^{⊤} 𝐀 = 𝐈}$ , the orthogonal matrices.

$𝐈^{⊤} 𝐈 = 𝐈 ⟹ 𝐈 \in O (𝑛)$ .
$\begin{aligned} 𝐀, 𝐁 \in O (𝑛) ⟹ {(𝐀 𝐁^{- 1})}^{⊤} (𝐀 𝐁^{- 1}) & = {(𝐁^{- 1})}^{⊤} 𝐀^{⊤} 𝐀 𝐁^{- 1} \\ = {(𝐁^{- 1})}^{⊤} 𝐁^{- 1} \\ = {(𝐁^{⊤})}^{- 1} 𝐁^{- 1} \\ = {(𝐁 𝐁^{⊤})}^{- 1} \\ = 𝐈^{- 1} (𝐁^{⊤} 𝐁 = 𝐈 ⟹ 𝐁 𝐁^{⊤} = 𝐈 for square 𝐁) \\ = 𝐈 \end{aligned}$

Hence by the subgroup test, $O (𝑛) \leq {GL}_{𝑛} (ℝ)$ .

Also ${SL}_{𝑛} (𝐹) \leq {GL}_{𝑛} (𝐹)$ can be shown by the subgroup test.

Lemma 1.27

𝐻 \leq 𝐺

and

𝐾 \leq 𝐺

, then

𝐻 \cap 𝐾 \leq 𝐺

Corollary 1.27.1

SO (𝑛) = {SL}_{𝑛} (ℝ) \cap O (𝑛) \leq {GL}_{𝑛} (ℝ)

Definition 1.28

Let $(𝐺, *_{𝐺}), (𝐻, *_{𝐻})$ be groups.

The product group is $(𝐺 \times 𝐻, *_{𝐺 \times 𝐻})$ , where $(𝑔_{1}, ℎ_{1}) *_{𝐺 \times 𝐻} (𝑔_{2}, ℎ_{2}) = (𝑔_{1} *_{𝐺} 𝑔_{2}, ℎ_{1} *_{𝐻} ℎ_{2})$ .

Lemma 1.29

The product of two groups is a group.

Proof. Associativity is easy.

$(𝑔, ℎ) (𝑒, 𝑒) = (𝑔 𝑒, ℎ 𝑒) = (𝑔, ℎ) = (𝑒, 𝑒) (𝑔, ℎ)$ , so $(𝑒, 𝑒)$ is an identity.

The inverse of $(𝑔, ℎ)$ is $(𝑔^{- 1}, ℎ^{- 1})$ .⁠ $□$

Definition 1.30

Let $𝐺$ be a group. $𝐺$ is cyclic if $\exists 𝑔 \in 𝐺$ s.t. $𝐺 = {𝑔^{𝑛} | 𝑛 \in ℤ}$ , where

𝑔^{𝑛} = {\begin{cases} 𝑔 𝑔^{𝑛 - 1} & if 𝑛 > 0 \\ 𝑒 & if 𝑛 = 0 \\ {(𝑔^{𝑛})}^{- 1} & if 𝑛 < 0 . \end{cases}

$𝑔$ is known as a generator of $𝐺$ .

Example 1.31

Definition 1.32

$𝐺 = (ℤ, +)$ is a cyclic group with $𝑔 = 1$ .

This is the infinite cyclic group.

Definition 1.33

For $𝑛 \in ℤ_{> 0}$ , $𝐶_{𝑛} = {𝑒, 𝑔, 𝑔^{2}, \dots, 𝑔^{𝑛 - 1}}$ is a cyclic group with binary operation

𝑔^{𝑎} 𝑔^{𝑏} = {\begin{cases} 𝑔^{𝑎 + 𝑏} & if 𝑎 + 𝑏 \leq 𝑛 - 1 \\ 𝑔^{𝑎 + 𝑏 - 𝑛} & if 𝑛 \leq 𝑎 + 𝑏 \leq 2 𝑛 - 2 \end{cases}

and inverse

{(𝑔^{𝑎})}^{- 1} = 𝑔^{𝑛 - 𝑎}

for

0 \leq 𝑎 < 𝑛

𝐶_{𝑛}

is the cyclic group of order

𝑛

Remark 1.34

A cyclic group can have more than one generator; for instance,

(ℤ, +)

also has

- 1

as a generator.

Remark 1.35

𝐶_{5} = ⟨ 𝑔^{2} ⟩

, where, for

ℎ \in 𝐻

, we write

⟨ ℎ ⟩ ≔ {ℎ^{𝑛} | 𝑛 \in ℤ}

. This is because 2 and 5 are coprime.

Definition 1.36

An isometry $𝑇 : ℝ^{𝑛} \to ℝ^{𝑛}$ is a distance-preserving function, i.e. $| 𝑇 (𝒗) - 𝑇 (𝒘) | = | 𝒗 - 𝒘 |$ for all $𝒗, 𝒘 \in ℝ^{𝑛}$ .

We write the set of isometries over $ℝ^{𝑛}$ as $Isom (ℝ^{𝑛})$ .

Remark 1.37

By the subgroup test,

Isom (ℝ^{𝑛}) \leq Sym (ℝ^{𝑛})

Remark 1.38

\forall 𝑇 \in Isom (ℝ^{𝑛}), \exists! 𝐀 \in 𝑂 (𝑛), 𝒃 \in ℝ^{𝑛}

s.t.

𝑇 (𝒗) = 𝐀 𝒗 + 𝒃

for all

𝒗 \in ℝ^{𝑛}

Definition 1.39

Let $𝑛 \in ℤ_{> 0}$ . Let $𝑃_{𝑛}$ be the regular $𝑛$ -sided polygon centred at the origin $𝑂$ .

The dihedral group $𝐷_{2 𝑛}$ is

𝐷_{2 𝑛} ≔ Isom (ℝ^{2}) \cap Stab (𝑃_{𝑛});

that is, it is the group of distance-preserving transformations that stabilise the regular $𝑛$ -sided polygon centred at the origin.

We denote the rotation by $2 𝜋 / 𝑛$ anticlockwise by $𝑟$ , and the reflection in an axis (which one depends on which way we choose to draw the polygons) by $𝑠$ . Then the elements of $𝐷_{2 𝑛}$ are $𝑒, 𝑟, 𝑟^{2}, \dots, 𝑟^{𝑛 - 1}, 𝑠, 𝑟 𝑠, 𝑟^{2} 𝑠, \dots, 𝑟^{𝑛 - 1} 𝑠$ . Note that this is $2 𝑛$ elements.

Proposition 1.40

$𝑆_{2 𝑛} = {𝑟^{𝑖} 𝑠^{𝑗} | 0 \leq 𝑖 < 𝑛, 𝑗 \in {0, 1}}$ .

Proof. Suppose $𝑟^{𝑖} 𝑠^{𝑗} = 𝑟^{𝑎} 𝑠^{𝑏}$ w.l.o.g. $𝑖 \geq 𝑎$ . Then $𝑟^{- 𝑎} 𝑟^{𝑖} 𝑠^{𝑗} = 𝑟^{- 𝑎} 𝑟^{𝑎} 𝑠^{𝑏} = 𝑠^{𝑏}$ , so w.l.o.g. $𝑎 = 0$ .

If $𝑗 = 𝑏$ , then $𝑟^{𝑖} = 𝑟^{0} = 𝑒 ⟹ 𝑟^{𝑖} (𝑝_{0}) = 𝑒 (𝑝_{0})$ for some point $𝑝_{0}$ , so $𝑖 = 0$ .

If $𝑗 \neq 𝑏$ , $𝑟^{𝑖} = 𝑠$ . Take dets to get $1 = - 1$ , contradiction.

Now let $𝑃 \in 𝐷_{2 𝑛}$ . Then $𝑃 (𝑝_{0}) = 𝑝_{𝑖} = 𝑟^{𝑖} (𝑝_{0})$ for some $𝑖 \in {0, \dots, 𝑛 - 1}$ .

Hence $𝑟^{- 𝑖} 𝑃 (𝑝_{0}) = 𝑝_{0}$ .

Now $| 𝑟^{- 𝑖} 𝑃 (𝑝_{1}) - 𝑟^{- 𝑖} 𝑃 (𝑝_{0}) | = | 𝑝_{1} - 𝑝_{0} |$ , hence $𝑟^{- 𝑖} 𝑃 (𝑝_{1}) \in {𝑝_{1}, 𝑝_{𝑛 - 1}}$ .

TODO finish this off⁠ $□$

Definition 1.41

The order of a group

𝐺

| 𝐺 |

, the number of elements in

𝐺

Definition 1.42

𝐺 = {𝑔_{1}, \dots, 𝑔_{𝑛}}

, its Cayley table is an

𝑛 \times 𝑛

array where with

𝑔_{𝑖} 𝑔_{𝑗}

in the

𝑖

th row and

𝑗

th column.

Definition 1.43

Let $𝐺, 𝐻$ be groups. An isomorphism between $𝐺$ and $𝐻$ is a bijection $𝜑 : 𝐺 \to 𝐻$ s.t.

𝜑 (𝑔_{1} 𝑔_{2}) = 𝜑 (𝑔_{1}) 𝜑 (𝑔_{2}) .

If there is an isomorphism between $𝐺$ and $𝐻$ , then $𝐺$ and $𝐻$ are isomorphic, written $𝐺 ≅ 𝐻$ .

Remark 1.44

Isomorphic finite groups will have the “same” Cayley tables (up to row/column orders).

Definition 1.45

For a group $𝐺$ , the order of an element $𝑔 \in 𝐺$ is

𝑜 (𝑔) ≔ min {𝑟 \in ℤ_{> 0} | 𝑔^{𝑟} = 𝑒} .

If $𝑔^{𝑟} \neq 𝑒$ for all $𝑟 \in ℤ_{> 0}$ , we say that $𝑔$ has infinite order.

Lemma 1.46

If $𝜑 : 𝐺 \to 𝐻$ is an isomorphism, then $\forall 𝑔 \in 𝐺$ ,

𝑜 (𝜑 (𝑔)) = 𝑜 (𝑔) .

Proof.

First we show that $𝜑 (𝑒) = 𝑒$ :

\begin{aligned} 𝜑 (𝑒) & = 𝜑 (𝑒^{2}) \\ = {𝜑 (𝑒)}^{2} \\ ⟹ 𝑒 & = {𝜑 (𝑒)}^{- 1} 𝜑 (𝑒) \\ = {𝜑 (𝑒)}^{- 1} {𝜑 (𝑒)}^{2} \\ = 𝜑 (𝑒) . \end{aligned}

Then

\begin{aligned} 𝑔^{𝑟} = 𝑒 & ⟺ 𝜑 (𝑔^{𝑟}) = 𝜑 (𝑒) = 𝑒 \\ ⟺ {𝜑 (𝑔)}^{𝑟} = 𝑒 . \end{aligned}

Hence

\begin{aligned} 𝑜 (𝑔) & = min {𝑟 > 0 | 𝑔^{𝑟} = 𝑒} \\ = min {𝑟 > 0 | {𝜑 (𝑔)}^{𝑟} = 𝑒} & = 𝑜 (𝜑 (𝑔)) . \end{aligned}

2. Permutation groups

Remark 2.1

| 𝑆_{𝑛} | = 𝑛!

Remark 2.2

We write permutations on the right, i.e. if $𝑖 \in {1, \dots, 𝑛}, 𝜎 \in 𝑆_{𝑛}$ , then $𝑖 𝜎 ≔ 𝜎 (𝑖)$ .

This means that composition is backwards from the usual order.

Definition 2.3

A cycle is a permutation $𝜎 \in 𝑆_{𝑛}$ such that $\exists {𝑎_{1}, \dots, 𝑎_{𝑚}} \subseteq {1, \dots, 𝑛}$ s.t. $𝑎_{𝑘} 𝜎 = 𝑎_{𝑘 + 1}$ for $𝑘 \in {1, \dots, 𝑚 - 1}$ and $𝑎_{𝑚} 𝜎 = 𝑎_{1}$ , and for all $𝑥 \in {1, \dots, 𝑛} \ {𝑎_{1}, \dots, 𝑎_{𝑚}}$ , $𝑥 𝜎 = 𝑥$ .

We denote this cycle as $(𝑎_{1} 𝑎_{2} \dots 𝑎_{𝑚})$ .

Remark 2.4

We could denote

𝑒 = (1) (2) \dots (𝑛)

Lemma 2.5

Disjoint cycles commute.

Proof. Let $𝜎 = (𝑎_{1} \dots 𝑎_{𝑚})$ and $𝜏 = (𝑏_{1} \dots 𝑏_{𝑘})$ be disjoint cycles, i.e. ${𝑎_{1}, \dots, 𝑎_{𝑚}} \cap {𝑏_{1}, \dots, 𝑏_{𝑘}} = \emptyset$ .

Let $𝑖 \in {1, \dots, 𝑛}$ . Then

𝑖 𝜎 𝜏 = {\begin{cases} 𝑎_{𝑗 + 1} 𝜏 = 𝑎_{𝑗 + 1} & if 𝑖 = 𝑎_{𝑗} \\ 𝑖 𝜏 = 𝑏_{𝑗 + 1} & if 𝑖 = 𝑏_{𝑗} \\ 𝑖 & otherwise; \end{cases}

𝑖 𝜏 𝜎 = {\begin{cases} 𝑖 𝜎 = 𝑎_{𝑗 + 1} & if 𝑖 = 𝑎_{𝑗} \\ 𝑏_{𝑗 + 1} 𝜎 = 𝑏_{𝑗 + 1} & if 𝑖 = 𝑏_{𝑗} \\ 𝑖 & otherwise . \end{cases}

Theorem 2.6

Every $𝜎 \in 𝑆_{𝑛}$ can be written as a product of disjoint cycles.

Moreover, this factorisation is unique up to cycling of elements within cycles, and order of (commuting) factors.

Proof. Fix $𝑎_{1} \in {1, \dots, 𝑛}$ and consider $𝑎_{1}, 𝑎_{1} 𝜎$ , $𝑎_{1} 𝜎^{2}, \dots$ .

There exists $0 \leq 𝑖 < 𝑗$ such that $𝑎_{1} 𝜎^{𝑖} = 𝑎_{1} 𝜎^{𝑘}$ . We choose such a pair $(𝑖, 𝑗)$ with minimal $𝑖$ .

Then applying $𝜎^{- 𝑖}$ , we get that $𝑎_{1} = 𝑎_{1} 𝜎^{𝑗 - 𝑖}$ , and note that $𝑜 < 𝑗 - 𝑖$ . Since $𝑖$ was minimal, $𝑖 = 0$ .

Let $𝑗 > 0$ be the least such that $𝑎_{1} 𝜎^{𝑗} = 𝜎_{1}$ , then $𝑎_{1}, 𝑎_{1} 𝜎, 𝑎_{1} 𝜎^{2}, \dots, 𝑎_{1} 𝜎^{𝑗 - 1}$ must all be distinct.

The set ${𝑎_{1}, 𝑎_{1} 𝜎, \dots, 𝑎_{1} 𝜎^{𝑗 - 1}}$ is known as the orbit of $𝑎_{1}$ under $𝜎$ , $orbit (𝑎_{1})$ .

Note that $orbit (𝑎_{1}) = {𝑎_{1} 𝜎^{𝑛} | 𝑛 \in ℕ} = {𝑎_{1} 𝜎^{𝑛} | 𝑛 \in ℤ}$ .

Now pick $𝑎_{2} \in {𝑎, \dots, 𝑛} \ orbit (𝑎_{1})$ . $orbit (𝑎_{2})$ must be disjoint from $orbit (𝑎_{1})$ , otherwise $𝑎_{2} \in orbit (𝑎_{1})$ , since if $𝑎_{1} 𝜎^{𝑟} = 𝑎_{2} 𝜎^{𝑠}$ , then $𝑎_{2} = 𝑎_{1} 𝜎^{𝑟 - 𝑠}$ .

We continue until we have a partition

{1, \dots, 𝑛} = orbit (𝑎_{1}) \cup \dots \cup orbit (𝑎_{𝑟}) .

Then $𝜎 = (𝑎_{1} 𝑎_{1} 𝜎 \dots 𝑎_{1} 𝜎^{𝑗_{1} - 1}) (𝑎_{2} 𝑎_{2} 𝜎 \dots 𝑎_{2} 𝜎^{𝑗_{2} - 1}) \dots (𝑎_{𝑟} 𝑎_{𝑟} 𝜎 \dots 𝑎_{𝑟} 𝜎^{𝑗_{𝑟} - 1})$ , where $𝑗_{𝑖} = | orbit (𝑎_{𝑖}) |$ for $𝑖 \in {1, \dots, 𝑟}$ .

If $𝜎 = 𝑐_{1} \cdot 𝑐_{2} \cdot \dots \cdot 𝑐_{𝑟} = 𝑐_{1^{'}} \cdot 𝑐_{2^{'}} \cdot \dots . \cdot 𝑐_{𝑟^{'}}$ , then 1 must appear in one of the $𝑐_{𝑖^{'}}$ s, supposing W.L.O.G. that $𝑖 = 1$ . Also 1 appears in $𝑐_{1}$ . Then $𝑐_{1} = (1 1 𝜎 \dots 1 𝜎^{𝑗_{1} - 2})$ , and $𝑐_{1^{'}} = (1 1 𝜎 \dots 1 𝜎^{𝑗_{1^{'}} - 1})$ , hence $𝑗_{1} = 𝑗_{1^{'}}$ and $𝑐_{1} = 𝑐_{1^{'}}$ . Repeat for all $𝑐_{𝑖^{'}}$ s, then the factorisation is unique up to commutation and cycling.⁠ $□$

Proposition 2.7

Let $𝜎 = 𝜌_{1} 𝜌_{2} \dots 𝜌_{𝑘} \in 𝑆_{𝑛}$ where the $𝜌_{𝑖}$ s are disjoint cycles. Then $𝑜 (𝜎) = lcm (𝑜 (𝜌_{1}), \dots, 𝑜 (𝜌_{𝑘}))$ and $𝑜 (𝜌_{𝑖}) = length of 𝜌_{𝑖}$ .

Proof. If $𝑐$ is a cycle of length $𝑙$ , $𝑐 = (𝑎_{1} 𝑎_{2} \dots 𝑎_{𝑙})$ , then $𝑎_{𝑖} 𝑐^{𝑙} = 𝑎_{𝑖}$ , whereas if $𝑥 \neq 𝑎_{𝑖}$ then $𝑥 𝑐 = 𝑥$ so $𝑥 𝑐^{𝑙} = 𝑥$ . Therefore $𝑐^{𝑙} = 𝑒$ .

Conversely, if $𝑐^{𝑚} = 𝑒$ for $𝑚 > 0$ then $𝑎_{1} 𝑐^{𝑚} = 𝑎_{1} 𝑒 = 𝑎_{1}$ , so $𝑚 \geq 𝑙$ therefore $𝑜 (𝑐) = 𝑙$ .

Then let $𝐿 ≔ lcm (𝑙_{𝑖}), 𝑙_{𝑖} = length (𝜌_{𝑖}) = 𝑜 (𝜌_{𝑖})$ .

Then $𝑙_{𝑖} ∣ 𝐿 \forall 𝑖$ , so $𝜎^{𝐿} = {(𝜌_{1} 𝜌_{2} \dots 𝜌_{𝑘})}^{𝐿} = 𝜌_{1}^{𝑙} 𝜌_{2}^{𝑙} \dots 𝜌_{𝑘}^{𝐿}$ (note that this is not a valid application of distributivity in the general case!).

Lemma 2.8

If $𝑔 \in 𝐺$ has finite order, then for $𝑛 \in ℤ$ , $𝑔^{𝑛} = 𝑒$ iff $𝑜 (𝑔) ∣ 𝑛$ .

Proof. “ $⟸$ ”:

If $𝑜 (𝑔) ∣ 𝑛$ , then $𝑛 = 𝑜 (𝑔) 𝑚$ , hence $𝑔^{𝑛} = 𝑔^{𝑜 (𝑔) 𝑚} = {(𝑔^{𝑜 (𝑔)})}^{𝑚} = 𝑒^{𝑚} = 𝑒$ .

“ $⟹$ ”:

We write $𝑛 = 𝑞 𝑜 (𝑔) + 𝑟$ for $𝑞 \in ℤ$ and $0 \leq 𝑟 < 𝑜 (𝑔)$ . Then $𝑔^{𝑛} = 𝑒 ⟹ 𝑔^{𝑞 𝑜 (𝑔) + 𝑟} = 𝑒$ hence $𝑔^{𝑟} = 𝑒$ . But $𝑟 < 𝑜 (𝑔)$ , so $𝑟 = 0$ by the defn of $𝑜 (𝑔)$ .⁠ $□$

We have that $𝜎^{𝐿} = 𝑒$ ; by the lemma, $𝑜 (𝜎) ∣ 𝐿$ .

Now consider $𝜎^{𝑜 (𝜎)} = 𝑒$ . Then ${(𝜌_{1} \dots 𝜌_{𝑘})}^{𝑜 (𝜎)} = 𝑒$ hence $𝜌_{1}^{𝑜 (𝜎)} \dots 𝜌_{𝑘}^{𝑜 (𝜎)} = 𝑒$ .

If we take $𝑦 \in {1, \dots, 𝑛}$ , saying W.L.O.G. that $𝑦$ appears in $𝜌_{𝑖}$ . Then $𝑦$ does not appear in any other $𝜌_{𝑗}$ , hence $𝑦 𝜌_{𝑖}^{𝑜 (𝜎)} = 𝑦 ⟹ 𝜌_{𝑖}^{𝑜 (𝜎)} = 𝑒$ for all $𝑖$ .

By the lemma, $𝑜 (𝜌_{𝑖}) ∣ 𝑜 (𝜎)$ , so $𝐿 = lcm (𝑜 (𝜌_{𝑖})) ∣ 𝑜 (𝜎)$ .⁠ $□$

Definition 2.9

For $𝜎 \in 𝑆_{𝑛}$ , we define $𝑃_{𝜎} \in {GL}_{𝑛 (ℝ)}$ to besuch that the $𝑖$ th row of $𝑃_{𝜎}$ has a $1$ in column $𝑖 𝜎$ , and has all other entries zero. Then $𝑃_{𝜎}$ is a permutation matrix.

That is,

{(𝑃_{𝜎})}_{𝑖 𝑗} = 𝛿_{𝑖 𝜎, 𝑗}

Proposition 2.10

$\forall 𝜎, 𝜏 \in 𝑆_{𝑛}$ , $𝑃_{𝜎} 𝑃_{𝜏} = 𝑃_{𝜎 𝜏}$ .

Proof. Fix $1 \leq 𝑖, 𝑗 \leq 𝑛$ . Then

\begin{aligned} {(𝑃_{𝜎} 𝑃_{𝜏})}_{𝑖 𝑗} = \sum_{𝑘 = 1}^{𝑛} {(𝑃_{𝜎})}_{𝑖 𝑘} {(𝑃_{𝜏})}_{𝑘 𝑗} \\ = \sum_{𝑘 = 1}^{𝑛} 𝛿_{𝑖 𝜎, 𝑘} 𝛿_{𝑘 𝜏, 𝑗} \\ = 𝛿_{(𝑖 𝜎) 𝜏, 𝑗} \\ = 𝛿_{𝑖 (𝜎 𝜏), 𝑗} \\ = 𝑃_{{(𝜎 𝜏)}_{𝑖 𝑗}} . \end{aligned}

Definition 2.11

The sign of a permutation is the function

sgn : 𝑆_{𝑛} \to ℝ

𝜎 \mapsto det 𝑃_{𝜎}

Remark 2.12

sgn (𝑎_{1} \dots 𝑎_{𝑘}) = \prod_{𝑖 = 1}^{𝑘 - 1} sgn (𝑎_{𝑖} 𝑎_{𝑖 + 1}) = {(- 1)}^{𝑘 - 1} .

Definition 2.13

A permutation

𝜎

is even if

sgn (𝜎) = 1

and odd if

sgn (𝜎) = - 1

Remark 2.14

sgn (𝜎 𝜏) = sgn (𝜎) sgn (𝜏) .

Definition 2.15

𝜎 \in 𝑆_{𝑛}

is a transposition if it is a 2-cycle, i.e.

𝜎 = (𝑖 𝑗)

for some

1 \leq 𝑖 < 𝑗 \leq 𝑛

Remark 2.16

sgn (𝜎) = {(- 1)}^{𝑚}

where

𝑚

is the number of transpositions of which

𝜎

can be be written as a product.

Definition 2.17

The alternating group is

𝐴_{𝑛} ≔ {𝜎 \in 𝑆_{𝑛} | sgn (𝜎) = 1} .

Remark 2.18

𝐴_{𝑛} \leq 𝑆_{𝑛}

by the Subgroup Test; also

| 𝐴_{𝑛} | = \frac{1}{2} | 𝑆_{𝑛} | = \frac{1}{2} 𝑛!

3. Conjugacy

Definition 3.1

Let $𝐺$ be a group, $𝑔, ℎ \in 𝐺$ . $𝑔$ is conjugate to $ℎ$ (in $𝐺$ ) if $\exists 𝑥 \in 𝐺$ s.t. $𝑥^{- 1} 𝑔 𝑥 = ℎ$ .

We write this as $𝑔 \sim ℎ$ .

Lemma 3.2

Conjugacy is an equivalence relation.

Proof. Let $𝑥, 𝑦, 𝑧 \in 𝐺$ .

Reflexivity: $𝑥 = 𝑒^{- 1} 𝑥 𝑒 ⟹ 𝑥 \sim 𝑥$

Symmetry:

\begin{aligned} 𝑥 \sim 𝑦 & ⟹ \exists 𝑔 \in 𝐺 . 𝑦 = 𝑔^{- 1} 𝑥 𝑔 \\ ⟹ 𝑥 = {(𝑔^{- 1})}^{- 1} 𝑥 𝑔^{- 1} \\ ⟹ 𝑦 \sim 𝑥 . \end{aligned}

Transitivity: Suppose $𝑥 \sim 𝑦$ and $𝑦 \sim 𝑧$ , then $𝑧 = 𝑔^{- 1} 𝑦 𝑔 = 𝑔^{- 1} ℎ^{- 1} 𝑥 ℎ 𝑔 = {(ℎ 𝑔)}^{- 1} 𝑥 (ℎ 𝑔)$ , so $𝑥 \sim 𝑧$ .⁠ $□$

Definition 3.3

The conjugacy class of

𝑥 \in 𝐺

is the equivalence class

𝑥

under

\sim

. We denote this

𝑔^{𝐺}

. (This is not standard notation).

Remark 3.4

$𝐺$ is the disjoint union of its conjugacy classes,

𝐺 = ⨃ {𝑔^{𝐺} | 𝑔 \in 𝐺} .

Proposition 3.5

If $𝐺$ is an abelian group, then $𝑦 \sim 𝑥$ iff $𝑦 = 𝑥$ .

Proof.

𝑦 = 𝑔^{- 1} 𝑥 𝑔 ⟺ 𝑦 = 𝑥 𝑔^{- 1} 𝑔 = 𝑥 .

Corollary 3.5.1

The conjugacy classes of an abelian group are singletons.

Lemma 3.6

Any conjugate of a $𝑘$ -cycle $(𝑎_{1} \dots 𝑎_{𝑘}) \in 𝑆_{𝑛}$ is itself a $𝑘$ -cycle.

Proof.

𝜌^{- 1} (𝑎_{1} \dots 𝑎_{𝑘}) 𝜌 = (𝑎_{1} 𝜌 \dots 𝑎_{𝑘} 𝜌) .

⁠ $□$

Theorem 3.7

For $𝜎, 𝜏 \in 𝑆_{𝑛}$ , $𝜎 \sim 𝜏$ iff $𝜎$ and $𝜏$ have the same cycle type (that, is they have the same number of cycles of each length when factored into cycles).

Proof. “ $⟹$ ”: Suppose $𝜎 \sim 𝜏$ , then it follows from unqieueness of cycle factorisation, Lemma 3.6 and distributivity that $𝜎$ and $𝜏$ have the same cycle type.

“ $⟸$ ”:

Suppose $𝜎$ and $𝜏$ have the same cycle type, writing $𝜎 = 𝑐_{1} \dots 𝑐_{𝑘}$ and $𝜏 = 𝑐_{1^{'}} \dots 𝑐_{𝑘^{'}}$ . By Lemma 3.6, we can choose any $𝜌 \in 𝑆_{𝑛}$ such that each $𝑐_{𝑖} = 𝜌^{- 1} 𝑐_{𝑖^{'}} 𝜌$ , then by distributivity $𝜎 = 𝜌^{- 1} 𝜏 𝜌$ so $𝜎 \sim 𝜏$ .⁠ $□$

4. Subgroups

Definition 4.1

Let $𝑆$ be a subset of a group $𝐺$ .

The subgroup generated by $𝑆$ is:

⟨ 𝑆 ⟩ ≔ ⋂ {𝐻 \leq 𝐺 | 𝐻 \supseteq 𝑆} .

Remark 4.2

⟨ 𝑆 ⟩

is the smallest subgroup of

𝐺

that contains

𝑆

Lemma 4.3

Arbitrary intersections of families of subgroups are subgroups.

Definition 4.4

Let

𝑆 \subseteq 𝐺

. A word in

𝑆

is some

𝑤 \in 𝐺

s.t.

\exists 𝑠_{1}, 𝑠_{2}, \dots, 𝑠_{𝑛} \in 𝑆

s.t.

𝑤 = 𝑠_{1} 𝑠_{2} \dots 𝑠_{𝑛}

Remark 4.5

𝑛 = 0

in the above definition, then the word

𝑤 = 𝑒

Proposition 4.6

Let $𝑆 \subseteq 𝐺$ , $𝑤 (𝑆) ≔ {words in 𝑆}$ , $𝑆^{- 1} ≔ {𝑠^{- 1} | 𝑠 \in 𝑆}$ .

Then $⟨ 𝑆 ⟩ = 𝑤 (𝑆 \cup 𝑆^{- 1})$ .

Proof.

“ $\supseteq$ ”: It suffices to prove (STP) that $\forall 𝐻 \leq 𝐺$ s.t. $𝐻 \supseteq 𝑆$ , $𝑤 (𝑆 \cup 𝑆^{- 1}) \subseteq 𝐻$ .

So let $𝑤 \in 𝑤 (𝑆 \cup 𝑆^{- 1})$ . Then $𝑤 = 𝑠_{1} 𝑠_{2} \dots 𝑠_{𝑛}$ for $𝑠_{𝑖} \in 𝑆 \cup 𝑆^{- 1}$ . Since $𝑆 \subseteq 𝐻$ , each $𝑠_{𝑖} \in 𝐻$ . Since $𝐻 \leq 𝐺$ , $𝑤 \in 𝐻$ .

“ $\subseteq$ ”: STP that $𝑤 (𝑆 \cup 𝑆^{- 1})$ is a subgroup of $𝐺$ containing $𝑆$ , so then $⟨ 𝑆 ⟩ \subseteq 𝑤 (𝑆 \cup 𝑆^{- 1})$ .

$𝑒 \in 𝑤 (𝑆) \subseteq 𝑤 (𝑆 \cup 𝑆^{- 1})$ .

If $𝑥, 𝑦 \in 𝑤 (𝑆 \cup 𝑆^{- 1})$ , then $𝑥 = 𝑠_{1} \dots 𝑠_{𝑛}$ , $𝑦 = 𝑡_{1} \dots 𝑡_{𝑚}$ for $𝑠_{𝑖}, 𝑡_{𝑖} \in 𝑆 \cup 𝑆^{- 1}$ . Then $𝑥 𝑦^{- 1} = 𝑠_{1} \dots 𝑠_{𝑛} 𝑡_{𝑚}^{- 1} \dots 𝑡_{1}^{- 1} \in 𝑤 (𝑆 \cup 𝑆^{- 1})$ .

For all $𝑠 \in 𝑆$ , $𝑠$ is a word in $𝑆$ , so $𝑆 \subseteq 𝑤 (𝑆 \cup 𝑆^{- 1})$ .⁠ $□$

Remark 4.7

⟨ {𝑔} ⟩ = ⟨ 𝑔 ⟩ = {𝑔^{𝑛} | 𝑛 \in ℤ}

Corollary 4.7.1

𝑔

has finite order, then

𝑜 (𝑔) = | ⟨ 𝑔 ⟩ |

Theorem 4.8

Let $𝐺 = ⟨ 𝑔 ⟩$ be a cyclic group.

If $| 𝐺 | = 𝑛$ is finite, then $𝐺 ≅ 𝐶_{𝑛}$
Otherwise, $𝐺 ≅ (ℤ, +)$ .

Proof.

$𝐺 = {𝑒, 𝑔, 𝑔^{2}, \dots, 𝑔^{𝑛 - 1}}$ .
Say $𝐶_{𝑛} = {𝑒, 𝑥, 𝑥^{2}, 𝑥^{𝑛 - 1}}$ .
Then $𝜑 : 𝐺 \to 𝐶_{𝑛}$ is defined by $𝑔^{𝑖} \mapsto 𝑥^{𝑖}$ .
Define $𝜑 : ℤ \to 𝐺; 𝑛 \mapsto 𝑔^{𝑛}$ .
Then $𝜑 (𝑛 + 𝑚) = 𝑔^{𝑛 + 𝑚} = 𝑔^{𝑛} 𝑔^{𝑚} = 𝜑 (𝑛) 𝜑 (𝑚)$ .
$𝜑$ is clearly surjective as $𝐺 = {𝑔^{𝑛} | 𝑛 \in ℤ}$ . If $𝜑 (𝑛) = 𝜑 (𝑚)$ , then $𝑔^{𝑛} = 𝑔^{𝑚}$ , so $𝑔^{𝑛 - 𝑚} = 𝑒$ ; since $𝐺$ has infinite order, $𝑛 - 𝑚 = 0$ so $𝑛 = 𝑚$ . Hence $𝜑$ is also injective, so it is a bijection.
⁠ $□$

Theorem 4.9

Any subgroup of a cyclic group is cyclic.

Proof. Say that $𝐺 = ⟨ 𝑔 ⟩$ , and let $𝐻 \leq 𝐺$ . If $𝐻 = {𝑒}$ , done.

Otherwise, $\exists 𝑚 \neq 0$ such that $𝑔^{𝑚} \in 𝐻$ .

Since $𝐻$ is closed under inverses, if $𝑚 < 0$ then also $𝑔^{- 𝑚} \in 𝐻$ . So we can assume that $𝑚 > 0$ .

Let $𝑛 ≔ min {𝑚 > 0 | 𝑔^{𝑚} \in 𝐻}$ . Then $𝑔^{𝑛} \in 𝐻$ , and if $0 < 𝑚 < 𝑛$ then $𝑔^{𝑚} \notin 𝐻$ .

Claim: $𝐻 = ⟨ 𝑔^{𝑛} ⟩$ .

“ $\supseteq$ ”:

\begin{aligned} 𝑔^{𝑛} \in 𝐻 & ⟹ {(𝑔^{𝑛})}^{𝑟} \in 𝐻 \forall 𝑟 \in ℤ \\ ⟹ ⟨ 𝑔^{𝑛} ⟩ = {𝑔^{𝑛 𝑟} | 𝑟 \in ℤ} \subseteq 𝐻 \end{aligned}

“ $\subseteq$ ”: Take $ℎ \in 𝐻$ . Since $𝐻 \subseteq 𝐺 = ⟨ 𝑔 ⟩$ , $\exists 𝑘 \in ℤ$ s.t. $ℎ = 𝑔^{𝑘}$ .

Divide $𝑘$ by $𝑛$ with remainder to get $𝑘 = 𝑞 𝑛 + 𝑟$ where $𝑞, 𝑟 \in ℤ$ and $0 \leq 𝑟 < 𝑛 - 1$ .

Then $𝑟 = 𝑘 - 𝑞 𝑛$ , so $𝑔^{𝑟} = 𝑔^{𝑘 - 𝑞 𝑛} = 𝑔^{𝑘} {(𝑔^{𝑛})}^{- 𝑞}$ .

Since $𝑔^{𝑘}, 𝑔^{𝑛} \in 𝐻$ , by the subgroup test $𝑔^{𝑟} \in 𝐻$ , so by our choice of $𝑛$ and $𝑟 < 𝑛$ , it must be that $𝑟 = 0$ . Hence $𝑘 = 𝑞 𝑛$ , so $ℎ = 𝑔^{𝑘} = {(𝑔^{𝑛})}^{𝑞} \in ⟨ 𝑔^{𝑛} ⟩$ .⁠ $□$

Corollary 4.9.1

The subgroups of

ℤ

are

𝑚 ℤ

for each

𝑚 \in ℤ

Proposition 4.10

Let $𝑚, 𝑛 \in ℤ$ . Then $\exists 𝑢, 𝑣 \in ℤ$ s.t. $𝑢 𝑚 + 𝑣 𝑛 ≕ ℎ$ generates $⟨ 𝑚, 𝑛 ⟩ (= 𝑚 ℤ + 𝑛 ℤ)$ .

If $ℎ > 0$ , then $ℎ = gcd (𝑚, 𝑛)$ .

Proof.

$⟨ 𝑚, 𝑛 ⟩$ is a subgroup of $(ℤ, +)$ , so, by Theorem 4.9, $⟨ 𝑚, 𝑛 ⟩ = ⟨ ℎ ⟩$ for some $ℎ \in ℤ$ .

Then $𝑚 \in ⟨ ℎ ⟩$ , so $𝑚 = 𝑟 ℎ$ for some $𝑟 \in ℤ$ . Similarly, $𝑛 = 𝑠 ℎ$ for some $𝑠 \in ℤ$ .

Thus $ℎ ∣ 𝑚$ and $ℎ ∣ 𝑛$ .

To show that $ℎ = gcd (𝑚, 𝑛)$ , we will show that if $𝑘 ∣ 𝑚$ and $𝑘 ∣ 𝑛$ , then $𝑘 ∣ ℎ$

But $\exists 𝑢, 𝑣 \in ℤ$ s.t. $ℎ = 𝑢 𝑚 + 𝑣 𝑛$ because $ℎ \in ⟨ 𝑚, 𝑛 ⟩$ , and now $𝑘 ∣ 𝑚$ and $𝑘 ∣ 𝑛$ $⟹ 𝑘 ∣ 𝑢 𝑚 + 𝑣 𝑛 = ℎ$ .⁠ $□$

Lemma 4.11 (Bézout's Lemma)

$\forall 𝑚, 𝑛 \in ℤ, \exists 𝑢, 𝑣 \in ℤ$ s.t. $gcd (𝑚, 𝑛) = 𝑢 𝑚 + 𝑣 𝑛$ .

Proof. Equivalent to Proposition 4.10.⁠ $□$

Theorem 4.12 (Chinese Remainder Theorem)

Suppose $𝑚, 𝑛 \in ℤ^{+}$ are coprime. Then $𝐶_{𝑚} \times 𝐶_{𝑛}$ is cyclic, and is isomorphic to $𝐶_{𝑚 \times 𝑛}$ .

Proof. Say $𝐶_{𝑚} = ⟨ 𝑔 ⟩$ and $𝐶_{𝑛} = ⟨ ℎ ⟩$ .

STP: $𝐶_{𝑚} \times 𝐶_{𝑛} = ⟨ (𝑔, ℎ) ⟩$ .

Let $𝑘 ≔ 𝑜 ((𝑔, ℎ))$ . Then $(𝑔^{𝑘}, ℎ^{𝑘}) = {(𝑔, ℎ)}^{𝑘} = (𝑒, 𝑒)$ . Therefore $𝑚 ∣ 𝑘$ and $𝑛 ∣ 𝑘$ , hence $𝑚 𝑛 ∣ 𝑘$ ,= because $𝑚, 𝑛$ coprime, by Bézout’s Lemma.

Also, ${(𝑔, ℎ)}^{𝑚 𝑛} = (𝑔^{𝑚 𝑛}, ℎ^{𝑚 𝑛}) = (𝑒^{𝑛}, 𝑒^{𝑚}) = (𝑒, 𝑒)$ . So $𝑘 ∣ 𝑚 𝑛$ .

Therefore $𝑘 = 𝑚 𝑛$ .⁠ $□$

5. Modular arithmetic

Definition 5.1

For a set $𝑋$ and relation $𝑅 \in 𝑋^{2}$ , we write

𝑋 / 𝑅 ≔ {{[𝑥]}_{𝑅} | 𝑥 \in 𝑋}

to be the set of equivalence classes in

𝑋

under

𝑅

Lemma 5.2

$\equiv_{𝑛}$ is an equivalence relation (where $\underset{𝑛}{\equiv}$ is congruence modulo $𝑛$ ).

Proof. See e.g. Discrete Maths (MT2025).⁠ $□$

Definition 5.3

We write

ℤ_{𝑛}

to mean

ℤ / \equiv_{𝑛}

Definition 5.4

We write

\overset{̅}{𝑥} ≔ {[𝑥]}_{\equiv_{𝑛}}

Example 5.5

ℤ_{2} = {{\dots, - 4, - 2, 0, 2, 4, \dots}, {\dots, - 3, - 1, 1, \vec{3} . .}} = {\overset{̅}{0}, \overset{̅}{1}} .

Lemma 5.6

Let $𝑥, 𝑥^{'}, 𝑦, 𝑦^{'} \in ℤ$ such that $𝑥 \equiv 𝑥^{'} mod 𝑛$ and $𝑦 \equiv 𝑦^{'} mod 𝑛$ .

$𝑥 + 𝑦 \equiv 𝑥^{'} + 𝑦^{'} mod 𝑛$
$𝑥 𝑦 \equiv 𝑥^{'} 𝑦^{'} mod 𝑛$

Proof.

$𝑛 ∣ 𝑥 - 𝑥^{'}$ and $𝑛 ∣ 𝑦 - 𝑦^{'}$ , so
$𝑛 ∣ (𝑥 - 𝑥^{'}) + (𝑦 - 𝑦^{'}) = (𝑥 + 𝑦) - (𝑥^{'} + 𝑦^{'})$
hence $𝑥 + 𝑦 \equiv 𝑥^{'} + 𝑦^{'} mod 𝑛$ .
$𝑥^{'} 𝑦^{'} - 𝑥 𝑢 = 𝑥^{'} (𝑦^{'} - 𝑦) + (𝑥^{'} - 𝑥) 𝑦$ , which is an integer multiple of $𝑛$ if $𝑛 ∣ 𝑥 - 𝑥^{'}$ and $𝑛 ∣ 𝑦 - 𝑦^{'}$ . Hence $𝑥^{'} 𝑦^{'} = 𝑥 𝑦 mod 𝑛$ .
⁠ $□$

Proposition 5.7

There following are well-defined binary operations on $ℤ_{𝑛}$ :

$\overset{̅}{𝑎} + \overset{̅}{𝑏} ≔ \overset{̅}{𝑎 + 𝑏}$
$\overset{̅}{𝑎} \times \overset{̅}{𝑏} ≔ \overset{̅}{𝑎 𝑏}$

Proof. It suffices to prove (STP) that these definitions do not depend on the choices made for the two $𝛼, 𝛽 \in ℤ_{𝑛}$ :

pick $𝑎 \in 𝛼, 𝑏 \in 𝛽$
set $𝛼 + 𝛽 = \overset{̅}{𝑎 + 𝑏}$ .

If $𝑎^{'} \in 𝛼$ and $𝑏^{'} \in 𝛽$ , then $𝑎^{'} + 𝑏^{'} \equiv 𝑎 + 𝑏 mod 𝑛$ by the Lemma (TODO ref), so $\overset{̅}{𝑎^{'} + 𝑏^{'}} = \overset{̅}{𝑎 + 𝑏}$ . Similarly $\overset{̅}{𝑎^{'} 𝑏^{'}} = \overset{̅}{𝑎 𝑏}$ .⁠ $□$

Proposition 5.8

$(ℤ_{𝑛}, +)$ is an abelian group, and moreover is cyclic.
$(ℤ_{𝑛}, \times)$ satisifies associativity and commutativity, and admits an identity element
$𝑥 (𝑦 + 𝑧) = 𝑥 𝑦 + 𝑥 𝑧$ for all $𝑥, 𝑦, 𝑧 \in ℤ_{𝑛}$ .

Proof.

$\begin{matrix} \overset{̅}{𝑥} + (\overset{̅}{𝑦} + \overset{̅}{𝑧}) = \overset{̅}{𝑥} + (\overset{̅}{𝑦 + 𝑧}) = \overset{̅}{𝑧 + (𝑦 + 𝑧)} \\ = \overset{̅}{(𝑥 + 𝑦) + 𝑧} = \overset{̅}{𝑥 + 𝑦} + \overset{̅}{𝑧} = (\overset{̅}{𝑥} + \overset{̅}{𝑦}) + \overset{̅}{𝑧} . \end{matrix}$
$\overset{̅}{0} + \overset{̅}{𝑥} = \overset{̅}{0 + 𝑥} = \overset{̅}{𝑥} = \overset{̅}{𝑥 + 0} = \overset{̅}{𝑥} + \overset{̅}{0}$ , so $(ℤ_{𝑛}, +)$ admits an identity.
The inverse of $\overset{̅}{𝑥}$ is $\overset{̅}{- 𝑥}$ .
This group is cyclic because $\overset{̅}{𝑘} = \underset{𝑘 times}{\underset{⏟}{\overset{̅}{1} + \dots + \overset{̅}{1}}}$ for all $𝑘 \in ℤ_{> 0}$ .
Hence $(ℤ_{𝑛}, +)$ is generated by $\overset{̅}{1}$ . $\overset{̅}{1}$ has order $𝑜 (\overset{̅}{1}) = 𝑛$ .
Inherited from the integers in a similar manner to the above, with $\overset{̅}{1}$ as the identity.
Also inherited from the integers.
⁠ $□$

Remark 5.9

ℤ_{𝑛}

is a unital commutative ring.

Lemma 5.10

The function from ${0, 1, \dots, 𝑛 - 1} \to ℤ_{𝑛}$ defined by $𝑟 \mapsto \overset{̅}{𝑟}$ is a bijection.

Proof.

Suppose $0 \leq 𝑟, 𝑟 \leq 𝑛 - 1$ and $\overset{̅}{𝑟} = \overset{̅}{𝑠}$ . Then $𝑟 \equiv 𝑠 mod 𝑛$ , so $𝑛 ∣ 𝑟 - 𝑠$ , i.e. $𝑟 - 𝑠 = 𝑛 𝑘$ for some $𝑘 \in ℤ$ . WLOG suppose $𝑠 \geq 𝑟$ , then if $𝑘 \neq 0$ then $| 𝑠 - 𝑟 | \geq 𝑛$ . But $| 𝑠 - 𝑟 | \leq 𝑛 - 1$ , so $𝑘 = 0$ and $𝑟 = 𝑠$ . Hence the function is injective.

Now take $𝛼 \in ℤ_{𝑛}$ , and say $𝛼 = \overset{̅}{𝑎}$ for some $𝑎 \in ℤ$ . Divide $𝑎$ by $𝑛$ with remainder to get $𝑎 = 𝑞 𝑛 + 𝑟$ for some $𝑞, 𝑟 \in ℤ$ with $0 \leq 𝑟 \leq 𝑛 - 1$ .

Then $𝑛 ∣ 𝑞 𝑛 = 𝑎 - 𝑟$ , so $𝑎 \equiv 𝑟 mod 𝑛$ . Note that $𝛼 = \overset{̅}{𝑎} = \overset{̅}{𝑟}$ , so the function is surjective.

Hence the function is a bijection.⁠ $□$

Proposition 5.11

Let $\overset{̅}{𝑥}$ in $ℤ_{𝑛}$ . Then $\overset{̅}{𝑥}$ admits a multiplicative inverse iff $gcd (𝑥, 𝑛) = 1$ .
Define $ℤ_{𝑛}^{\times} ≔ {\overset{̅}{𝑥} \in ℤ_{𝑛} | \exists 𝑦 \in ℤ_{𝑛} s.t. \overset{̅}{𝑥} \overset{̅}{𝑦} = \overset{̅}{1}}$ . Then $ℤ_{𝑛}^{\times}$ is an abelian group.
For prime $𝑝$ , $ℤ_{𝑝}^{\times} = ℤ_{𝑝} \ {\overset{̅}{0}}$ , so $ℤ_{𝑝}$ is a field.

Proof.

exercise
If $\overset{̅}{𝑎}, \overset{̅}{𝑏} \in ℤ_{𝑛}^{\times}$ , then $\overset{̅}{𝑎} \overset{̅}{𝑐} = \overset{̅}{1} = \overset{̅}{𝑏} \overset{̅}{𝑑}$ for some $\overset{̅}{𝑐}, \overset{̅}{𝑑} \in ℤ_{𝑛}$ . Hence $(\overset{̅}{𝑎} \overset{̅}{𝑏}) (\overset{̅}{𝑐} \overset{̅}{𝑑}) = (\overset{̅}{𝑎} \overset{̅}{𝑐}) (\overset{̅}{𝑏} \overset{̅}{𝑑}) = \overset{̅}{1} \cdot \overset{̅}{1} = \overset{̅}{1}$ .
Let $\overset{̅}{0} \neq \overset{̅}{𝑥} \in ℤ_{𝑝}$ . Then $𝑝 ∤ 𝑥$ . Since $𝑝$ is prime, $gcd (𝑝, 𝑥) = 1$ . Hence by (a), $\overset{̅}{𝑥} \in ℤ_{𝑛}^{\times}$ .⁠ $□$

6. Cosets & Lagrange’s Theorem

Definition 6.1

Let $𝐻 \leq 𝐺$ not necessarily finite.

A left coset of $𝐻$ is a subset of $𝐺$ of the form $𝑔 𝐻$ for some $𝑔 \in 𝐺$ , where

𝑔 𝐻 ≔ {𝑔 ℎ | ℎ \in 𝐻} .

A right coset of $𝐻$ is a subset of $𝐺$ of the form $𝐻 𝑔$ for some $𝑔 \in 𝐺$ , where

𝐻 𝑔 ≔ {ℎ 𝑔 | ℎ \in 𝐻} .

Definition 6.2

We write

𝐺 / 𝐻

(“

𝐺

mod

𝐻

”) to mean the set of left cosets of

𝐻

𝐺

; we write

𝐻 \ 𝐺

to mean the set of right cosets of

𝐻

𝐺

Definition 6.3

The index of $𝐻$ in $𝐺$ is

[𝐺 : 𝐻] ≔ | 𝐺 / 𝐻 | .

Example 6.4

$𝐺 = (ℤ, +)$ ; fix $𝑛 \in ℤ_{> 0}$ .

Let $𝐻 = ⟨ 𝑛 ⟩ = {𝑛 𝑎 | 𝑎 \in ℤ = 𝑛 ℤ}$ .

The left cosets of $𝐻$ are

{0 + 𝑛 ℤ, 1 + 𝑛 ℤ, 2 + 𝑛 ℤ, \dots, 𝑛 - 1 + 𝑛 ℤ} .

Hence $ℤ / 𝑛 ℤ = ℤ_{𝑛}$ .

Remark 6.5

𝐺

is abelian, then its left cosets are the same as its right cosets.

Remark 6.6

In general

| 𝐺 / 𝐻 | = | 𝐻 \ 𝐺 |

Lemma 6.7 (Coset Equality Lemma)

Let $𝐻 \leq 𝐺$ and $𝑔_{1}, 𝑔_{2} \in 𝐺$ .

Then $𝑔_{1} 𝐻 = 𝑔_{2} 𝐻$ iff $𝑔_{2}^{- 1} 𝑔_{1} \in 𝐻$ .

Proof.

“ $⟹$ ”:

\begin{aligned} 𝑒 \in 𝐻 & ⟹ 𝑔_{1} 𝑒 \in 𝑔_{1} 𝐻 \\ ⟹ 𝑔_{1} \in 𝑔_{2} 𝐻 \\ ⟹ \exists ℎ \in 𝐻 s.t. 𝑔_{1} = 𝑔_{2} ℎ . \end{aligned}

Hence $𝑔_{2}^{- 1} 𝑔_{1} = ℎ \in 𝐻$ .

“ $⟸$ ” :

Suppose $𝑔_{2}^{- 1} 𝑔_{1} \in 𝐻$ , then $𝑔_{1} 𝐻 = 𝑔_{2} 𝑔_{2}^{- 1} 𝐻 = 𝑔_{2} 𝐻$

because $𝑥 \in 𝐻$ , then $𝑥 𝐻 = {𝑥 ℎ | ℎ \in 𝐻} = 𝐻$ .⁠ $□$

Remark 6.8

Left cosets have the property that if

𝑥 \in 𝐺

and

𝑔 𝐻 \in 𝐺 / 𝐻

, then

𝑥 𝑔 𝐻 \in 𝐺 / 𝐻

Theorem 6.9 (Lagrange's Theorem)

For $𝐺$ a finite group, and $𝐻 \leq 𝐺$ a subgroup of $𝐺$ , then $| 𝐻 | ∣ | 𝐺 |$ .

Proof. We will show that $𝐺 / 𝐻$ forms a partition of $𝐺$ , and that $\forall 𝑔_{1} 𝐻, 𝑔_{2} 𝐻 \in 𝐺 / 𝐻$ , $| 𝑔_{1} 𝐻 | = | 𝑔_{2} 𝐻 |$ .

$𝑔 𝐻 ∋ 𝑔 ⟹ 𝑔 𝐻 \neq \emptyset$ . Moreover, if $𝑔 \in 𝐺$ , then

𝑔 = 𝑔 𝑒 \in 𝑔 𝐻 ⟹ 𝐺 = ⋃_{𝐶 \in 𝐺 / 𝐻} 𝐶 .

If $𝑔_{1} 𝐻$ and $𝑔_{2} 𝐻$ are not disjoint, then $\exists 𝑥 \in 𝑔_{1} \cap 𝑔_{2} 𝐻$ . We write $𝑥 = 𝑔_{1} ℎ_{1} = 𝑔_{2} ℎ_{2}$ for some $ℎ_{1}, ℎ_{2} \in 𝐻$ .

Then $𝑔_{2}^{- 1} 𝑔_{1} = ℎ_{2} ℎ_{1}^{- 1} \in 𝐻$ as $𝐻 \leq 𝐺$ .

Hence by the Coset Equality Lemma, $𝑔_{1} 𝐻 = 𝑔_{2} 𝐻$ . Therefore distinct left cosets are disjoint.

Say that $𝐺 / 𝐻 = {𝑔_{1} 𝐻, 𝑔_{2} 𝐻, \dots, 𝑔_{𝑛} 𝐻}$ where $𝑛 = | 𝐺 / 𝐻 |$ .

The function $𝜑 : 𝐻 \to 𝑔_{𝑖} 𝐻; ℎ \mapsto 𝑔_{𝑖} ℎ$ is a bijection, with inverse $𝑦 \mapsto 𝑔_{𝑖}^{- 1} 𝑦$ . Hence $| 𝑔_{𝑖} 𝐻 | = | 𝐻 | = | 𝑔_{𝑖} 𝐻 |$ .

Then $| 𝐺 | = \sum_{𝑖 = 1}^{𝑛} | 𝑔_{𝑖} 𝐻 | = 𝑛 | 𝐻 | = [𝐺 : 𝐻] | 𝐻 |$ .

⁠ $□$

Corollary 6.9.1

For $𝐺$ a finite group and $𝑔 \in 𝐺$ , then $𝑜 (𝑔) ∣ | 𝐺 |$ .

Proof. Recall that $𝑜 (𝑔) = min {𝑛 \in ℤ_{> 0} | 𝑔^{𝑛} = 𝑒}$ , but also $𝑜 (𝑔) = | ⟨ 𝑔 ⟩ |$ . By Lagrange’s Theorem, $| ⟨ 𝑔 ⟩ | ∣ | 𝐺 |$ , so $𝑜 (𝑔) ∣ | 𝐺 |$ .⁠ $□$

Corollary 6.9.2

Suppose $𝑝$ is prime and $𝐺$ is a group of order $𝑝$ . Then $𝐺 ≅ 𝐶_{𝑝}$ , and all non-identity elements of $𝐺$ have order $𝑝$ .

Proof. By Corollary 6.9.1, for $𝑔 \in 𝐺$ , $𝑜 (𝑔) = 1$ or $𝑜 (𝑔) = | 𝐺 |$ . $𝑜 (𝑔) = 1$ iff $𝑔 = 𝑒$ , so for all $𝑔 \in 𝐺 \ {𝑒}$ , $𝑜 (𝑔) = 𝑝$ .

Now pick some $𝑔 \in 𝐺$ s.t. $𝑔 \neq 𝑒$ , then $⟨ 𝑔 ⟩ ≅ 𝐶_{𝑜 (𝑔)} = 𝐶_{𝑝}$ .⁠ $□$

Corollary 6.9.3

If $𝐺$ is a finite group, $𝑔 \in 𝐺$ , then $𝑔^{| 𝐺 |} = 𝑒$ .

Proof. From Corollary 6.9.1, $| 𝐺 | = 𝑟 \cdot 𝑜 (𝑔)$ for some $𝑟 \in ℕ$ . Hence

𝑔^{𝐺} = 𝑔^{𝑟 \cdot 𝑜 (𝑔)} = {(𝑔^{𝑜 (𝑔)})}^{𝑟} = 𝑒^{𝑟} = 𝑒 .

Theorem 6.10 (Euler's Totient Theorem)

Let $𝑛 \geq 2$ , and let $𝑎 \in ℤ$ be coprime to $𝑛$ . Then

𝑎^{𝜙 (𝑛)} \equiv 1 mod 𝑛,

where

𝜙 (𝑛) ≔ | ℤ_{𝑛}^{\times} | = | {0 < 𝑘 < 𝑛 | gcd (𝑘, 𝑛) = 1} | .

Proof. Apply Corollary 6.9.3 to $ℤ_{𝑛}^{\times}$ :

\begin{matrix} 𝑎 + 𝑛 ℤ \in ℤ_{𝑛}^{\times}, | ℤ_{𝑛} | = 𝜙 (𝑛) \\ ⟹ {(𝑎 + 𝑛 ℤ)}^{𝜙 (𝑛)} = 1 + 𝑛 ℤ \\ ⟹ 𝑎^{𝜙 (𝑛)} = 1 mod 𝑛 . \end{matrix}

⁠ $□$

Theorem 6.11 (Fermat's Little Theorem)

For prime $𝑝$ and $𝑎 \in ℤ$ coprime to $𝑝$ ,

𝑎^{𝑝 - 1} \equiv 1 mod 𝑝 .

Proof. Apply Euler’s Totient Theorem with $𝑛 = 𝑝$ :

𝜙 (𝑝) = | ℤ_{𝑝}^{\times} | = | {\overset{̅}{1}, \overset{̅}{2}, \dots, 𝑝 - 1} | = 𝑝 - 1 .

Theorem 6.12 (Wilson's Theorem)

For prime $𝑝$ , $(𝑝 - 1)! \equiv - 1 mod 𝑝$ .

Proof. Let $𝐺$ be a finite group and define $\sim$ , a relation on $𝐺$ by

𝑥 \sim 𝑦 ⟺ 𝑦 = 𝑥 \lor 𝑦 = 𝑥^{- 1} .

$\sim$ is an equivalence relation; reflexivity is obvious, symmetry is by taking inverse of both sides, and transitivity is also simple.

Then

𝐺 = {𝑔 \in 𝐺 | 𝑥 = 𝑥^{- 1}} \cup ⋃_{\begin{matrix} 𝑦 \in 𝐺; \\ 𝑦 \neq 𝑦^{- 1} \end{matrix}} {𝑦, 𝑦^{- 1}} .

Then if $𝐺$ is finite, and $𝑚 ≔ {𝑥 \in 𝐺 | 𝑥 = 𝑥^{- 1}}$ , then $| 𝐺 | \equiv 𝑚 mod 2$ .

We then apply these ideas to $ℤ_{𝑝}^{\times} = {𝑥 \in ℤ_{𝑝}^{\times} | 𝑥 = 𝑥^{- 1}} \cup ⋃_{𝑦 \in ℤ_{𝑝}^{\times}} {𝑦, 𝑦^{- 1}}$ .

Consider $\prod_{𝑥 \in ℤ_{𝑝}^{\times}} 𝑥$ . This is $\overset{̅}{(𝑝 - 1)!}$ . Since the $𝑦$ s cancel with $𝑦^{- 1}$ ,

\overset{̅}{(𝑝 - 1)!} = \prod_{\begin{matrix} \overset{̅}{𝑥} \in 𝕏_{𝑝}^{\times}; \\ \overset{̅}{𝑥} = {\overset{̅}{𝑥}}^{- 1} \end{matrix}} \overset{̅}{𝑥} .

But $\overset{̅}{𝑥} = {\overset{̅}{𝑥}}^{- 1} ⟺ {\overset{̅}{𝑥}}^{2} = \overset{̅}{1} ⟺ (\overset{̅}{𝑥} - \overset{̅}{1}) (\overset{̅}{𝑥} + \overset{̅}{1}) = 0$ .

Since $ℤ_{𝑝}$ is a field, ${\overset{̅}{𝑥}}^{2} = \overset{̅}{1} ⟹ \overset{̅}{𝑥} = \overset{̅}{1}$ or $\overset{̅}{𝑥} = - \overset{̅}{1}$ .

Hence $\overset{̅}{(𝑝 - 1)!} = \overset{̅}{1} \cdot \overset{̅}{- 1} = \overset{̅}{- 1}$ .

⁠ $□$

Corollary 6.12.1

Given a group $𝐺$ with $| 𝐺 |$ even, then $\exists 𝑔 \in 𝐺$ with $𝑜 (𝑔) = 2$ .

Proof. Consider ${𝑔, 𝑔^{- 1}}$ for each $𝑔 \in 𝐺$ . $| {𝑔, 𝑔^{- 1}} | = 2$ iff $𝑔 \neq 𝑔^{- 1}$ iff $𝑔^{2} \neq 𝑒$ .

That is, $| {𝑔, 𝑔^{- 1}} | = 1$ iff $𝑔^{2} = 𝑒$ iff $𝑔 = 𝑒$ or $𝑜 (𝑔) = 2$ .

Now $𝐺 = ⋃_{𝑔 \in 𝐺} {𝑔, 𝑔^{- 1}}$ so $| 𝐺 | \equiv 1 + | {𝑔 \in 𝐺 : 𝑜 (𝑔) = 2} | mod 2$ . Since $| 𝐺 |$ is even by assumption, there must exist at least one (in fact, an odd number of) $𝑔$ with $𝑜 (𝑔) = 2$ .⁠ $□$

Theorem 6.13

Let $𝑝 \geq 3$ be prime, and let $𝐺$ be a group with $| 𝐺 | = 2 𝑝$ . Then either $𝐺 ≅ 𝐶_{2 𝑝}$ or $𝐺 ≅ 𝐷_{2 𝑝}$ .

Proof. By Lagrange’s Theorem, $\forall 𝑔 \in 𝐺$ , $𝑜 (𝑔) = | ⟨ 𝑔 ⟩ | ∣ | 𝐺 |$ .

Since $𝑝 \geq 3$ is prime, this forces $𝑜 (𝑔) \in {1, 2, 𝑝, 2 𝑝}$ .

If $\exists 𝑔 \in 𝐺$ with $𝑜 (𝑔) = 2 𝑝$ , then $𝐺 = ⟨ 𝑔 ⟩ ≅ 𝐶_{2 𝑝}$ .

Suppose then $∄ 𝑔 \in 𝐺$ with $𝑜 (𝑔) = 2 𝑝$ .

If $\forall 𝑔 \in 𝐺, 𝑜 (𝑔) = 1$ or 2, then $𝑔^{2} = 𝑒$ for all $𝑔 \in 𝐺$ . In this case, $𝐺 ≅ 𝐶_{2}^{𝑛}$ for some $𝑛 \in ℕ$ . Then $2 𝑝 = | 𝐺 | = 2^{𝑛}$ which is a contradiction.

Therefore, $\exists 𝑥 \in 𝐺$ with $𝑜 (𝑥) = 𝑝$ .

Moreover, by Corollary TODO, $\exists 𝑦 \in 𝐺$ with $𝑜 (𝑦) = 2$ .

Now we have $⟨ 𝑥 ⟩, ⟨ 𝑥 ⟩ 𝑦 \subseteq 𝐺$ .

Note that these are disjoint: suppose that $𝑥^{𝑖} = 𝑥^{𝑗} 𝑦$ , then $𝑦 = 𝑥^{𝑖 - 𝑗} \in ⟨ 𝑥 ⟩$ so $2 ∣ | ⟨ 𝑥 ⟩ | = 𝑝$ , which is a contradiction.

Hence $𝐺 = ⟨ 𝑥 ⟩$ TODO⟨𝑥⟩𝑦={𝑥𝑖𝑦𝑗|0≤𝑖≤𝑝−1,𝑜≤𝑗≤1}.

Now note that

\begin{aligned} 𝑦 𝑥 𝑦^{- 1} \in (𝑦 ⟨ 𝑥 ⟩) 𝑦^{- 1} & = (𝐺 - ⟨ 𝑥 ⟩) 𝑦^{- 1} \\ = ⟨ 𝑥 ⟩ 𝑦 𝑦^{- 1} \\ = ⟨ 𝑥 ⟩ . \end{aligned}

Then $𝑦 𝑥 𝑦^{- 1} = 𝑥^{𝑖}$ for some $0 \leq 𝑖 \leq 𝑝 - 1$ .

Now $𝑥 = 𝑦^{2} 𝑥 𝑦^{- 2} = 𝑦 (𝑦 𝑥 𝑦^{- 1}) 𝑦^{- 1} = 𝑦 (𝑥^{𝑖}) 𝑦^{- 1} = {(𝑦 𝑥 𝑦^{- 1})}^{𝑖} = {(𝑥^{𝑖})}^{𝑖} = 𝑥^{𝑖^{2}}$ .

Hence $𝑖^{2} \equiv 1 mod 𝑝$ as $𝑜 (𝑥) = 𝑝$ .

Since $𝑝$ is prime, this forces $𝑖 = 1$ or $𝑖 \equiv - 1 mod 𝑝$ , so $𝑖 - 1$ or $𝑖 = 𝑝 - 1$ .

If $𝑖 = 1$ , then $𝑦 𝑥 𝑦^{- 1} = 𝑥 ⟹ 𝑦 𝑥 = 𝑥 𝑦$ , so $𝑜 (𝑥 𝑦) ∣ 2 𝑝$ . ${(𝑥 𝑦)}^{2} = 𝑥^{2} 𝑦^{2} = 𝑥^{2} \neq 𝑒 ⟹ 𝑜 (𝑥 𝑦) \neq 2$ . Similarly ${(𝑥 𝑦)}^{𝑝} = 𝑥^{𝑝} 𝑦^{𝑝} = 𝑦 \neq 𝑒 \Rightarrow 𝑜 (𝑥 𝑦) \neq 𝑝$ . So $𝑖 = 𝑝 - 1$ .

Therefore

𝐺 = {𝑥^{𝑖} 𝑦^{𝑗} | 0 \leq 𝑖 \leq 𝑝 - 1, 0 \leq 𝑗 \leq 1}

and $𝑦 𝑥 𝑦^{- 1} = 𝑥^{𝑝_{1}} = 𝑥^{- 1}$ .

Hence $𝐺 ≅ 𝐷_{2 𝑝}$ .⁠ $□$

7. Homomorphisms

Definition 7.1

Let

𝐺, 𝐻

be groups. A function

𝜑 : 𝐺 \to 𝐻

is a homomorphism if

𝜑 (𝑔_{1} *_{𝐺} 𝑔_{2}) = 𝜑 (𝑔_{1}) \times_{𝐻} 𝜑 (𝑔_{2})

for all

𝑔_{2}, 𝑔_{2} \in 𝐺

Remark 7.2

An isomorphism is a bijective homomorphism.

Definition 7.3

A monomorphism is an injective homomorphism. We write

𝐺 ↪︎ 𝐻

Definition 7.4

A epimorphism is a surjection homomorphism. We write

𝐺 ↠ 𝐻

Example 7.5

Definition 7.6

The trivial homomorphism is the homomorphism

𝜑 : 𝐺 \to 𝐺; 𝑔 \mapsto 𝑒_{𝐻}

Example 7.7

Linear maps between vector spaces are group homomorphisms (under addition).

Theorem 7.8

$Hom (ℤ, 𝐺) ≅ 𝐺$ .

Proof. Let $𝜑_{𝑔} : ℤ \to 𝐺$ be defined by $𝑛 \mapsto 𝑔^{𝑛}$ for each $𝑔 \in 𝐺$ .

Then STP that the function $𝐺 \to Hom (ℤ, 𝐺); 𝑔 \mapsto 𝜑_{𝑔}$ is bijective.

If $𝑔, ℎ \in 𝐺$ and $𝜑_{𝑔} = 𝜑_{ℎ}$ , then $𝑔 = 𝜑_{𝑔} (1) = 𝜑_{ℎ} (1) = ℎ$ , so $𝑔 \mapsto 𝜑_{𝑔}$ is injective.

Let $𝜓 : ℤ \to 𝐺$ be a homomorphism, then if $𝑔 ≔ 𝜓 (1) \in 𝐺$ , then $𝜑_{𝑔} (𝑛) = 𝑔^{𝑛} = {𝜓 (1)}^{𝑛} = 𝜓 (𝑛)$ for all $𝑛 \in ℤ$ . Then $𝜓 = 𝜑_{𝑔}$ , so $𝑔 \mapsto 𝜑_{𝑔}$ is surjective.⁠ $□$

Definition 7.9

An automorphism of

𝐺

is an isomorphism

𝜓 : 𝐺 \to 𝐺

Remark 7.10

Automorphisms form a group

Aut (𝐺)

under composition.

Definition 7.11

Fix

𝑔 \in 𝐺

. Define

𝜃_{𝑔} : 𝐺 \to 𝐺

𝑥 \mapsto 𝑔^{- 1} 𝑥 𝑔

;

𝜃_{𝑔}

is the conjugation by

𝑔

Proposition 7.12

$𝜃_{𝑔}$ is an automorphism.

Proof. $𝜃_{𝑔} (𝑥 𝑦) = 𝑔^{- 1} 𝑥 𝑦 𝑔 = 𝑔^{- 1} 𝑥 𝑔 𝑔^{- 1} 𝑦 𝑔 = 𝜃_{𝑔} (𝑥) 𝜃_{𝑔} (𝑦)$ . Hence each $𝜃_{𝑔}$ is a homomorphism.

Moreover, $𝜃_{𝑔}$ is invertible : $𝜃_{𝑔}^{- 1} = 𝜃_{𝑔^{- 1}}$ .⁠ $□$