Exercises on Groups

Let $n \in \mathbb{N}, n > 0$. For $x, y \in \mathbb{Z}$ we write

x \equiv y \pmod{n} \iff n \text{ divides } x - y.

(a)

Show that $\equiv \pmod{n}$ is an equivalence relation.

(b)

Now we consider the so-called residue classes of a number $k \in \mathbb{Z}$, defined by

[k]_n = k + n\mathbb{Z} = \{k + nz \mid z \in \mathbb{Z}\}.

In such a residue class, all numbers have the same remainder as $k$ when divided by $n$. The set of all residue classes is denoted by $\mathbb{Z}/n\mathbb{Z}$.\\

Show that $\mathbb{Z}/n\mathbb{Z} = \{[0], [1], \ldots, [n - 1]\}$.

(c)

We define addition and multiplication of residue classes mod $n$ by

[a]_n + [b]_n := [a + b]_n,

[a]_n \cdot [b]_n := [a \cdot b]_n.

Show that these operations are well-defined, associative, and commutative, and that $(\mathbb{Z}/n\mathbb{Z}, +)$ is an abelian group. Show that $(\mathbb{Z}/n\mathbb{Z}, \cdot)$ is generally not a group.

Beweis

(a)

i)	$x \equiv x \pmod{n}$ is clear.
ii)	Let $x, y \in \mathbb{Z}$ with $x \equiv y \pmod{n}$, then $y \equiv x \pmod{n}$ also holds.
iii)	Let $x, y, z \in \mathbb{Z}$ with $x \equiv y \pmod{n}$ and $y \equiv z \pmod{n}$. This means $n \mid x - y$ and $n \mid y - z$. Then it also holds that $n \mid ((x - y) + (y - z)) = x - z$, so $x \equiv z \pmod{n}$.

(b)

The classes $[0]_n, \ldots, [n - 1]_n$ are different, because $i \equiv j$ for $i \neq j$ and $i, j \in \{0, \ldots, n - 1\}$ is not the case. If $m \in \mathbb{Z}$, we can divide $m$ by $n$ with a remainder, i.e., there are $k, r \in \mathbb{Z}$ with $0 \leq r < n - 1$ such that $m = kn + r$. Modulo $n$ it holds that $[m]_n = [kn + r]_n = [r]_n$, i.e., $[m]_n$ is one of the classes $[0]_n, \ldots, [n - 1]_n$.

(c)

We need to show that from $a \equiv a'$ mod $n$ and $b \equiv b'` mod $n$ it follows that $a + b \equiv a' + b'$ mod $n$ and $ab \equiv a'b'$ mod $n$. The assumption means that there are $k, l \in \mathbb{Z}$ with $a = a' + kn$ and $b = b' + ln$. It follows that

a + b = a' + kn + b' + ln = a' + b' + (k + l)n \equiv a' + b' \pmod{n}

and

ab = (a' + kn)(b' + ln) = a'b' + a'ln + b'kn + kln^2 \equiv a'b' \pmod{n}.

This shows that addition and multiplication are well-defined. Associativity and commutativity follow from the corresponding properties of $+$ and $\cdot$, e.g.,

([a]_n + [b]_n) + [c]_n = [a + b]_n + [c]_n = [(a + b) + c]_n = [a + (b + c)]_n = [a]_n + ([b]_n + [c]_n).

The neutral element of $(\mathbb{Z}/n\mathbb{Z}, +)$ is $[0]_n$, because

[a]_n + [0]_n = [a + 0]_n = [a]_n.

For every $[a]_n \in \mathbb{Z}/n\mathbb{Z}$ it holds that

[a]_n + [-a]_n = [a - a]_n = [0]_n.

Thus, $(\mathbb{Z}/n\mathbb{Z}, +)$ is an abelian group.\\

$(\mathbb{Z}/n\mathbb{Z}, \cdot)$ is generally not a group, because for example, for $a = 0$, the inverse $a^{-1}$ does not exist.