Section14.5The multiplicative groups \((\Z_p^\otimes,\otimes)\)
In Section 14.4 we had seen that for all natural numbers \(m\) the set \(\Z_m=\{0,1,2,\dots,m-1\}\) with addition modulo \(m\) is a group. In this section, we investigate which sets form a group with the operation \(\otimes\text{.}\)
In the video in Figure 14.26 we present the main results of this section. Then we consider several examples and eventually proof the main result that states \((\Z_p^\otimes,p)\) is a group only when \(p\) is a prime number.
Figure14.26.Examples of Groups (Part 2: Multiplicative Groups) by Matt Farmer and Stephen Steward.
We first investigate what happens when we consider the binary operation given by \(a \oplus b\fmod m\) is a composite number.
Example14.27.Is \((\Z_6,\otimes)\) a group ?
We consider the set \(\Z_6\) with the binary operation \(\otimes:\Z_6\times\Z_6\to\Z_6\) given by \(a\otimes b=(a\cdot b)\fmod 6\text{.}\) Note that \(\otimes\) is not a binary operation on \(\Z_6^\otimes\) as \(2\otimes 4=0\not\in\Z_6^\otimes\text{.}\) The operation table for \(\otimes\) is:
\(\otimes\)
0
1
2
3
4
5
0
0
0
0
0
0
0
1
0
1
2
3
4
5
2
0
2
4
0
2
4
3
0
3
0
3
0
3
4
0
4
3
0
4
2
5
0
5
4
3
2
1
From the table we see that 1 is the identity element with respect to \(\otimes\text{.}\) The only elements that have a 1 in their row (or column) are 1 and 5. So 0, 2, 3, and 4 do not have inverses with respect to \(\otimes\text{.}\) Hence \(\Z_6\) with the operation \(\otimes\) is not a group.
In Example 14.27 we found that \(0\) and the divisors of the modulus \(6\) do not have inverses. We now investigate what happens when we reduce the number of divisors of the modulus by using a prime number.
Example14.28.Is \((\Z_7,\otimes)\) a group ?
We consider \(\Z_7\) with the binary operation \(\otimes:\Z_7\times \Z_7\to\Z_7\) given by \(a\otimes b=(a\cdot b)\fmod 7\text{.}\)
From the multiplication table in Table 14.15 we see that \(1\) is the only possibility of an identity element with respect to \(\otimes\text{.}\) We also see that \(0\) does not have an inverse with respect to \(\otimes\text{.}\) Thus \(\Z_7\) with \(\otimes\) does not satisfy Definition 14.2Item 2. Which implies that \((\Z_7,\otimes)\) is not a group.
In Example 14.28 we have seen above that \(\Z_7\) with the binary operation \(\otimes: \Z_7 \times \Z_7 \to \Z_7\) is not a group because \(0\) which is an element of \(\Z_7\) does not have an inverse with respect to \(\otimes\text{.}\)
We remedy this situation by excluding \(0\) from the set and show that \((\Z_7^\otimes,\otimes)\) is a group.
Problem14.29.Is \((\Z_7^\otimes,\otimes)\) a group ?
Show that the set \(\Z_7^\otimes=\{1,2,3,4,5,6\}\) with the operation \(a\otimes b=(a\cdot b)\fmod 7\) is a group.
Solution.
We show that \(\Z_7^\otimes\) with \(\otimes\) satisfies the properties of a groups from Definition 14.2. Because \(7\) is a prime number, the product of two numbers that are not divisible by \(7\) is also not divisible by \(7\text{.}\) Again because \(7\) is prime, none of the elements in \(\Z_7^\otimes\) are divisible by seven. Thus the product of two elements of \(\Z_7^\otimes\) is not divisible by \(7\text{,}\) and its remainder is not \(0\text{.}\) Thus \(\otimes\) is a binary operation on \(\Z_7^\otimes\text{.}\)
Identity: Since \(a\cdot 1=a\) and \(1\cdot a=a\) for all integers \(a\) we have \(a\otimes 1=(a\cdot 1)\fmod 7=a\) and \(1\otimes a=(1\cdot a)\fmod 7=a\fmod 7=a\) for all \(a\in\Z_7^\otimes\text{.}\) Hence \(1\) is the identity with respect to \(\otimes\text{.}\)
Inverses: From the multiplication table in Table 14.15 we get \(2\otimes 4=1\text{,}\)\(3\otimes 5=1\text{,}\)\(4\otimes 2=1\text{,}\)\(5\otimes 3=1\text{,}\) and \(6\otimes 6=1\text{.}\) Thus each element in \(\Z_7^\otimes\) has an inverse.
Associativity: Let \(a\in\Z_7^\otimes\text{,}\)\(b\in\Z_7^\otimes\text{,}\) and \(c\in\Z_7^\otimes\text{.}\) By Theorem 3.50 we only need to show that \((a\cdot(b\cdot c))\fmod 7=((a\cdot b)\cdot c)\fmod 7\text{.}\) This holds since \(a\cdot (b\cdot c)=(a\cdot b)\cdot c\) for all integers \(a\text{,}\)\(b\text{,}\) and \(c\) by the associative property of the integers. Hence \(\otimes\) is associative.
Commutativity: By the commutative property of multiplication of integers we have \(a\cdot b=b\cdot a\) for all integers \(a\) and \(b\text{.}\) Thus also for all \(a\in\Z_7^\otimes\) and \(b\in\Z_7^\otimes\) we have \(a\cdot b=b\cdot a\) and \(a\otimes b=(a\cdot b)\fmod 7=(b\cdot a)\fmod 7=b\otimes a\text{.}\) We can also deduce the commutativity of \(\otimes\) from the symmetry of the multiplication table in Table 14.15.
In Checkpoint 14.30 work through the steps of Problem 14.29 that the set with the give binary operations is a group.
Checkpoint14.30.Is this 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
.
If \(p \in \N\) is prime, we still need to check that every element in \(\Z_p^\otimes\) has an inverse. In the following problem, we compute the inverse of an element in \(\Z_7^\otimes\) with respect to modular multiplication.
Problem14.31.The multiplicative inverse of \(5\) modulo \(7\).
Find \(b\in\Z_7^\otimes\) such that \(5\cdot b\fmod 7=1\text{.}\)
Solution.
As there are only 6 elements in \(\Z_7^\otimes\text{,}\) we decide to try them all until we find the solution. We have \((5\cdot 1)\fmod 7=5\ne 1\text{,}\)\((5\cdot 2)\fmod 7=10\fmod 7=3\ne 1\text{,}\)\((5\cdot 3)\fmod 7=15\fmod 7=1\) so we have found the solution \(b=3\) and do not need to continue our search.
In the group \((\Z_5^\otimes,\otimes)\) where \(a\otimes b:=(a\cdot b)\fmod 5\) find the inverses of all elements of \(\Z_5^\otimes\text{.}\)
Solution.
The numbers in this problem are small enough for trial and error works well enough. Recall that \(\Z_5^\otimes = {1,2,3,4}\text{.}\)
The inverse of 1.
To find the inverse of \(1\) we try the values in {1,2,3,4} until we succeed.
\(1 \otimes 1=1\text{,}\) so the inverse of 1 is 1.
To find the inverse of \(2\) we try the values in {1,2,3,4} until we succeed.
\(1 \otimes 2=2\text{,}\) so 1 is not the inverse of 2.
\(2 \otimes 2=4\text{,}\) so 2 is not the inverse of 2.
\(3 \otimes 2=1\text{,}\) so 3 could be the inverse of 2. As \(2 \otimes 3=1\text{,}\) the inverse of 2 is 3. Since we have found the inverse we do not have to keep trying.
As \(3\) is the inverse of \(2\text{,}\) we have that \(2\) is the inverse of \(3\text{.}\)
To find the inverse of \(4\) we try the values in {1,2,3,4} until we succeed.
\(1 \otimes 4=4\text{,}\) so 1 is not the inverse of 4.
\(2 \otimes 4=3\text{,}\) so \(2\) is not the inverse of \(4\text{.}\)
\(3 \otimes 4=2\text{,}\) so \(3\) is not the inverse of \(4\text{,}\)
\(4 \otimes 4=1\text{,}\) so \(4\) is the inverse of itself.
We show that \(\Z_p^\otimes=\{1,2,\dots,p-1\}\) with the operation given by \(a\otimes b=(a\cdot b)\fmod p\) is a group. In particular, when \(p\) is a prime number any element in \(\Z_p^\otimes\) has a multiplicative in \(\Z_p^\otimes\) with respect to \(\otimes\text{.}\)
Theorem14.33.
If \(p\in\N\) is a prime number and \(a\in\Z_p^\otimes\text{,}\) then there is \(b\in\Z_p^\otimes\) such that \(a\otimes b = (a\cdot b)\fmod p=1\text{,}\) that is, \(b\) is the multiplicative inverse of \(a\) with respect to multiplication modulo \(p\text{.}\)
Proof.
As \(1\le a \le p-1\) and \(p\) is prime, we have \(\gcd(a,p)=1\text{.}\) By Bézout’s identity (Theorem 4.25) there are \(s\in\Z\) and \(t\in\Z\) such that \((s\cdot a)+(t\cdot p)=1\text{,}\) hence \((s\cdot a) =1- (t\cdot p)\) and \((s\cdot a)\fmod p=1\text{.}\) Thus \(s\fmod p\) is the inverse of \(a\) with respect to \(\otimes\text{.}\)
The Euclidean algorithm (Algorithm 4.17) along with the computation of the quotients is everything that is needed to find the values of \(s\) and \(t\) in Bézout’s identity, so it is possible to develop a method of finding modular multiplicative inverses. In particular if for a prime \(p\) and \(1\le a\le (p-1)\) the \(s\) from Bézout’s identity for \(\gcd(a,p)\) is known, we can easily find the inverse of \(a\) in \((\Z_p^\otimes,\otimes)\text{.}\)
Strategy14.1.Modular Inverses.
Let \(p\) be a prime number and \(1\le a\le p-1\text{.}\) Let \(s\) and \(t\) be such that
Then the inverse \(a^{-1\otimes}\) of \(a\) in the group \((\Z_p^\otimes,\otimes)\) is \(s\fmod p\text{.}\) That is, \(a^{-1\otimes}= s\fmod p\text{.}\)
Example14.34.The multiplicative inverse of \(7\) modulo \(19\).
We have that \(\gcd(19,7)=1\text{.}\) By Bézout’s Identity (Theorem 4.25) there are \(s\in\Z\) and \(t\in\Z\) such that \((s\cdot 19)+(t\cdot 7)=\gcd(19,7)\text{.}\) Possible solutions for \(s\) and \(t\) are \(s=3\) and \(t=-8\text{.}\) We get
So \((3\cdot 19)+((-8)\cdot 7)=1\text{.}\) Using modular arithmetic, \(((-3\cdot 19) + ((-8)\cdot 7))\fmod 19=1 \fmod 19\text{.}\) Recalling that the order in which we perform the \(\fmod\) and the arithmetic does not change the outcome, observe that \((-3 \cdot 19) \fmod 19 = 0\text{.}\) So \(((-8 \cdot 7) \fmod 19 = 1\text{,}\) and \((-8) \fmod 19 = 11\text{.}\) Hence \((7 \cdot 11) \fmod 19 = 1\text{,}\) and \(11\) is the inverse of \(7\) in \((\Z_{19}^\otimes,\otimes)\text{.}\)
Problem14.35.Inverse from Bézout’s identity.
Knowing that \(\gcd(113,80)=1=(17\cdot 113)+((-24)\cdot 80)\text{,}\) find the inverse of \(80\) in the group \((\Z_{113}^\otimes,\otimes)\text{.}\)
Solution.
We have \(((-24)\cdot80)+(17\cdot 113))\fmod 113=1\text{.}\) Hence \(((-24)\cdot 80)\fmod 113 =1\text{.}\) Thus the inverse of \(80\) is \((-24)\fmod 113=89\text{.}\)
In Checkpoint 14.36 apply the methods from Section 4.4 to fund the cofactors in Bézout’s identity and the read of the multiplicative modular inverse.
Checkpoint14.36.Inverse from Bézout’s identity.
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 .
We have seen that when \(a\in\Z\) is coprime to an integer \(m\) we can always find \(b\in\Z\) such that \((a \cdot b)\fmod m=1\text{.}\) When \(m\) is a prime number all elements in \(\Z_{m}^\otimes=\{1,2,\dots,m-1\}\) are coprime to \(m\) and therefor have a multiplicative inverse modulo \(m\text{.}\) We show that when \(m\) is prime then \((\Z_{m}^\otimes,\otimes)\)\(a \otimes b=(a\cdot b) \fmod m\) is a group.
Theorem14.37.
Let \(p\in\N\) be a prime number The set \(\Z_p^\otimes=\{1,\dots,p-1\}\) with the operation \(a \otimes b=(a\cdot b) \fmod p\) is a group.
Proof.
We show that \(\Z_p^\otimes\) with \(\otimes\) satisfies the properties of a group from Definition 14.2.
Identity: Since \(a\cdot 1=a\) and \(1\cdot a=a\) for all integers \(a\) we have \(a\otimes 1=(a\cdot 1)\fmod p=a\) and \(1\otimes a=(1\cdot a)\fmod p=a\fmod p=a\) for all \(a\in\Z_p^\otimes\text{.}\) Hence \(1\) is the identity with respect to \(\otimes\text{.}\)
Inverse: Since \(p\) is prime every \(a\in\Z_p^\otimes\) has an inverse with respect to \(\otimes\) by Theorem 14.33.
Associativity: Let \(a\in\Z_p^\otimes\text{,}\)\(b\in\Z_p^\otimes\text{,}\) and \(c\in\Z_p^\otimes\text{.}\) By Theorem 3.50 we only need to show that \((a\cdot(b\cdot c))\fmod p=((a\cdot b)\cdot c)\fmod p\text{.}\) This holds since \(a\cdot (b\cdot c)=(a\cdot b)\cdot c\) for all integers \(a\text{,}\)\(b\text{,}\) and \(c\) by the associative property of the integers. Hence \(\otimes\) is associative.
Commutativity: By the commutative property of multiplication of integers we have \(a\cdot b=b\cdot a\) for all integers \(a\) and \(b\text{.}\) Thus also for all \(a\in\Z_p^\otimes\) and \(b\in\Z_p^\otimes\) we have \(a\cdot b=b\cdot a\) and \(a\otimes b=(a\cdot b)\fmod p=(b\cdot a)\fmod p=b\otimes a\text{.}\)
