Skip to main content

Section 14.5 The 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.

Figure 14.5.1. 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.

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 =\) .

Answer 1.

\(3\)

Answer 2.

\(16\)

Answer 3.

\(23\)

Answer 4.

\(9\)

Answer 5.

\(2\)

Answer 6.

\(4\)

Answer 7.

\(3\)

Answer 8.

\(12\)

Answer 9.

\(4\)

Answer 10.

\(13\)

Answer 11.

\(5\)

Answer 12.

\(16\)

Answer 13.

\(6\)

Answer 14.

\(2\)

Answer 15.

\(7\)

Answer 16.

\(6\)

Answer 17.

\(8\)

Answer 18.

\(18\)

Answer 19.

\(9\)

Answer 20.

\(8\)

Answer 21.

\(10\)

Answer 22.

\(1\)

Answer 23.

\(11\)

Answer 24.

\(3\)

Answer 25.

\(12\)

Answer 26.

\(9\)

Answer 27.

\(13\)

Answer 28.

\(4\)

Answer 29.

\(14\)

Answer 30.

\(12\)

Answer 31.

\(15\)

Answer 32.

\(13\)

Answer 33.

\(16\)

Answer 34.

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

Strategy 14.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.

Answer 1.

\(6\)

Answer 2.

\(6\)

Answer 3.

\(6\)

Answer 4.

\(36\)

Answer 5.

\(36\)

Answer 6.

\(36\)

Answer 7.

\(51\)

Answer 8.

\(51\)

Answer 9.

\(51\)

Answer 10.

\(28\)

Answer 11.

\(28\)

Answer 12.

\(28\)

Answer 13.

\(37\)

Answer 14.

\(37\)

Answer 15.

\(37\)

Answer 16.

\(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)=\)

Answer 1.

\(1\)

Answer 2.

\(8\)

Answer 3.

\(12\)

Answer 4.

\(5\)

Answer 5.

\(1\)

Answer 6.

\(8\)

Answer 7.

\(12\)

Answer 8.

\(5\)

Answer 9.

\(1\)

Answer 10.

\(8\)

Answer 11.

\(12\)

Answer 12.

\(5\)

Answer 13.

\(1\)

Answer 14.

\(0\)