## 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.

Recall the definition of the equivalence relation of congruence mod *n* from the first part of this course:

**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 equivalence class of *a* under this relation.

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 equivalence classes of the relation of congruence modulo

*n*on \(\zz\).

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\).

*+*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|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|ab\) then \(p|a\) or \(p|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).

**Lemma 4.2**(the

**pigeonhole principle.**) Let

*X*be a finite set and \(f:X \to X\) be a function. Then

*f*is injective if and only if it is surjective.

*Proof.*Let \(|X|=n\), and label the elements of

*X*as \(x_1,\ldots, x_n\). If

*f*is injective then all the elements \(f(x_1),\ldots, f(x_n)\) are distinct, so \(|\im f|=n\), so \(\im f = X\) and

*f*is surjective. If

*f*is not injective then \(f(x_1)=f(x_2)\), say, so \(|\im f| < n\) and

*f*is not surjective.

**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\).

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\) |