Section 14.4 The additive groups \((\Z_n,\oplus)\)
Before we prove that \((\Z_n,\oplus)\) where \(a \oplus b=(a+b)\fmod n\) is a group for all \(n\in\N\text{,}\) we examine an example.
Problem 14.4.1. Is \((\Z_7,\oplus)\) a group ?
Show that \((\Z_7,\oplus)\) where \(\Z_7=\{0,1,2,3,4,5,6\}\) and \(a\oplus b=(a+b)\fmod 7\) is a group.
We show that \(\Z_7\) with \(\oplus\) satisfies the properties of a group from Definition 14.1.2. As the remainder of division by \(7\) is always in \(\Z_7\) we have that \(\oplus\) is indeed a binary operation on \(\Z_7\text{.}\)
Identity: Because \(a\oplus 0=(a+0)\fmod 7=a\) and \(0\oplus a = (a + 0) \fmod 7 = a\) for all \(a\in\Z_7\text{,}\) \(0\) is the identity element of \(\oplus\text{.}\)
-
Inverse: We have \(0 \oplus 0 = (0 + 0) \fmod 7 = 0\text{.}\) So \(0\) is the identity element in \(\Z_7\text{.}\) Let \(a\in\Z_7\) with \(a \neq 0\) and let \(b=7-a\text{.}\) Then,
\begin{align*} a\oplus b\amp= a\oplus (7-a)=(a+7-a)\fmod 7\\ \amp=(a-a+7)\fmod 7=7\fmod 7=0\text{.} \end{align*}Thus \(b\) is the inverse of \(a\) with respect to \(\oplus\text{.}\)
Associativity: Let \(a\in\Z_7\text{,}\) \(b\in\Z_7\text{,}\) and \(c\in\Z_7\text{.}\) By Theorem 3.4.10 we only need to show that \((a+(b+c))\fmod 7=((a+b)+c)\fmod 7\text{.}\) This holds since \(a+(b+c)=(a+b)+c\) for all integers \(a\text{,}\) \(b\text{,}\) and \(c\) by the associative property of the integers. Hence \(\oplus\) is associative.
Commutativity: By the commutative property of the integers we have \(a+b=b+a\) for all integers \(a\) and \(b\text{.}\) Thus also for all \(a\in\Z_7\) and \(b\in\Z_7\text{,}\) we have \(a+b=b+a\) and \(a\oplus b=(a+b)\fmod 7=(b+a)\fmod 7=b\oplus a\text{.}\) We can also deduce the commutativity of \(\oplus\) from the symmetry of the addition table in Table 14.3.3.
In Checkpoint 14.4.2 work through the steps of Problem 14.4.1 to show that the set with the given binary operations is a group.
Checkpoint 14.4.2. Is this a group ?
Fill in the operation table for the binary operation \(\oplus\) on the set \(\mathbb{Z}_{3}\) defined by \(a \oplus b = (a + b)\bmod 3\) :
| \(\oplus\) | 0 | 1 | 2 |
| 0 | |||
| 1 | |||
| 2 |
Complete the following:
(a) In \(\mathbb{Z}_{3}\) with respect to \(\oplus\)
select
the identity element is 0
the identity element is 1
there is no identity element
(b) In \(\mathbb{Z}_{3}\)
select
each element has an inverse
at least one element does not have an inverse
there is no identity, so inverses are not defined
(c) The operation \(\oplus\) is
select
associative
not associative
(d) The operation \(\oplus\) is
select
commutative
not commutative
Conclude whether \(\left(\mathbb{Z}_{3},\oplus\right)\) is a commutative group:
The set \(\mathbb{Z}_{3}\) with the operation \(\oplus\) is
select
a commutative group
not a commutative group
\(0\)
\(1\)
\(2\)
\(1\)
\(2\)
\(0\)
\(2\)
\(0\)
\(1\)
\(\text{the identity element is 0}\)
\(\text{each element has an inverse}\)
\(\text{associative}\)
\(\text{commutative}\)
\(\text{a commutative group}\)
In general we have that for any natural number \(n\) in \((\Z_n,\oplus)\) where \(a\oplus b=(a+b)\fmod m\) is a group. We give an overview over this result in the video in Figure 14.4.3 and then go through the result and its proof in detail below.
The main result of this section is:
Theorem 14.4.4.
Let \(n\in\N\text{.}\) The set \(\Z_n=\{0,1,2,\dots,n-1\}\) with the operation \(\oplus:\Z_n\times\Z_n\to\Z_n\text{,}\) \(a\oplus b=(a+b)\fmod n\) is a group.
Proof.
We show that \((\Z_n,\oplus)\) satisfies properties Item 1 to Item 4 from Definition 14.1.2.
Identity: Let \(a\in\Z_n\text{.}\) We have \(a\oplus 0=(a+0)\fmod n=a\fmod n=a\) and similarly \(0\oplus a=(0+a)\fmod n=a\fmod n=a\text{.}\) Hence \(0\) is an identity element with respect to \(\oplus\text{.}\)
-
Inverses: We have \(0\oplus 0=(0+0)\fmod n=0\text{.}\) Thus 0 is the inverse of 0 in \(\Z_n\) with respect to \(\oplus\text{.}\) Now consider \(a\in\Z_n\) and \(a \neq 0\text{.}\) Let \(b=n-a\text{.}\) So \(b \in \Z_n\text{.}\) Then
\begin{equation*} a\oplus b=a\oplus(n-a)=(a+(n-a)) \fmod n =(a-a+n)\fmod n = 0\fmod n\text{.} \end{equation*}Thus \(n-a=b\) is the inverse of \(a\text{.}\)
Associativity: The associativity of \(\oplus\) follows from the associativity of \(+\text{.}\) Let \(a\in\Z_n\text{,}\) \(b\in\Z_n\text{,}\) and \(c\in\Z_n\text{.}\) By Theorem 3.4.10 we only need to show that \((a+(b+c))\fmod n=((a+b)+c)\fmod n\text{.}\) This holds since \(a+(b+c)=(a+b)+c\) for all integers \(a\text{,}\) \(b\text{,}\) and \(c\) by the associative property of the integers. Hence \(\oplus\) is associative.
Commutativity: By the commutative property of the integers we have \(a+b=b+a\) for all integers \(a\) and \(b\text{.}\) Thus also for all \(a\in\Z_n\) and \(b\in\Z_n\) we have \(a+b=b+a\) and \(a\oplus b=(a+b)\fmod n=(b+a)\fmod n=b\oplus a\text{.}\)
Directly from the proof of Theorem 14.4.4 Item 2 we obtain a method for finding inverses in \((\Z_n,\oplus)\text{.}\) Namely if \(a\in\Z_n\) and \(a \neq 0\) then \(b=n-a\in\Z_n\) and \(a\oplus b=0\text{.}\)
Problem 14.4.5. The inverse of \(5\) in \((\Z_{12},\oplus)\).
Find the inverse of \(5\) in the group \((\Z_{12},\oplus)\) where \(a\oplus b=(a+b)\fmod 12\text{.}\)
We have \(5\oplus 7=(5+7)\fmod 12=12\fmod 12=0\text{.}\) As the group \((\Z_{12},\oplus)\) is commutative this shows that 7 is the inverse of \(5\text{.}\)
Find the identity of such a group and the inverses of its elements yourself.
Checkpoint 14.4.6. Determine identity and inverses.
Let \(\mathbb{Z}_{61}={ 0,1,2,\dots, 61}\text{.}\) Consider the binary operation \(\oplus:\mathbb{Z}_{61}\times \mathbb{Z}_{61}\to \mathbb{Z}_{61}\) given by \(a \oplus b = \left(a + b\right) \bmod 61\text{.}\)
The identity with respect to \(\oplus\) in \(\mathbb{Z}_{61}\) is .
The inverse of \(18\) with respect to \(\oplus\) in \(\mathbb{Z}_{61}\) is .
An element \(e\in \mathbb{Z}_m\) is the identity with respect to \(\oplus\) if \(a \oplus e= a\) and \(e \oplus a=a\) for all \(a\in \mathbb{Z}_m\text{..}\)
An element \(b\in \mathbb{Z}_m\) is the inverse of \(a\in \mathbb{Z}_m\) with respect to \(\oplus\) if \(a \oplus b=0\) and \(b \oplus a=e\text{.}\)
Make sure that your answer is an element of \(\mathbb{Z}_m\text{.}\)
\(0\)
\(43\)
We end this section with Checkpoint 14.4.7 in which you fill in the blanks in a proof of Theorem 14.4.4.
Checkpoint 14.4.7. \((Z_m,\oplus)\) is a group.
Let m be a natural number. Let S={0,1,2,3,...,m-1}. Let \(\oplus\text{:}\)S\(\times\)S\(\to\)S be given by a\(\oplus\)b=(a+b) mod m.
We show that (S,\(\oplus\)) is a group.
(a) Because a\(\oplus\)0=
a
a-1
0
1
2
m-a
a-m
a
a-1
0
1
2
m-a
a-m
a
a-1
0
1
2
m-a
a-m
analogue
identity
inverse
opposite
(b) For all a in S we have a\(\oplus\)
a
a-1
0
1
2
m-a
a-m
a
a-1
0
1
2
m-a
a-m
Thus each a in S has an
analogue
identity
inverse
opposite
(c) The addition of integers is associative. That means
(a+b)+c = a+(b+c)
a+b = b+a
a+0 = a and 0+a = a
a+b = 0 and b+a = 0
Thus for for all a, b, and c in S we have
(a\(\oplus\)b)\(\oplus\) c =
((a+b)+c) mod m
(a+(b+c)) mod m
(a+b) mod m
(b+a) mod m
(a(b+c)) mod m
(ab+ac) mod m
((a+b)+c) mod m
(a+(b+c)) mod m
(a+b) mod m
(b+a) mod m
(a(b+c)) mod m
(ab+ac) mod m
Hence the operation \(\oplus\) is
associative
commutative
disruptive
distributive
orderly
(d) The addition of integers is commutative. That means
(a+b)+c = a+(b+c)
a+b = b+a
a+0 = a and 0+a = a
a+b = 0 and b+a = 0
Thus for all a and b in S we have
a\(\oplus\)b =
((a+b)+c) mod m
(a+(b+c)) mod m
(a+b) mod m
(b+a) mod m
(a(b+c)) mod m
(ab+ac) mod m
((a+b)+c) mod m
(a+(b+c)) mod m
(a+b) mod m
(b+a) mod m
(a(b+c)) mod m
(ab+ac) mod m
Hence the operation \(\oplus\) is
associative
commutative
disruptive
distributive
orderly
We have shown that
(a) the set S contains an identity with respect to the operation \(\oplus\text{,}\)
(b) for each element in S the set S contains an inverse with respect to \(\oplus\text{,}\)
(c) the operation \(\oplus\) is associative,
(d) the operation \(\oplus\) is commutative.
Thus the set S with the operation \(\oplus\) is a commutative group.
\(\text{a}\)
\(\text{a}\)
\(\text{0}\)
\(\text{identity}\)
\(\text{m-a}\)
\(\text{m-a}\)
\(\text{inverse}\)
\(\text{(a+b)+c = a+(b+c)}\)
\(\text{((a+b)+c) mod m}\)
\(\text{(a+(b+c)) mod m}\)
\(\text{associative}\)
\(\text{a+b = b+a}\)
\(\text{(a+b) mod m}\)
\(\text{(b+a) mod m}\)
\(\text{commutative}\)