Z over nZ - The Integers Modulo n

Let $n$ be a fixed positive integer. Define a relation on $Z$ by:

a \sim b ⟺ n | (b - a)

clearly $a \sim a, a \sim b \to b \sim a$ so the relation is trivially reflexive and symmetric. Further work shows it's transitive too, so then $\sim$ is an equivalence relation, so we can write:

a \sim b \Rightarrow a \equiv b (mod n)

For any $k \in Z$ we'll denote the equivalence class of $a$ as $\overset{―}{a}$ , named the congruence/residue class of $a$ . It consists of the integers from $a$ that by an integral multiple of $n$ (using the relation above), ie:

\begin{aligned} \overset{―}{a} & = {a + k n | k \in Z} \\ = {a, a \pm n, a \pm 2 n, \dots} \end{aligned}

There are precisely $n$ distinct equivalence classes $mod n$ , namely:

\overset{―}{0}, \overset{―}{1}, \dots, \overset{―}{n - 1}

determined by the possible remainders after division by $n$ .

\frac{Z}{n Z}

The groups $\frac{Z}{n Z}$ are the sets of equivalence classes $\overset{―}{0}, \overset{―}{1}, \dots, \overset{―}{n - 1}$ such that each one describes the integers with remainder of the equivalence class.

\frac{Z}{6 Z}

There are 6 possible remainders here:

\overset{―}{0}, \overset{―}{1}, \overset{―}{2}, \overset{―}{3}, \overset{―}{4}, \overset{―}{5}

Where, for example, $\overset{―}{2} = {\dots, - 10, - 4, 2, 8, \dots}$ .

A cool thing here is that any element of the equivalence class can represent it. Namely:

\dots = \overset{―}{- 4} = \overset{―}{0} = \overset{―}{6} = \overset{―}{12} = \dots

Some Properties

For $(\frac{Z}{n Z}, +)$ then $\overset{―}{a} + \overset{―}{b} = \overset{―}{a + b}$ (so it's an Abelian Group of order $n$ )
For $(\frac{Z}{n Z}, \cdot)$ then $\overset{―}{a} \overset{―}{b} = \overset{―}{a b}$ (almost an Abelian Group, but it lacks the inverse for some elements like $\overset{―}{0}$ )
- Here $\overset{―}{a} \in \frac{Z}{n Z}$ has in inverse under $\cdot$ iff $gcd (a, n) = 1$ .

\frac{Z}{6 Z}

Here:

- \overset{―}{2} = \overset{―}{- 2} = \overset{―}{4}

\overset{―}{1} \cdot \overset{―}{1} = \overset{―}{1}

\overset{―}{5} \cdot \overset{―}{5} = \overset{―}{25} = \overset{―}{1}

Notice that $\overset{―}{1}, \overset{―}{5}$ are the only elements with other.

The group ${(\frac{Z}{n Z})}^{\times} = {\overset{―}{a} \in \frac{Z}{n Z} | gcd (a, n) = 1}$ is an Abelian Group under $\cdot$ .
- Back in the day, they used $\overset{―}{a} = \overset{―}{b} ⟺ a \equiv b (mod n)$ . In $\frac{Z}{n Z}$ this is " $a$ congruent to $b$ modulo $n$ ".

Permutation Group

Consider the Permuation Group. Any finite set $X$ will have perumations:

permuation

A permutation of $X$ is a bijection $σ : X \to X$ . It's essentially a shuffling of the elements in $X$ .

X = {1, 2, 3, 4, 5}

Count the number of bijections $σ : X \to X$ . Using principles of proofs, this is the number of injections $σ : X \to X$ (since $X$ is finite). Once we know where $1$ goes we have 5 options, then for 2 we have 4 options, ... so then we have $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5! = 120$ possibilities.

There are some notational options here (which is where the old-timey modulo notation comes into play):

(Functional Notation:) one permuation is: $σ (1) = 2, σ (2) = 3, σ (3) = 5, σ (4) = 1, σ (5) = 4$ . This is obviously super slow so we don't want to do this one.
(Modified Functional Notation:) write it instead with $\to$ : $1 \mapsto 2, 2 \mapsto 3, \dots$ .
(Use A Table:) write where the top row maps to the bottom row:

(\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 5 & 1 & 4 \end{matrix})

("Cycle Notation":) write out a visual graph of what number maps to where:

We write this as:

σ = (\begin{matrix} 1 & 2 & 3 & 5 & 4 \end{matrix})

Another example would be:

τ = (\begin{matrix} 1 & 3 & 5 \end{matrix}) (\begin{matrix} 2 & 4 \end{matrix})

Creates the following:

Here $τ$ has a 3-cycle and a 2-cycle (or a transposition). This $τ$ is a product of disjoint cycles. Notice that since we have a cycle where $n \geq 3$ then the group isn't abelian with operation $τ$ .