The Group of Integers Modulo n

The Group of Integers Modulo n

Recall from the Groups page that a group a set $G$ with a binary operation $* : G \times G \to G$ where:

  • For all $a, b \in G$ we have that $(a * b) \in G$ (Closure under $*$).
  • For all $a, b, c \in G$ we have that $(a * b) * c = a * (b * c)$ (Associativity of $*$).
  • There exists an element $e \in G$ such that $a * e = a$ and $e * a = a$ (The existence of an identity for $*$).
  • For all $a \in G$ there exists a $a^{-1} \in G$ such that $a * a^{-1} = e$ and $a^{-1} * a = e$ (The existence of inverses for each element in $G$).

We will now look at the group of integers modulo $n$ denoted $\mathbb{Z}_n = \{ 0, 1, 2, ..., n - 1 \}$ for integers $n > 1$. For each of these groups, define the operation of $*$ for $x, y \in \mathbb{Z}_n$ by:

(1)
\begin{align} \quad x * y = \mathrm{the \: remainder \: when} \: x + y \: \mathrm{is \: divided \: by} \: n. \end{align}

Recall from the Modular Arithmetic page that we can can rewrite this operation for $x, y \in \mathbb{Z}_n$ to be:

(2)
\begin{align} \quad x * y = (x + y) \mod n \end{align}

The operation $*$ above has a very nice interpretation. For any $n > 1$ we can interpret the operation of $*$ on $\mathbb{Z}_n$ for $x * y$ by considering a circle numbered $0$ through $n - 1$ clockwise, starting at $x$, and then traveling clockwise around the circle a distance of $y$ to get $x * y$ as illustrated in the following diagram:

Screen%20Shot%202015-09-05%20at%2011.03.05%20AM.png

We will now show that $(\mathbb{Z}_n, *)$ is a group. For $x, y \in \mathbb{Z}_n$ we have the $x * y$ is the remainder of the sum $x + y$ on division by $n$. The only possible remainders are $0, 1, ..., n - 1$ and so $)x * y) \in \mathbb{Z}_n$, so $\mathbb{Z}_n$ is closed under $*$.

It's not hard to intuitively see that the remainder of $x + (y + z)$ upon division by $n$ is equal to the remainder of $(x + y) + z$ for all $x, y, z \in \mathbb{Z}_n$, so indeed, $x * (y * z) = (x * y) * z$, so $*$ is associative.

For each $x \in \mathbb{Z}_n$ we note that the remainder of $x + 0$ is equal to the remainder of $x$ upon division by $n$ and the remainder of $0 + x$ is equal to the remainder of $x$ upon division by $n$. In other words, $x * 0 = x$ and $0 * x = x$. Furthermore, $0 \in \mathbb{Z}_n$, so $0$ is the identity element for $*$.

Lastly, for each $x \in \mathbb{Z}_n$ we have that $n - x$ is such that $x + (n - x) = n$ and the remainder of $n$ upon division by $n$ is $0$. Therefore, for $x \neq 0$ we have that $n - x$ is the inverse of $x$ under $*$. Furthermore, if $x = 0$ then the inverse of $x$ under $*$ is $0$ itself.

Hence, $(\mathbb{Z}_n, *)$ is a group.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License