9.6. Group Theory

Some facts about group theory especially cyclic groups are helpful to give a theoretic foundation for modulo arithmetic.

9.6.1. Subgroups

Definition:

A subgroup of a group is a subset of the group which is a group under the group operation restriceted to the subgroup.

E.g. the even integers \(2\mathbb{Z} = \{ \ldots,-2, 0, 2, 4, \ldots\}\) is a subgroup of the integers under addition.

Some facts:

• A subgrroup contains the neutral element.

• A subgroup is closed under the group operation and the inverse operation.

9.6.2. The Integers mod n

Definition:

Two integers \(a\) and \(b\) are equivalent mod \(n\) if \(n\) divides \(a - b\). We denote the equivalence classes by \(\mathbb{Z}_n\).

E.g. the integers mod 3 have 3 equivalence classes:

[0] := { …, -6, -3, 0, 3, 6, … }

[1] := { …, -5, -2, 1, 4, 7, … }

[2] := { …, -4, -1, 2, 5, 8, … }

The set of equivalence classes form a group with the natural embedding \([n] \mapsto n\) and the group operation \([a] + [b] := [a + b\; mod\; n]\). Furthermore we can define a multiplication \([ab] := [ab \; mod \; n]\).

9.6.3. Cyclic Subgroups

Definition:

Let \(G\) be a group and \(a\) be an element of the group. Then we define \(\langle a \rangle := \{a^n: n \in \mathbb{Z}\}\) where \(a^0 = e\) with the neutral element \(e\), \(a^{n+1} = a a^n\) and \(a^{-n} = (a^{n})^{-1}\).

Theorem:

\(\langle a \rangle\) is a subgroup of \(G\). It is the smallest subgroup of \(G\) containing the element \(a\).

Definition:

\(\langle a \rangle\) is the cyclic subgroup of \(G\) generated by \(a\). If \(G = \langle a \rangle\) then \(G\) is a cyclic group.

Definition:

We call the smallest integer \(n\) such that \(a^n = e\) the order of the group \(\langle a \rangle\). The order of \(\langle a \rangle\) is infinite, if no such number exists.

Theorem:

Every cyclic group is abelian.

Theorem:

Every subgroup of a cyclic group is cyclic.

The group of integers is cyclic because \(\mathbb{Z} = \langle 1 \rangle\).