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

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

\(\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\) and consider the map \(f: \zz_p^\times \to \zz^\times_p\) defined by \(f([b]_p)=[a]_p[b]_p\). This is injective: if \(f([b]_p)=f([c]_p)\) then \([ab]_p=[ac]_p\), so \(p|(ab-ac)\), so \(p|a(b-c)\). Since \(p \nmid a\) we have \(p|(b-c)\) so \([b]_p=[c]_p\). It is therefore surjective by Lemma 4.2, so \(f([b]_p)=[1]_p\) for some \([b]_p \in \zz^\times_p\), which means that \([a]_p[b]_p=[1]_p\) and therefore \([b]_p\) is an inverse for \([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\)