ads Greatest Common Divisors and the Integers Modulo n

Caution: Don’t confuse the “divides” symbol with the “divided by” symbol. The former is vertical while the latter is slanted. Notice however that the statement

2 ∣ 18

is related to the fact that

18 / 2

is a whole number.

🔗

Definition 11.4.4. Greatest Common Divisor.

🔗

Given two integers,

a

and

b,

not both zero, the greatest common divisor of

a

and

b

is the positive integer

g = gcd (a, b)

such that

g ∣ a,

g ∣ b,

and

c ∣ a and c ∣ b \Rightarrow c ∣ g

🔗

A little simpler way to think of

gcd (a, b)

is as the largest positive integer that is a divisor of both

a

and

b .

However, our definition is easier to apply in proving properties of greatest common divisors.

🔗

For small numbers, a simple way to determine the greatest common divisor is to use factorization. For example if we want the greatest common divisor of 660 and 350, you can factor the two integers:

660 = 2^{2} \cdot 3 \cdot 5 \cdot 11

and

350 = 2 \cdot 5^{2} \cdot 7 .

Single factors of 2 and 5 are the only ones that appear in both factorizations, so the greatest common divisor is

2 \cdot 5 = 10 .

🔗

Some pairs of integers have no common divisors other than 1. Such pairs are called relatively prime pairs.

🔗

Definition 11.4.5. Relatively Prime.

🔗

A pair of integers,

a

and

b,

are relatively prime if

gcd (a, b) = 1

🔗

For example,

128 = 2^{7}

and

135 = 3^{3} \cdot 5

are relatively prime. Notice that neither 128 nor 135 are primes. In general,

a

and

b

need not be prime in order to be relatively prime. However, if you start with a prime, like 23, for example, it will be relatively prime to everything but its multiples. This theorem, which we prove later, generalizes this observation.

🔗

Theorem 11.4.6.

🔗

p

is a prime and

a

is any integer such that

p ∤ a

then

gcd (a, p) = 1

🔗

Subsection 11.4.2 The Euclidean Algorithm

🔗

As early as Euclid’s time it was known that factorization wasn’t the best way to compute greatest common divisors.

🔗

The Euclidean Algorithm is based on the following properties of the greatest common divisor.

\begin{matrix} (11.4.1) & gcd (a, 0) = a for a \neq 0 \\ (11.4.2) & gcd (a, b) = gcd (b, r) if b \neq 0 and a = b q + r \end{matrix}

🔗

To compute

gcd (a, b),

we divide

b

into

a

and get a remainder

r

such that

0 \leq r < | b | .

By the property above,

gcd (a, b) = gcd (b, r) .

We repeat the process until we get zero for a remainder. The last nonzero number that is the second entry in our pairs is the greatest common divisor. This is inevitable because the second number in each pair is smaller than the previous one. Table 11.4.7 shows an example of how this calculation can be systematically performed.

🔗

Table 11.4.7. A Table to Compute

gcd (99, 53)

$q$	$a$	$b$
-	99	53
1	53	46
1	46	7
6	7	4
1	4	3
1	3	1
3	1	0

🔗

Here is a Sage computation to verify that

gcd (99, 53) = 1 .

At each line, the value of

a

is divided by the value of

b .

The quotient is placed on the next line along with the new value of

a,

which is the previous

b;

and the remainder, which is the new value of

b .

Recall that in Sage, a%b is the remainder when dividing b into a.

xxxxxxxxxx
 
a=99
b=53
while b>0:
    print('computing gcd of '+str(a)+' and '+str(b))
    [a,b]=[b,a%b]
print('result is '+str(a))

🔗

Investigation 11.4.1.

🔗

If you were allowed to pick two integers less than 100, which would you pick in order to force Euclid to work hardest? Here’s a hint: The size of the quotient at each step determines how quickly the numbers decrease.

Solution.

If quotient in division is 1, then we get the slowest possible completion. If

a = b + r,

then working backwards, each remainder would be the sum of the two previous remainders. This described a sequence like the Fibonacci sequence and indeed, the greatest common divisor of two consecutive Fibonacci numbers will take the most steps to reach a final value of 1.

🔗

For fixed values of

a

and

b,

consider integers of the form

a x + b y

where

x

and

y

can be any two integers. For example if

a

= 36 and

b

= 27, some of these results are tabulated below with

x

values along the left column and the

y

values on top.

🔗
Figure 11.4.8. Linear combinations of 36 and 27

🔗

Do you notice any patterns? What is the smallest positive value that you see in this table? How is it connected to 36 and 27?

🔗

Theorem 11.4.9. Bézout’s lemma.

🔗

a

and

b

are positive integers, the smallest positive value of

a x + b y

is the greatest common divisor of

a

and

b,

gcd (a, b) .

Proof.

g = gcd (a, b),

since

g ∣ a

and

g ∣ b,

we know that

g ∣ (a x + b y)

for any integers

x

and

y,

a x + b y

can’t be less than

g .

To show that

g

is exactly the least positive value, we show that

g

can be attained by extending the Euclidean Algorithm. Performing the extended algorithm involves building a table of numbers. The way in which it is built maintains an invariant, and by The Invariant Relation Theorem, we can be sure that the desired values of

x

and

y

are produced.

🔗

To illustrate the algorithm, Table 11.4.10 displays how to compute

gcd (152, 53) .

In the

r

column, you will find 152 and 53, and then the successive remainders from division. So each number in

r

after the first two is the remainder after dividing the number immediately above it into the next number up. To the left of each remainder is the quotient from the division. In this case the third row of the table tells us that

152 = 53 \cdot 2 + 46 .

The last nonzero value in

r

is the greatest common divisor.

🔗

Table 11.4.10. The extended Euclidean algorithm to compute

gcd (152, 53)

$q$	$r$	$s$	$t$
$- -$	152	1	0
$- -$	53	0	1
2	46	1	$- 2$
1	7	$- 1$	3
6	4	7	$- 20$
1	3	$- 8$	23
1	1	15	$- 43$
3	0	$- 53$	152

🔗

The “

s

” and “

t

” columns are new. The values of

s

and

t

in each row are maintained so that

152 s + 53 t

is equal to the number in the

r

column. Notice that

🔗

Table 11.4.11. Invariant in computing

gcd (152, 53)

152 = 152 \cdot 1 + 53 \cdot 0

53 = 152 \cdot 0 + 53 \cdot 1

46 = 152 \cdot 1 + 53 \cdot (- 2)

⋮

1 = 152 \cdot 15 + 53 \cdot (- 43)

0 = 152 \cdot (- 53) + 53 \cdot 152

🔗

The next-to-last equation is what we’re looking for in the end! The main problem is to identify how to determine these values after the first two rows. The first two rows in these columns will always be the same. Let’s look at the general case of computing

gcd (a, b) .

If the

s

and

t

values in rows

i - 1

and

i - 2

are correct, we have

(A) {\begin{matrix} a s_{i - 2} + b t_{i - 2} = r_{i - 2} \\ a s_{i - 1} + b t_{i - 1} = r_{i - 1} \end{matrix}

🔗

In addition, we know that

r_{i - 2} = r_{i - 1} q_{i} + r_{i} \Rightarrow r_{i} = r_{i - 2} - r_{i - 1} q_{i}

🔗

If you substitute the expressions for

r_{i - 1}

and

r_{i - 2}

from (A) into this last equation and then collect the

a

and

b

terms separately you get

r_{i} = a (s_{i - 2} - q_{i} s_{i - 1}) + b (t_{i - 2} - q_{i} t_{i - 1})

🔗

s_{i} = s_{i - 2} - q_{i} s_{i - 1} and t_{i} = t_{i - 2} - q_{i} t_{i - 1}

🔗

Look closely at the equations for

r_{i}, s_{i}, and t_{i} .

Their forms are all the same. With a little bit of practice you should be able to compute

s

and

t

values quickly.

🔗

Subsection 11.4.3 Modular Arithmetic

🔗

We remind you of the relation on the integers that we call Congruence Modulo

n

. If two integers,

a

and

b,

differ by a multiple of

n,

we say that they are congruent modulo

n,

denoted

a \equiv b (\mod n) .

For example,

13 \equiv 38 (\mod 5)

because

13 - 38 = - 25,

which is a multiple of 5.

🔗

Definition 11.4.12. The Integers Modulo $n$ .

🔗

n

is a positive integer greater than one, we define the integers modulo

n

to be the set

{0, 1, 2, . . ., n - 1} .

🔗

Definition 11.4.13. Modular Addition.

🔗

n

is a positive integer, we define addition modulo

n

(+_{n}

) as follows. If

a, b \in Z_{n},

a +_{n} b = the remainder after a + b is divided by n

🔗

Definition 11.4.14. Modular Multiplication.

🔗

n

is a positive integer, we define multiplication modulo

n

(\times_{n}

) as follows. If

a, b \in Z_{n},

a \times_{n} b = the remainder after a \cdot b is divided by n

🔗

Note 11.4.15.

🔗

The result of doing arithmetic modulo $n$ is always an integer between 0 and $n - 1,$ by the Division Property. This observation implies that ${0, 1, \dots, n - 1}$ is closed under modulo $n$ arithmetic.
It is always true that $a +_{n} b \equiv (a + b) (\mod n)$ and $a \times_{n} b \equiv (a \cdot b) (\mod n) .$ For example, $4 +_{7} 5 = 2 \equiv 9 (\mod 7)$ and $4 \times_{7} 5 = 6 \equiv 20 (\mod 7) .$
One interpretation of $Z_{n}$ is that each element is a representative of its equivalence class with respect to congruence modulo $n .$ For example, if $n = 7,$ the number $1$ in $Z_{7}$ really represents all numbers in $[1] = 1 + 7 k : k \in Z .$ In doing modular arithmetic, we can temporarily replace elements of $Z_{n}$ with other elements in their equivalence class modulo $n .$

Example 11.4.16. Some Examples.

We are all somewhat familiar with $Z_{12}$ since the hours of the day are counted using this group, except for the fact that 12 is used in place of 0. Military time uses the mod 24 system and does begin at 0. If someone started a four-hour trip at hour 21, the time at which she would arrive is $21 +_{24} 4 = 1 .$ If a satellite orbits the earth every four hours and starts its first orbit at hour 5, it would end its first orbit at time $5 +_{24} 4 = 9 .$ Its tenth orbit would end at $5 +_{24} 10 \times_{24} 4 = 21$ hours on the clock
Virtually all computers represent unsigned integers in binary form with a fixed number of digits. A very small computer might reserve seven bits to store the value of an integer. There are only $2^{7}$ different values that can be stored in seven bits. Since the smallest value is 0, represented as 0000000, the maximum value will be $2^{7} - 1 = 127,$ represented as 1111111. When a command is given to add two integer values, and the two values have a sum of 128 or more, overflow occurs. For example, if we try to add 56 and 95, the sum is an eight-digit binary integer 10010111. One common procedure is to retain the seven lowest-ordered digits. The result of adding 56 and 95 would be $0010111_{two} = 23 \equiv 56 + 95 (\mod 128) .$ Integer arithmetic with this computer would actually be modulo 128 arithmetic.

🔗

Subsection 11.4.4 Properties of Modular Arithmetic

🔗

Theorem 11.4.17. Additive Inverses in $Z_{n}$ .

🔗

a \in Z_{n},

a \neq 0,

then the additive inverse of a is

n - a .

Proof.

a + (n - a) = n \equiv 0 (mod n),

since

n = n \cdot 1 + 0 .

Therefore,

a +_{n} (n - a) = 0 .

🔗

Addition modulo

n

is always commutative and associative; 0 is the identity for

+_{n}

and every element of

Z_{n}

has an additive inverse. These properties can be summarized by noting that for each

n \geq 1,

[Z_{n}; +_{n}]

is a group.

🔗

Definition 11.4.18. The Additive Group of Integers Modulo $n$ .

🔗

The Additive Group of Integers Modulo

n

is the group with domain

{0, 1, 2, \dots, n - 1}

and with the operation of mod

n

addition. It is denoted as

Z_{n} .

🔗

Multiplication modulo

n

is always commutative and associative, and 1 is the identity for

\times_{n} .

🔗

Notice that the algebraic properties of

+_{n}

and

\times_{n}

Z_{n}

are identical to the properties of addition and multiplication on

Z .

🔗

Notice that a group cannot be formed from the whole set

{0, 1, 2, \dots, n - 1}

with mod

n

multiplication since zero never has a multiplicative inverse. Depending on the value of

n

there may be other numbers that will be excluded.

🔗

Definition 11.4.19. The Multiplicative Group of Integers Modulo $n$ .

🔗

The Multiplicative Group of Integers Modulo

n

is the group with domain

{k \in Z | 1 \leq k \leq n - 1 and gcd (n, k) = 1}

and with the operation of mod

n

multiplication. It is denoted as

U_{n} .

Example 11.4.20. Some operation tables.

Here are examples of operation tables for modular groups. Notice that although 8 is greater than 5, the two groups

U_{5}

and

U_{8}

both have order 4. In the case of

U_{5},

since 5 is prime all of the nonzero elements of

Z_{5}

are included. Since 8 isn’t prime we don’t include integers that share a common factor with 8, the even integers in this case.

$+_{5}$	$0$	$1$	$2$	$3$	$4$
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

Table 11.4.21. Operation Table for the group

Z_{5}

$\times_{5}$	$1$	$2$	$3$	$4$
1	1	2	3	4
2	2	4	1	3
3	3	1	4	2
4	4	3	2	1

Table 11.4.22. Operation table for the group

U_{5}

$\times_{8}$	$1$	$3$	$5$	$7$
1	1	3	5	7
3	3	1	7	5
5	5	7	1	3
7	7	5	3	1

Table 11.4.23. Operation table for the group

U_{8}

🔗

Computing Modular Multiplicative Inverses. Unlike the nice neat formula for additive inverses mod

n,

multiplicative inverses can most easily computed by applying Bézout’s lemma. If

a

is an element of the group

U_{n},

then by definition

gcd (n, a) = 1,

and so there exist integers

s

and

t

such that

1 = n s + a t .

They can be computed with the Extended Euclidean Algorithm.

1 = n s + a t \Rightarrow a t = 1 + (- s) n \Rightarrow a \times_{n} t = 1

🔗

Since

t

might not be in

U_{n}

you might need take the remainder after dividing it by

n .

Normally, that involves simply adding

n

t .

🔗

For example, in

U_{2048},

if we want the muliplicative inverse of

1001,

we run the Extended Euclidean Algorithm and find that

gcd (2048, 1001) = 1 = 457 \cdot 2048 + (- 935) \cdot 1001

🔗

Thus, the multiplicative inverse of 1001 is

2048 - 935 = 1113 .

See the SageMath Note below to see how to run the Extended Euclidean Algorithm.

🔗

Subsection 11.4.5 SageMath Note - Modular Arithmetic

🔗

Sage inherits the basic integer division functions from Python that compute a quotient and remainder in integer division. For example, here is how to divide 561 into 2017 and get the quotient and remainder.

xxxxxxxxxx
 
a=2017
b=561
[q,r]=[a//b,a%b]
[q,r]

🔗

In Sage,

g c d

is the greatest common divisor function. It can be used in two ways. For the gcd of 2343 and 4319 we can evaluate the expression

g c d (2343, 4319) .

If we are working with a fixed modulus

m

that has a value established in your Sage session, the expression

m . g c d (k)

to compute the greatest common divisor of

m

and any integer value

k .

The extended Euclidean algorithm can also be called upon with

x g c d :

xxxxxxxxxx
 
a=2017
b=561
print(gcd(a,b))
print(xgcd(a,b))

🔗

Sage has some extremely powerful tool for working with groups. The integers modulo

n

are represented by the expression

I n t e g e r s (n)

and the addition and multiplications tables can be generated as follows.

xxxxxxxxxx
 
R = Integers(6)
print(R.addition_table('elements'))
print(R.multiplication_table('elements'))

🔗

Once we have assigned

R

a value of

I n t e g e r s (6),

we can do calculations by wrapping

R ()

around the integers 0 through 5. Here is a list containing the mod 6 sum and product, respectively, of 5 and 4:

xxxxxxxxxx
 
[R(5)+R(4), R(5)*R(4)]

🔗

Generating the multiplication table for the family of groups

U_{n}

takes a bit more code. Here we restrict the allowed inputs to be integers from 2 to 64.

xxxxxxxxxx
 
def U_table(n):
    if n.parent()!=2.parent() or n < 2 or n > 64:
        return "input error/out of range"
    R=Integers(n)
    els=[]
    for k in filter(lambda k:gcd(n,k)==1,range(n)):
        els=els+[str(k)]
    return R.multiplication_table(elements=els,names="elements")
    
U_table(18)

🔗

Exercises 11.4.6 Exercises

🔗

1.

🔗

Determine the greatest common divisors of the following pairs of integers without using any computational assistance.

$2^{3} \cdot 3^{2} \cdot 5$ and $2^{2} \cdot 3 \cdot 5^{2} \cdot 7$
$7!$ and $3 \cdot 5 \cdot 7 \cdot 9 \cdot 11 \cdot 13$
$19^{4}$ and $19^{5}$
12112 and 0

Answer.

$2^{2} \cdot 3 \cdot 5$
$3^{2} \cdot 5 \cdot 7$
$19^{4}$
12112

🔗

2.

🔗

Find all possible values of the following, assuming that

m

is a positive integer.

$gcd (m + 1, m)$
$gcd (m + 2, m)$
$gcd (m + 4, m)$

🔗

3.

🔗

Calculate:

$7 +_{8} 3$
$7 \times_{8} 3$
$4 \times_{8} 4$
$10 +_{12} 2$
$6 \times_{8} 2 +_{8} 6 \times_{8} 5$
$6 \times_{8} (2 +_{8} 5)$
$3 \times_{5} 3 \times_{5} 3 \times_{5} 3 \equiv 3^{4} (mod 5)$
$2 \times_{11} 7$
$2 \times_{14} 7$

Answer.

🔗

4.

🔗

List the additive inverses of the following elements:

4, 6, 9 in $Z_{10}$
16, 25, 40 in $Z_{50}$

🔗

5.

🔗

In the group

Z_{11}

, what are:

3(4)?
36(4)?
How could you efficiently compute $m (4),$ $m \in Z ?$

Answer.

1
1
$m (4) = r (4),$ where $m = 11 q + r,$ $0 \leq r < 11$

🔗

6.

🔗

When defining notice that we could define this operation on all integers, but we restricted the set to

Z_{n}

to satisfy the properties of a group. Can you explain what goes wrong if we define

+_{n}

on all of the integers?

🔗

7.

🔗

A student is asked to solve the following equations under the requirement that all arithmetic should be done in

Z_{2} .

List all solutions.

$x^{2} + 1 = 0 .$
$x^{2} + x + 1 = 0 .$

Answer.

Since the solutions, if they exist, must come from

Z_{2},

substitution is the easiest approach.

1 is the only solution, since $1^{2} +_{2} 1 = 0$ and $0^{2} +_{2} 1 = 1$
No solutions, since $0^{2} +_{2} 0 +_{2} 1 = 1,$ and $1^{2} +_{2} 1 +_{2} 1 = 1$

🔗

8.

🔗

Determine the solutions of the same equations as in Exercise 5 in

Z_{5} .

🔗

9.

🔗

Write out the operation table for $\times_{1} 4$ on ${1, 3, 5, 9, 11, 13},$ and convince your self that this is a group.
Let $U_{n}$ be the elements of $Z_{n}$ that have inverses with respect to $\times_{n} .$ Convince yourself that $U_{n}$ is a group under $\times_{n} .$
Prove that the elements of $U_{n}$ are those elements $a \in Z_{n}$ such that $gcd (n, a) = 1 .$ You may use Theorem 11.4.9 in this proof.

🔗

10.

🔗

Prove the division property, Theorem 11.4.1.

Hint.

Prove by induction on

m

that you can divide any positive integer into

m .

That is, let

p (m)

be “For all

n

greater than zero, there exist unique integers

q

and

r

such that

\dots

.” In the induction step, divide

n

into

m - n .

🔗

11.

🔗

Suppose

f : Z_{17} \to Z_{17}

such

f (i) = a \times_{17} i +_{17} b

where

a

and

b

are integer constants. Furthermore, assume that

f (1) = 11

and

f (2) = 4 .

Find a formula for

f (i)

and also find a formula for the inverse of

f .

Solution.

The given conditions can be converted to a system of linear equations:

\begin{matrix} f (1) = 11 \Rightarrow a +_{17} b = 11 \\ f (2) = 4 \Rightarrow 2 \times_{17} a +_{17} b = 4 \end{matrix}

If we subtract the first equation from the second, we get

a = 4 +_{17} (- 11) = 4 +_{17} 6 = 10 .

This implies that

b = 1,

and

f (i) = 10 \times + 17 i + 1 .

To get a formula for the inverse of

f

we solve

f (j) = i

for

j,

using the fact that the multiplicative inverse of 10 (mod 17) is 12.

\begin{aligned} f (j) = i & \Rightarrow 10 \times + 17 j + 1 = i \\ \Rightarrow 10 \times + 17 j = i +_{17} 16 \\ \Rightarrow j = 12 \times_{17} (i +_{17} 16) \end{aligned}

Therefore

f^{- 1} (i) = 12 \times_{17} (i +_{17} 16) = 12 \times_{17} i +_{17} 5 .

🔗

12.

🔗

Write out the operation table for mod 10 multiplication on

T = {0, 2, 4, 6, 8} .

[T; \times_{10}]

a monoid? Is it a group?

Solution.

This system is a monoid with identity 6 (surprise!). However it is not a group since 0 has no inverse.

🔗

13.

🔗

Given that

1 = 2021 \cdot (- 169) + 450 \cdot 759,

explain why

450

is an element of the group

U_{2021}

and determine its inverse in that group.

Solution.

By Bézout’s lemma,

450

is an element of

U_{2021} .

It’s inverse in the group is

759

because

450 \cdot 759 = 2021 \cdot 169 + 1 \Rightarrow 450 \times_{2021} 759 = 1.

🔗

14.

🔗

Let

n = 2021 .

Solve

450 \times_{n} x = 321

for

x

in the group

U_{n}

🔗

15.

🔗

Let

p

be an odd prime. Find all solutions to the equation

x^{2} = x \times_{n} x = 1

in the group

U_{p} .

🔗

16.

🔗

It was observed above that in doing modular arithmetic, one can replace an element of

Z_{n}

with any other element of its equivalence class modulo

n .

For example, if one is computing

452 \times_{461} 7,

the alternative to multiplying

452

time

7

and then dividing by

461

to get the remainder in

Z_{461},

we can replace

452

with

- 9

and get a product of

- 63

which is conguent of

398 .

Use this “trick” to compute the following without the use of a calculator.

🔗

$898 \times_{1001} 998$
$77^{10} \mod 81$
The solution to $196 \times_{197} x = 120$

🔗

17.

🔗

We associate the set

Z_{n} = {0, 1, 2, ..., n - 1}

with the addition modulo

n,

+_{n},

because the pair

[Z_{n}; +_{n}]

form a group. Why must we use a matching modulus? Explain why by considering the following two examples.

$[Z_{3}, +_{2}]$
$[Z_{3}, +_{4}]$

You have attempted of activities on this page.

Prev Top Next

Section 11.4 Greatest Common Divisors and the Integers Modulo n

Subsection 11.4.1 Greatest Common Divisors

Theorem 11.4.1. The Division Property for Integers.

Note 11.4.2.

Definition 11.4.4. Greatest Common Divisor.

Definition 11.4.5. Relatively Prime.

Theorem 11.4.6.

Subsection 11.4.2 The Euclidean Algorithm

Investigation 11.4.1.

Theorem 11.4.9. Bézout’s lemma.

Proof.

Subsection 11.4.3 Modular Arithmetic

Definition 11.4.12. The Integers Modulo n.

Definition 11.4.13. Modular Addition.

Definition 11.4.14. Modular Multiplication.

Note 11.4.15.

Example 11.4.16. Some Examples.

Subsection 11.4.4 Properties of Modular Arithmetic

Theorem 11.4.17. Additive Inverses in Zn.

Proof.

Definition 11.4.18. The Additive Group of Integers Modulo n.

Definition 11.4.19. The Multiplicative Group of Integers Modulo n.

Example 11.4.20. Some operation tables.

Subsection 11.4.5 SageMath Note - Modular Arithmetic

Exercises 11.4.6 Exercises

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

Section 11.4 Greatest Common Divisors and the Integers Modulo $n$

Definition 11.4.12. The Integers Modulo $n$ .

Theorem 11.4.17. Additive Inverses in $Z_{n}$ .

Definition 11.4.18. The Additive Group of Integers Modulo $n$ .

Definition 11.4.19. The Multiplicative Group of Integers Modulo $n$ .