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