## 4.2 Examples of groups

To get a good understanding of group theory it’s important to have a library of examples.

Example 4.2

• $$(\mathbb{Z}, +)$$ is a group. The identity is 0, the inverse of $$a\in\ZZ$$ is $$-a$$, and addition is associative. Equally the real numbers, or the complex numbers, with the binary operation + form groups. But the natural numbers $$\mathbb{N}$$ with the operation + are not a group (why?)
• $$(\ZZ, -)$$ is not a group. Work out $$1-(2-3)$$ and $$(1-2)-3$$. They’re different, so the binary operation $$-$$ isn’t associative on $$\ZZ$$.
• ‘’The’’ trivial group. Let $$G = \{ e \}$$, a one element set, and let $$*$$ be the binary operation on G defined by $$e*e=e$$ (in fact, there’s only one binary operation on a one element set). Then $$(G, *)$$ is a group called the trivial group.
• $$(\CC, \times)$$ is not a group. What would the inverse element of 0 be? But if we write $$\CC^{\times}$$ for the set of nonzero complex numbers then $$\CC^{\times}, \times$$ is a group. Equally the nonzero real numbers or rational numbers under multiplication are groups.
• Let $$G = GL(n,\CC)$$ be the set of $$n \times n$$ invertible matrices over the complex numbers. Let $$*$$ be matrix multiplication. Then $$(G,*)$$ is a group.
• Let $$V = \{ 1, -1, i ,-i\} \subset \CC$$ and let $$*$$ be multiplication of complex numbers on V. Then $$(V,*)$$ is a group.
• Recall that $$S_n$$ is the set of all bijections from $$\{1,2,\ldots,n\}$$ to itself, and that the composition of two bijections is again a bijection. This means that $$\circ$$ is a binary operation on $$S_n$$, and in fact $$(S_n,\circ)$$ is a group. The identity element is the identity permutation $$\id$$, the inverse of a bijection is a bijection so the second group axiom holds, and function composition is always associative so the final axiom holds too. This is why we called $$S_n$$ the symmetric group on n letters.

### 4.2.1 Modular arithmetic

An example which is particularly important for applications in computer science and cryptography is the group of integers modulo n under addition, which we’ll define in this subsection.

Definition 4.4 Let $$n,a,b \in \ZZ$$. We say a is congruent to b modulo (or just mod) n if a-b is divisible by n. In this case we write $a \equiv b \mod n.$ We write $$[a]_n$$, or just $$[a]$$, for the set of all integers congruent to a modulo n, and we call this the congruence class of a modulo n.

If two integers a and b are congruent modulo n, then $$[a]_n = [b]_n$$ - this will be an exercise.

For example, $$[0]_2 = \{\ldots, -2, 0, 2, 4, 6, \ldots\}= [-2]_2=[42]_2$$ and $$[1]_2 = \{\ldots, -3, -1, 1, 3, 5, \ldots\}=[-1]_2=[33]_2$$.

Definition 4.5 Let $$n>0$$. Then $$\ZZ_n$$ is the set of congruence classes modulo n.

If $$n >0$$, any integer is congruent mod n to exactly one of the numbers $$0,1,\ldots,n-1$$.
Because of this, the set $$\ZZ_n$$ has size n and $\zz_n = \{ [0]_n,[1]_n,\ldots, [n-1]_n\}.$

Lemma 4.1 Define a binary operation + on $$\ZZ_n$$ by $$[a]_n+[b]_n=[a+b]_n$$. Then $$(\ZZ_n,+)$$ is a group.

Proof. First we need to check that this really does define a binary operation on $$\zz_n$$. The potential problem is that an eqivalence class $$[a]_n$$ can have lots of different representatives, e.g. $$[5]_3 = [2]_3$$, but our definition of + seems to depend on a specific choice of representative. Couldn’t it be that $$[a]_n = [a']$$ and $$[b]_n = [b']_n$$ but $$[a+b]_n \neq [a'+b']_n$$? If so our definition of + wouldn’t work - it would not be “well-defined.”

We need to check that if $$[a]_n=[a']_n$$ and $$[b]_n=[b']_n$$ then $$[a+b]_n=[a'+b']_n$$. Because $$[a]_n=[a']_n$$, a and a’ are congruent mod n so $$a=a'+kn$$ for some integer k, and similarly $$b=b'+ln$$ for some integer l. Therefore \begin{align*} a+b &= a'+kn + b' + ln \\ &= a'+b' + (k+l)n \end{align*} so $$a+b \equiv a'+b' \mod n$$ and $$[a+b]_n = [a'+b']_n$$.

The group axioms are easy to check. $$[0]_n$$ is clearly an identity element, $$[-a]_n$$ is inverse to $$[a]_n$$, and because + is associative on $$\zz$$ we have $$[a]_n+ ([b]_n+[c]_n)= [a]_n + [b+c]_n = [a+b+c]_n$$ and $$([a]_n+[b]_n)+[c]_n = [a+b]_n+[c]_n=[a+b+c]_n$$ so $\begin{equation*} [a]_n+ ([b]_n+[c]_n) = ([a]_n+[b]_n)+[c]_n \end{equation*}$ and + is associative on $$\zz_n$$.

From now on we’ll just write + for the group operation + on $$\ZZ_n$$.

Definition 4.6 Let $$n>0$$. The binary operation $$\times$$ on $$\ZZ_n$$ is defined by $$[a]_n \times [b]_n = [ab]_n$$

We’ll sometimes write $$[a]_n[b]_n$$ instead of $$[a]_n\times [b]_n$$.

Again, we should check that this really defines a binary operation on $$\zz_n$$: if $$[a]_n=[a']_n$$ and $$[b]_n=[b']_n$$ then we need $$[ab]_n = [a'b']_n$$. This is true because $$a=a'+kn$$ and $$b=b'+ln$$ for some $$k,l \in \zz$$ so \begin{align*} ab &= (a'+kn)(b'+ln) \\ &= a'b' + n(kb'+la'+kln) \end{align*} so $$ab \equiv a'b' \mod n$$ and therefore $$[ab]_n=[a'b']_n$$.

This does not make $$(\ZZ_n, \times)$$ into a group because 0 has no inverse for the operation $$\times$$.

On the other hand, $$\times$$ is always an associative binary operation on $$\zz_n$$ since $$\times$$ is associative on $$\zz$$.

We write $$x\mid y$$ to mean that y is an integer multiple of x, or equivalently that x divides y, and $$x \nmid y$$ to mean that x does not divide y. A prime number is a positive integer $$p>1$$ such that for all $$a,b \in \zz$$, if $$p\mid ab$$ then $$p\mid a$$ or $$p\mid |b$$. (This is equivalent to the traditional definition that a prime number is one with no positive divisors except for itself and 1, but is more useful for us).

Theorem 4.1 Let p be a prime number and let $$\ZZ_p^\times = \{[1]_p,[2]_p,\ldots,[p-1]_p\}$$. Then $$(\ZZ_p^\times, \times)$$ is a group.

Proof. First note that $$\times$$ really is a binary operation on $$\ZZ_p^\times$$. If $$[a]_p,[b]_p \in \ZZ_p^\times$$ then $$[ab]_p \neq [0]_p$$ (if it did we would have $$p|ab$$, so $$p|a$$ or $$p|b$$, so $$[a]_p=[0]_p$$ or $$[b]_p=[0]_p$$), and hence $$[ab]_p \in \zz_p^\times$$.

$$\times$$ is clearly associative, and $$[1]_p$$ is an identity element, so we only need to check the existence of inverses. Fix $$[a]_p \in \zz_p^\times$$. The greatest common divisor of a and p is 1, so using Euclid’s algorithm we can find numbers r and s such that ra + sp = 1. Then $$[r]_p[a]_p = [ra]_p = [1-sp]_p = [1]_p$$ as $$1-sp \equiv 1 \mod p$$, so $$[r]_p$$ is an inverse to $$[a]_p$$.

These groups $$\ZZ_p^\times$$ are an important part of the famous RSA cryptosystem.

### 4.2.2 Group tables

For small groups $$(G,*)$$ we can completely describe the group operation by drawing a table called a group table or Cayley table. This has rows and columns labelled by the elements of G, and the entry in row g and column h is $$g * h$$. For example, if $$V,*$$ is the group of Example 4.2, the group table is:

$$\times$$ 1 $$-1$$ $$i$$ $$-i$$
1 1 $$-1$$ $$i$$ $$-i$$
-1 -1 1 $$-i$$ $$i$$
$$i$$ $$i$$ $$-i$$ -1 1
$$-i$$ $$-i$$ $$i$$ 1 $$-1$$