September 10th, 2026

For any set $S$, we define a permutation $p$ of $S$ as a bijection $p: S \to S$. If $p$ leaves all points in $S$ fixed, we say $p$ is the identity permutation. If $|S| < \infty$, we can define a permutation matrix $P$ such that $Pe_k = e_{p(k)}$ for each standard basis vector $e_k$ for $\bR^{|S|}$.

Let $S = \{1, \dots, 5\}$. Define the permutation $p: S \to S$ by the following table.

It is common to represent permutations with cycle notation. To write a permutation $p$ in cycle notation, we simply choose one index $i \in S$ and chase it with $p$ until all elements in $S$ are achieved, or until we hit a loop. For example, let $i = 3$. Then note $3 \to 4 \to 1$, where the arrow denotes applying $p$, and this completes one cycle. Since we did not complete cycling through $S$, we choose any other element from $S$. Choose $2 \in S$, then note $2 \to 5$. Thus our permutation's action is simply denoted by the sequence

where the arrow denotes applying $p$. In terser notation, we say $p = (3\,\,4\,\,1)(2\,\,5)$.

An $n$-cycle is a cycle with $n$ indices. A $2$-cycle is said to be a transposition, since the permutation simply acts by swapping the two indices. For example, $(2\,\,5)$ is a transposition, since $2$ is swapped with $5$ and vice versa under $p$. A $1$-cycle is a fixed point under $p$, and we tend to omit it. If all elements of $S$ are fixed points under $p$, then $p$ is simply the identity permutation, denoted $p = 1$.

Suppose $p: S \to S$ is a permutation over a finite set $S$. Then we define the sign of the permutation $p$, denoted $\sgn(p)$, by the determinant of the permutation matrix $P$ induced by $p$. Immediately we have that $\sgn(p) \in \{ 1,-1 \}$—we say that $p$ is even if $\sgn(p) = 1$, otherwise $p$ is odd ($\sgn(p) = -1$).

There are two equivalent ways to view the sign of a permutation. From the linear-algebraic perspective, $\sgn(p)$ is simply the determinant of the permutation matrix induced by $p$. From the group-theoretic perspective, every cycle

may be decomposed into transpositions as

Thus a $k$-cycle is a product of $k - 1$ transpositions. More generally, every permutation of a finite set can be written as a product of transpositions, say

and we may equivalently define

Although such a decomposition is not unique, the parity of $m$ is strictly independent of the chosen decomposition.

A group is a set $G$ together with a map $G \times G \to G$, called the group operation, satisfying the following requirements.

1. Associativity. For any $a, b, c \in G$, applying the group operation to $(ab, c)$ yields the same element in $G$ as applying it to $(a, bc)$.

2. Identity. There is some element $1 \in G$ such that, for any $g \in G$, we have that $(g, 1) \mapsto g$ and $(1, g) \mapsto g$.

3. Inverse. For every $g \in G$, there is some element $g^{-1} \in G$ such that $(g, g^{-1}) \mapsto 1$ and $(g^{-1}, g) \mapsto 1$.

If, for any $a, b \in G$, we have that $(a, b)$ and $(b, a)$ have the same image under the group operation, the group operation is commutative. A group together with a commutative operation is said to be an abelian group.

The group of integers together with the addition operation forms an abelian group. Note that $\bZ$ together with multiplication is not a group (elements like $2$ have no multiplicative inverse in $\bZ$), but the set of non-zero rationals $\bQ \setminus \{0\}$ together with multiplication is.

Fix $n \in \bZ_+$. The symmetric group of order $n$, denoted $S_n$, is the group of all permutations on the set $\{1, \dots, n\}$, where the group operation is function composition. The general linear group of order $n$, denoted $GL_n(\bF)$, is the group of all $n \times n$ invertible matrices over a field $\bF$, where the group operation is matrix multiplication.

A group is typically said to be either “multiplicative” or “additive”, and the operation is said to be multiplication or addition respectively. Multiplication is denoted by juxtaposition, whereas addition is denoted by $+$. Unless otherwise stated, we take a group to be multiplicative and its operation to be denoted by juxtaposition.

Fix a group $G$. By definition, note that for any $a, b \in G$, we have that $ab \in G$ (again, recall $ab$ is simply the group operation applied to $a$ and $b$). When a structure is such that an operation on it keeps elements in the set, we say that it is closed. Accordingly, $G$ is inherently closed with respect to its group operation.

It is taken for granted that the identity and inverse elements are unique, as these fall out immediately from the axioms.

The order of a group $G$ is its cardinality as a set, denoted $|G|$. A group is said to be a finite group if its order is finite. For example, the symmetric group $S_n$ has order $|S_n| = n!$.

Let $S$ be a set, which we call an alphabet whose elements are letters. We formally construct a set of inverses $S^{-1} = \{s^{-1} : s \in S\}$. A word is a finite sequence of characters from $S \cup S^{-1}$. A word is reduced if it contains no adjacent inverse pairs $s s^{-1}$ or $s^{-1} s$.

The free group generated by $S$, denoted $F(S)$, is the set of all reduced words. The group operation is string concatenation followed by reduction, and the identity is the empty word.

Let $S$ be an alphabet, $G$ be an arbitrary group, and $f: S \to G$ be a map of sets assigning each letter to an element in $G$. There exists a unique group homomorphism $\phi: F(S) \to G$ extending $f$, mapping each reduced word to the corresponding product in $G$.

Let $S$ be an alphabet and $R \subseteq F(S)$ be a set of words, called relations or constraints. To form a group where every word in $R$ collapses to the identity, we must mod out by $R$. Because we can only quotient by normal subgroups, we define $N(R)$ as the normal closure of $R$ in $F(S)$—the intersection of all normal subgroups containing $R$, which precisely consists of all finite products of conjugates of words in $R$.

The group presentation $\langle S \mid R \rangle$ is defined as the quotient group

Consider $S_3$, which consists of all permutations on $\{1, 2, 3\}$. Let $x = (1\,\,2\,\,3)$ and $y = (1\,\,2)$. Computing their compositions, we note $x^3 = 1$, $y^2 = 1$, and $yx = (2\,\,3) = x^2y$.

This last constraint, $yx = x^2y$, forces the word $yxy^{-1}x^{-2}$ to equal the identity. We claim that $S_3$ is precisely the free group on $\{x, y\}$ modded out by the normal closure of these constraint words.

$S_3 \cong \langle x, y \mid x^3 = 1, y^2 = 1, yx = x^2y \rangle$.

Suppose $G$ is a group. A subset $H \subseteq G$ is said to be a subgroup if the following properties are satisfied.

1. Closure. For any $a, b \in H$, we have that $ab \in H$.

2. Identity. We have that the identity $1$ from $G$ is contained in $H$.

3. Inverse. Each element in $H$ has an inverse contained in $H$.

Equivalently, $H$ is a subgroup of $G$ if $H$ is a group with respect to the group operation inherited from $G$.

All subgroups of $\bZ^+$ take the form of either the trivial group $\{0\}$ or the set $a\bZ = \{an: n \in \bZ\}$, for some $a \in \bZ_+$.

Fix $a, b \in \bZ_+$. Note that $a\bZ \subseteq b\bZ$ if and only if $b \mid a$ (i.e., $b$ divides $a$). The logic is straightforward: a larger subgroup requires a smaller generator (step size). We will consider two natural set operations on $a\bZ$ and $b\bZ$, namely intersection and addition, to motivate their arithmetic counterparts.

First, consider $a\bZ \cap b\bZ$. Note that $x \in a\bZ \cap b\bZ$ if and only if $x$ is a multiple of both $a$ and $b$. It's quick to show $a\bZ \cap b\bZ$ is a subgroup of $\bZ^+$, and so

for some unique positive integer $d$. Because $d$ generates the set of all common multiples, it must be the smallest positive number in the intersection, which is precisely the least common multiple of $a, b$. Thus $d = \lcm(a, b)$.

Now consider the sum

which is the smallest subgroup of $\bZ^+$ containing both $a\bZ$ and $b\bZ$. Note this sum must also equal $c\bZ$ for a unique positive integer $c$. The inclusions $a\bZ \subseteq c\bZ$ and $b\bZ \subseteq c\bZ$ force $c \mid a$ and $c \mid b$, making $c$ a common divisor; because $c\bZ$ is the minimal subgroup containing both, its generator $c$ must have the largest possible step size, identifying $c$ uniquely as $\gcd(a, b)$. As an immediate corollary, since $c \in c\bZ = a\bZ + b\bZ$, there exist integers $r, s \in \bZ$ such that $ra + sb = \gcd(a, b)$, a result famously known as Bézout's Lemma.