MAT 112 Integers and Modern Applications for the Uninitiated

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 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.2 Item 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{.}$$
1. 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{.}$$
2. 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.
3. 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.
4. 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.

Problem14.32.All multiplicative inverses modulo $$5$$.

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{.}$$

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
\begin{equation*} (s\cdot a)+(t\cdot p)=\gcd(a,p)=1\text{.} \end{equation*}
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{.}$$
We illustrate Strategy 14.1 with an example.

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
\begin{equation*} (3\cdot 19)+((-8)\cdot 7)=\gcd(19,7)=1\text{.} \end{equation*}
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.

Proof.

We show that $$\Z_p^\otimes$$ with $$\otimes$$ satisfies the properties of a group from Definition 14.2.
1. 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{.}$$
2. Inverse: Since $$p$$ is prime every $$a\in\Z_p^\otimes$$ has an inverse with respect to $$\otimes$$ by Theorem 14.33.
3. 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.
4. 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{.}$$
We end with Checkpoint 14.38 in which you fill in the blanks in a proof of Theorem 14.37.

Checkpoint14.38.$$(\Z_p^\otimes,\otimes)$$ is a group.

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.