## 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.5.1 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.

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

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.3.3 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.1.2 Item 2. Which implies that $$(\Z_7,\otimes)$$ is not a group.

In Example 14.5.3 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.

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.1.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.3.3 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.4.14 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.3.3.

In Checkpoint 14.5.5 work through the steps of Problem 14.5.4 that the set with the give 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

.

$$1$$

$$2$$

$$2$$

$$1$$

$$\text{the identity element is 1}$$

$$\text{each element has an inverse}$$

$$\text{associative}$$

$$\text{commutative}$$

$$\text{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.

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

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.4.1) 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.3.2) 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.5.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.5.1 with an example.

We have that $$\gcd(19,7)=1\text{.}$$ By Bézout's Identity (Theorem 4.4.1) 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{.}$$

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.5.11 apply the methods from Section 4.4 to fund the cofactors in Bézout's identity and the read of the multiplicative modular inverse.

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 .

$$728$$

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.1.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.5.8.

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.4.14 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.5.13 in which you fill in the blanks in a proof of Theorem 14.5.12.

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.

$$\text{a}$$

$$\text{a}$$

$$\text{1}$$

$$\text{identity}$$

$$\text{1}$$

$$\text{1}$$

$$\text{s}$$

$$\text{s}$$

$$\text{s}$$

$$\text{inverse}$$

$$\text{associative}$$

$$\text{associative}$$

$$\text{commutative}$$

$$\text{commutative}$$

$$\text{identity}$$
$$\text{inverse}$$
$$\text{commutative}$$