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