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

Naive Exponentiation

With the naive exponentiation algorithm find $$3^{16}\bmod 23\text{.}$$

Input: Base $$b :=$$ an exponent $$n:=$$ and a modulus $$m:=$$ .

let $$c:=3$$ and let $$i:=1\text{.}$$

let $$c:=(c\cdot 3)\bmod 23 =$$ and let $$i:=i+1 =$$

let $$c:=(c\cdot 3)\bmod 23 =$$ and let $$i:=i+1 =$$

let $$c:=(c\cdot 3)\bmod 23 =$$ and let $$i:=i+1 =$$

let $$c:=(c\cdot 3)\bmod 23 =$$ and let $$i:=i+1 =$$

let $$c:=(c\cdot 3)\bmod 23 =$$ and let $$i:=i+1 =$$

let $$c:=(c\cdot 3)\bmod 23 =$$ and let $$i:=i+1 =$$

let $$c:=(c\cdot 3)\bmod 23 =$$ and let $$i:=i+1 =$$

let $$c:=(c\cdot 3)\bmod 23 =$$ and let $$i:=i+1 =$$

let $$c:=(c\cdot 3)\bmod 23 =$$ and let $$i:=i+1 =$$

let $$c:=(c\cdot 3)\bmod 23 =$$ and let $$i:=i+1 =$$

let $$c:=(c\cdot 3)\bmod 23 =$$ and let $$i:=i+1 =$$

let $$c:=(c\cdot 3)\bmod 23 =$$ and let $$i:=i+1 =$$

let $$c:=(c\cdot 3)\bmod 23 =$$ and let $$i:=i+1 =$$

let $$c:=(c\cdot 3)\bmod 23 =$$ and let $$i:=i+1 =$$

let $$c:=(c\cdot 3)\bmod 23 =$$ and let $$i:=i+1 =$$

Because the statement $$i=16$$ is true, the loop ends here.

Output: $$3^{16} \bmod 23 = c =$$ .

$$3$$

$$16$$

$$23$$

$$9$$

$$2$$

$$4$$

$$3$$

$$12$$

$$4$$

$$13$$

$$5$$

$$16$$

$$6$$

$$2$$

$$7$$

$$6$$

$$8$$

$$18$$

$$9$$

$$8$$

$$10$$

$$1$$

$$11$$

$$3$$

$$12$$

$$9$$

$$13$$

$$4$$

$$14$$

$$12$$

$$15$$

$$13$$

$$16$$

$$13$$

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.

Let $$(G,\otimes)$$ be a group and $$b\in G\text{.}$$ We set $$b^{0\otimes}=e$$ where $$e\in G$$ is the identity of $$(G,\otimes)\text{.}$$ For $$n\in\mathbb{N}$$ we set

\begin{equation*} b^{n\otimes}=\underbrace{b\otimes b\otimes\dots\otimes b}_{\mbox{n copies of b}}. \end{equation*}

In $$(\mathbb{Z}_{83}^\otimes,\otimes)$$ where $$a\otimes b=(a\cdot b)\bmod 83$$ follow these steps to compute $$6^{32\otimes}\text{.}$$

$$6^{1\otimes}=$$

$$6^{2\otimes}= 6^{1\otimes}\otimes6^{1\otimes}=$$ $$\otimes$$$$=$$

$$6^{4\otimes}= 6^{2\otimes}\otimes6^{2\otimes}=$$ $$\otimes$$$$=$$

$$6^{8\otimes}= 6^{4\otimes}\otimes6^{4\otimes}=$$ $$\otimes$$$$=$$

$$6^{16\otimes}= 6^{8\otimes}\otimes6^{8\otimes}=$$ $$\otimes$$$$=$$

$$6^{32\otimes}= 6^{16\otimes}\otimes6^{16\otimes}=$$ $$\otimes$$$$=$$

Hint.

We have $$b^{n\otimes}=b^n \bmod 83\text{.}$$ Always compute $$\bmod 83$$ before entering the answers.

$$6$$

$$6$$

$$6$$

$$36$$

$$36$$

$$36$$

$$51$$

$$51$$

$$51$$

$$28$$

$$28$$

$$28$$

$$37$$

$$37$$

$$37$$

$$41$$

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.

In $$(\mathbb{Z}_{13}^\otimes,\otimes)$$ where $$a\otimes b=(a\cdot b)\bmod 13$$ compute:

$$8^{0 \otimes}=$$

$$8^{1 \otimes}=$$

$$8^{2 \otimes}=$$

$$8^{3 \otimes}=$$

$$8^{4 \otimes}=$$

$$8^{5 \otimes}=$$

$$8^{6 \otimes}=$$

$$8^{7 \otimes}=$$

$$8^{8 \otimes}=$$

$$8^{9 \otimes}=$$

$$8^{10 \otimes}=$$

$$8^{11 \otimes}=$$

$$8^{12 \otimes}=$$

Now use the information above to find the following:

$$\log_{8}^\otimes(1)=$$

$$1$$

$$8$$

$$12$$

$$5$$

$$1$$

$$8$$

$$12$$

$$5$$

$$1$$

$$8$$

$$12$$

$$5$$
$$1$$
$$0$$