Discrete Mathematics for Computer Science

Subsection 11.4.1 Greatest Common Divisors

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

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

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 \mid 18\) is related to the fact that \(18/2\) is a whole number.

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 \cdot 5^2\cdot 7\text{.}\) 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\text{.}\)

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

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.

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.

To compute \(\gcd(a,b)\text{,}\) we divide \(n\) into \(m\) and get a remainder \(r\) such that \(0\leq r <\lvert b\rvert \text{.}\) By the property above, \(\gcd(a, b)= \gcd(b, r)\text{.}\) 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.

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

For fixed values of \(m\) and \(n\text{,}\) consider integers of the form \(a x+b y\) where \(x\) and \(y\) can be any two integers. For example if \(m\) = 36 and \(n\) = 27, some of these results are tabulated below with \(x\) values along the left column and the \(y\) values on top.

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?

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\text{.}\) The last nonzero value in \(r\) is the greatest common divisor.

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

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

In addition, we know that

If you substitute the expressions for \(r_{i-1}\) and \(r_{i-2}\) from (A) into this last equation and then collect the \(m\) and \(n\) terms separately you get

or

Look closely at the equations for \(r_i, s_i, \textrm{ and } t_i\text{.}\) 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 Definition 10.3.13. If two numbers, \(m\) and \(n\text{,}\) differ by a multiple of \(n\text{,}\) we say that they are congruent modulo \(n\text{,}\) denoted \(a \equiv b\pmod{n}\text{.}\) For example, \(13 \equiv 38\pmod{5}\) because \(13-38 = -25\text{,}\) which is a multiple of 5.

Subsection 11.4.4 Properties 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\text{,}\) \(\left[\mathbb{Z}_n; +_n\right]\) is a group.

Multiplication modulo \(n\) is always commutative and associative, and 1 is the identity for \(\times_n\text{.}\)

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

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 restrictions. The following group will be explored in Exercise 9.

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.

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)\text{.}\) 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)\text{,}\) 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: