Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section11.4Greatest Common Divisors and the Integers Modulo \(n\)

In this section introduce the greatest common divisor operation, and introduce an important family of concrete groups, the integers modulo \(n\text{.}\)

Subsection11.4.1Greatest Common Divisors

We start with a theorem about integer division that is intuitively clear. We leave the proof as an exercise.

Note11.4.2

The division property says that if \(m\) is divided by \(n\text{,}\) you will obtain a quotient and a remainder, where the remainder is less than \(n\text{.}\) This is a fact that most elementary school students learn when they are introduced to long division. In doing the division problem \(1986 \div 97\), you obtain a quotient of 20 and a remainder of 46. This result could either be written \(\frac{1986}{97}= 20+\frac{46}{97}\) or \(1986 = 97\cdot 20 + 46\). The latter form is how the division property is normally expressed in higher mathematics.

List11.4.3

We now remind the reader of some interchangeable terminology that is used when \(r=0\), i. e., \(a = b q\). All of the following say the same thing, just from slightly different points of view.

divides

\(b\) divides \(a\)

multiple

\(a\) is a multiple of \(b\)

factor

\(b\) is a factor of \(a\)

divisor

\(b\) is a divisor of \(a\)

We use the notation \(b \mid a\) if \(b\) divides \(a\text{.}\)

For example \(2\mid 18\) and \(9\mid 18\) , but \(4\nmid 18\).

Caution: Don't confuse the “divides” symbol with the “divided by” symbol. The former is vertical while the later is slanted. Notice however that the statement \(2 \mid 18\) is related to the fact that \(18/2\) is a whole number.

Definition11.4.4Greatest Common Divisor

Given two integers, \(a\) and \(b\text{,}\) not both zero, the greatest common divisor of \(a\) and \(b\) is the positive integer \(g=\gcd(a,b)\) such that \(g \mid a\), \(g\mid b\), and \[ c\mid a \textrm{ and } c \mid b \Rightarrow c \mid 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\text{.}\) 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\ 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.

Definition11.4.5Relatively 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.

Subsection11.4.2The 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{gather} \gcd(a,0)= a \textrm{ for } a\neq 0\label{eq-euclid-basis}\tag{11.4.1}\\ \gcd(a, b)= \gcd(b, r)\textrm{ if } b\neq 0\textrm{ and }a = b q + r\label{eq-euclid-recursion}\tag{11.4.2} \end{gather}

To compute \(\gcd(a,b)\), we divide \(b\) into \(a\) and get a remainder \(r\) such that \(0\leq r <\lvert b\rvert \). 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.

\(q\) \(a\) \(b\)
- 99 53
1 53 46
1 46 7
6 7 4
1 4 3
1 3 1
3 1 0
Table11.4.7A Table to Compute \(\gcd(99,53)\)

Here is a Sage computation to verify that \(\gcd(99, 53) = 1\text{.}\) At each line, the value of \(a\) is divided by the value of \(b\text{.}\) The quotient is placed on the next line along with the new value of \(a\text{,}\) which is the previous \(b\text{;.}\) and the remainder, which is the new value of \(b\text{.}\) Recall that in Sage, a%b is the remainder when dividing b into a.

Investigation11.4.1

If you were allowed to pick two numbers 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

For fixed values of \(a\) and \(b\text{,}\) 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.

Linear combinations of 36 and 27
Figure11.4.8Linear combinations of 36 and 27

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

Proof

To illustrate the algorithm, Table 11.4.10 displays how to compute \(\gcd(152,53)\text{.}\) 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.

\(q\) \(r\) \(s\) \(t\)
\(--\) 153 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
Table11.4.10The extended Euclidean algorithm to compute \(\gcd(152,53)\)

The “\(s\)” and “\(t\)” columns are new. The values of \(s\) and \(t\) in each row are maintained so that \(152s + 53t\) is equal to the number in the \(r\) column. Notice that

\(152 = 152\cdot 1+ 53\cdot 0\)
\(53 =152\cdot 0 + 53\cdot 1\)
\(46 = 152\cdot 1 + 53\cdot (-2)\)
\(\vdots\)
\(1 = 152\cdot 15 + 53\cdot (-43)\)
\(0 = 152 \cdot (-53) + 53\cdot 152\)
Table11.4.11Invarient in computing \(\gcd(152,53)\)

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)\text{.}\) If the \(s\) and \(t\) values in rows \(i - 1\) and \(i - 2\) are correct, we have \[(A)\textrm{ }\left\{ \begin{array}{c} a s_{i-2}+b t_{i-2}=r_{i-2} \\ a s_{i-1}+b t_{i-1}=r_{i-1} \\ \end{array} \right.\] In addition, we know that \[r_{i-2}=r_{i-1} q_i+r_i\textrm{ }\Rightarrow \textrm{ }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\left(s_{i-2}- q_is_{i-1}\right) + b\left(t_{i-2} - q_it_{i-1}\right)\] or \[s_{i }=s_{i-2}- q_is_{i-1}\textrm{ and } t_i= t_{i-2} - q_it_{i-1}\] Look closely at the equations for \(r_i, s_i, \textrm{ 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.

Subsection11.4.3Modular Arithmetic

We remind you of the relation on the integers that we call Definition 6.3.13. If two numbers, \(a\) and \(b\text{,}\) differ by a multiple of \(n\text{.}\) we say that they are congruent modulo \(n\text{,}\) denoted \(a \equiv b\pmod{n}\). For example, \(13 \equiv 38\pmod{5}\) because \(13-38 = -25\text{,}\) which is a multiple of 5.

Definition11.4.12Modular Addition

If \(n\) is a positive integer, we define addition modulo \(n\) \(\left(+_n\right.\)) as follows. If \(a, b \in \mathbb{Z}\), \[a +_n b = \textrm{ the remainder after } a + b \textrm{ is divided by } n\]

Definition11.4.13Modular Multiplication

If \(n\) is a positive integer, we define multiplication modulo \(n\) \(\left(\times_n\right.\)) as follows. If \(a, b \in \mathbb{Z}\), \[a \times_n b = \textrm{ the remainder after } a \cdot b \textrm{ is divided by } n\]

Note11.4.14

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

  2. It is always true that \(a +_n b \equiv (a + b) \pmod{n}\) and \(a\times_n b \equiv (a \cdot b) \pmod{n}\). For example, \(4 +_7 5 = 2 \equiv 9 \pmod{7}\) and \(4 \times_7 5 \equiv 6 \equiv 20 \pmod{7}\).

  3. We will use the notation \(\mathbb{Z}_n\) to denote the set \(\{0, 1, 2,. . ., n-1\}\).

Subsection11.4.4Properties of Modular Arithmetic

Addition modulo \(n\) is always commutative and associative; 0 is the identity for \(+_n\) and every element of \(\mathbb{Z}_n\) has an additive inverse. These properties can be summarized by noting that for each \(n\geq 1\), \(\left[\mathbb{Z}_n; +_n\right]\) is a group. Henceforth, we will use the abbreviated notation \(\mathbb{Z}_n\) when referring to this group, which we call “The group of integers modulo \(n\text{.}\)”

Proof

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\) on \(\mathbb{Z}_n\) are identical to the properties of addition and multiplication on \(\mathbb{Z}\text{.}\)

Example11.4.16Some Examples

  1. We are all somewhat familiar with \(\mathbb{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

  2. 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_{\textrm{ two}} = 23 \equiv 56 + 95\pmod{128}\). Integer arithmetic with this computer would actually be modulo 128 arithmetic.

Subsection11.4.5Sage 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.

In Sage, \(gcd\) 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 \(gcd(2343,4319)\). If we are working with a fixed modulus \(m\) that has a value established in your Sage session, the expression \(m.gcd(k)\) to compute the greatest common divisor of \(m\) and any integer value \(k\text{.}\) The extended Euclidean algorithm can also be called upon with \(xgcd\text{:}\)

Sage has some extremely powerful tool for working with groups. The integers modulo \(n\) are represented by the expression \(Integers(n)\) and the addition and multiplications tables can be generated as follows.

Once we have assigned \(R\) a value of \(Integers(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:

Subsection11.4.6Exercises for Section 11.4

1

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

  1. \(2^3 \cdot 3^2\cdot 5\) and \(2^2 \cdot 3 \cdot 5^2\cdot 7\)

  2. \(7! \) and \(3\cdot 5\cdot 7\cdot 9\cdot 11\cdot 13\)

  3. \(19^4\) and \(19^5\)

  4. 12112 and 0

Answer
2

Find all possible values of the following, assuming that \(m\) is a positive integer.

  1. \(\gcd(m+1,m)\)

  2. \(\gcd(m+2,m)\)

  3. \(\gcd(m+4,m)\)

3

Calculate:

  1. \(7 +_8 3\)

  2. \(7 \times_8 3\)

  3. \(4\times_8 4\)

  4. \(10+_{12} 2\)

  5. \(6\times_8 2 +_8 6\times_8 5 \)

  6. \(6\times_8 \left(2 +_85\right)\)

  7. \(3 \times_5 3 \times_5 3 \times_5 3 \equiv 3^4 (\textrm{ mod} 5)\)

  8. \(2 \times_{11}7\)

  9. \(2 \times_{14}7\)

Answer
4

List the additive inverses of the following elements:

  1. 4, 6, 9 in \(\mathbb{Z}_{10}\)

  2. 16, 25, 40 in \(\mathbb{Z}_{50}\)

5

In the group \(\mathbb{Z}_{11}\) , what are:

  1. 3(4)?

  2. 36(4)?

  3. How could you efficiently compute \(m(4)\), \(m \in \mathbb{Z}\)?

Answer
6

Prove that \(\{1, 2, 3, 4\}\) is a group under the operation \(\times_5 \).

7

A student is asked to solve the following equations under the requirement that all arithmetic should be done in \(\mathbb{Z}_2\). List all solutions.

  1. \(x^2 + 1 = 0\).

  2. \(x^2 + x + 1 = 0\).

Answer
8

Determine the solutions of the same equations as in Exercise 5 in \(\mathbb{Z}_5\).

9

  1. Write out the operation table for \(\times_8\) on \(\{1,3,5,7\}\), and convince your self that this is a group.

  2. Let \(U(\mathbb{Z}_{n})\) be the elements of \(\mathbb{Z}_{n}\) that have inverses with respect to \(\times_{n}\). Convince yourself that \(U(\mathbb{Z}_{n})\) is a group under \(\times_{n}\).

  3. Prove that the elements of \(U(\mathbb{Z}_{n})\) are those elements \(a\in \mathbb{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