Skip to main content

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.

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.

Solution.

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

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

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

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

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

Fill in the operation table for the binary operation \(\otimes\) on the set \(\mathbb{Z}_{3}^\otimes\) defined by \(a \otimes b = (a \cdot b)\bmod 3\) :

\(\otimes\) 1 2
1
2

Complete the following:

(a) In \(\mathbb{Z}_{3}^\otimes\) with respect to \(\otimes\)

  • select

  • the identity element is 1

  • there is no identity element

.

(b) In \(\mathbb{Z}_{3}^\otimes\)

  • select

  • each element has an inverse

  • at least one element does not have an inverse

  • there is no identity, so inverses are not defined

with respect to \(\otimes\text{.}\)

(c) The operation \(\otimes\) is

  • select

  • associative

  • not associative

.

(d) The operation \(\otimes\) is

  • select

  • commutative

  • not commutative

.

Conclude whether \(\left(\mathbb{Z}_{3}^\otimes,\otimes\right)\) is a commutative group:

The set \(\mathbb{Z}_{3}^\otimes\) with the operation \(\otimes\) is

  • select

  • a commutative group

  • not a commutative group

.

Answer 1.

\(1\)

Answer 2.

\(2\)

Answer 3.

\(2\)

Answer 4.

\(1\)

Answer 5.

\(\text{the identity element is 1}\)

Answer 6.

\(\text{each element has an inverse}\)

Answer 7.

\(\text{associative}\)

Answer 8.

\(\text{commutative}\)

Answer 9.

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

Figure 14.4.3. Examples of Groups (Part 2: Additive Groups) by Matt Farmer and Stephen Steward.

The main result of this section is:

We show that \((\Z_n,\oplus)\) satisfies properties Item 1 to Item 4 from Definition 14.1.2.

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

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

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

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

Find the inverse of \(5\) in the group \((\Z_{12},\oplus)\) where \(a\oplus b=(a+b)\fmod 12\text{.}\)

Solution.

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.

In the group \((\mathbb{Z}_{929}^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b) \bmod 929\) find the inverse of \(550\) with respect to \(\otimes\text{.}\)

We have \(\gcd(550,929)=1\) and \(-201\cdot 550 + 119\cdot 929 = \gcd(550,929)\text{.}\)

The inverse of \(550\) in \(\mathbb{Z}^\otimes_{929}\) with respect to \(\otimes\) is .

Answer.

\(728\)

We end this section with Checkpoint 14.4.7 in which you fill in the blanks in a proof of Theorem 14.4.4.

Let p be a prime number. Let S={1,2,3,...,p-1}. Let \(\otimes\text{:}\)S\(\times\)S\(\to\)S be given by a\(\otimes\)b=(a\(\cdot\)b) mod p.

We show that (S,\(\otimes\)) is a group.

(a) Because a\(\otimes\)1=

  • a

  • p

  • s

  • t

  • 0

  • 1

and 1\(\otimes\)a=
  • a

  • p

  • s

  • t

  • 0

  • 1

for all a in S, the element
  • a

  • p

  • s

  • t

  • 0

  • 1

is the
  • analogue

  • identity

  • inverse

  • opposite

  • unit

with respect to the operation \(\otimes\text{.}\)

(b) Let a in {1,2,3,...,p-1}. As p is prime we have gcd(a,p)=

  • a

  • p

  • s

  • t

  • 0

  • 1

.

By Bezout's theorem there are integers s and t such that s\(\cdot\)a+t\(\cdot\)p=

  • a

  • p

  • s

  • t

  • 0

  • 1

.

Thus

  • a

  • p

  • s

  • t

  • 0

  • 1

\(\otimes\)a=(
  • a

  • p

  • s

  • t

  • 0

  • 1

a) mod p =1.

So

  • a

  • p

  • s

  • t

  • 0

  • 1

mod p is the
  • analogue

  • identity

  • inverse

  • opposite

  • unit

of a with respect to \(\otimes\text{.}\)

(c) The multiplication of integers is

  • associative

  • commutative

  • disruptive

  • distributive

  • negative

  • orderly

  • positive

  • transitive

, that is,

(a\(\cdot\)b)\(\cdot\) c= a\(\cdot\)(b\(\cdot\) c)

for all integers a, b, and c. Thus for for all a, b, and c in S we have

(a\(\otimes\)b)\(\otimes\) c =((a\(\cdot\)b)\(\cdot\) c) mod p =(a\(\cdot\)(b\(\cdot\) c)) mod p =a\(\otimes\)(b\(\otimes\) c).

Hence the operation \(\otimes\) is

  • associative

  • commutative

  • disruptive

  • distributive

  • negative

  • orderly

  • positive

  • transitive

.

(d) The multiplication of integers is

  • associative

  • commutative

  • disruptive

  • distributive

  • negative

  • orderly

  • positive

  • transitive

, that is,

a\(\cdot\)b=b\(\cdot\)a

for all integers a and b. Thus for all a and b in S we have

a\(\otimes\)b =(a\(\cdot\)b) mod p =(b\(\cdot\)a) mod p =b\(\otimes\)a.

Hence the operation \(\otimes\) is

  • associative

  • commutative

  • disruptive

  • distributive

  • negative

  • orderly

  • positive

  • transitive

.

We have shown that

(a) the set S contains an

  • analogue

  • identity

  • inverse

  • opposite

  • unit

with respect to the operation \(\otimes\text{,}\)

(b) for each element in S the set S contains an

  • analogue

  • identity

  • inverse

  • opposite

  • unit

with respect to \(\otimes\text{,}\)

(c) the operation \(\otimes\) is associative,

(d) the operation \(\otimes\) is

  • associative

  • commutative

  • disruptive

  • distributive

  • negative

  • orderly

  • positive

  • transitive

.

Thus the set S with the operation \(\otimes\) is a commutative group.

Answer 1.

\(\text{a}\)

Answer 2.

\(\text{a}\)

Answer 3.

\(\text{1}\)

Answer 4.

\(\text{identity}\)

Answer 5.

\(\text{1}\)

Answer 6.

\(\text{1}\)

Answer 7.

\(\text{s}\)

Answer 8.

\(\text{s}\)

Answer 9.

\(\text{s}\)

Answer 10.

\(\text{inverse}\)

Answer 11.

\(\text{associative}\)

Answer 12.

\(\text{associative}\)

Answer 13.

\(\text{commutative}\)

Answer 14.

\(\text{commutative}\)

Answer 15.

\(\text{identity}\)

Answer 16.

\(\text{inverse}\)

Answer 17.

\(\text{commutative}\)