## Chapter 27Notes for the eighth week: GCD, LCM, ax + by = c

Notes also available as PDF.

What we covered last week:

• divisibility and prime numbers,
• factorization into primes,
• modular arithmetic,
• finding divisibility rules,

This week’s topics:

• review modular arithmetic and finding divisibility rules,
• greatest common divisors and least common factors,
• Euclid’s algorithm for greatest common divisors, and
• solving linear Diophantine equations.

These all are useful when you deal with integral numbers of things

### 27.1 Modular arithmetic

Remember the divisibility form for b with respect to dividing by a\mathrel{≠}0,

 b = q ⋅ a + r,\text{ with }0 ≤ r < |a|.

This form is unique for a given a and b.

Consider a = 5. There are only five possible values of r, zero through four. Because the form is unique, we can place every b into one of r congruence classes. Each congruence class is a set. For a = 5, we have the following classes:

 \{\mathop{\mathop{…}}, -10, -5, 0, 5, 10, \mathop{\mathop{…}}\} = \{5k + 0\kern 1.66702pt |\kern 1.66702pt k J\} \{\mathop{\mathop{…}}, -9, -4, 1, 6, 11, \mathop{\mathop{…}}\} = \{5k + 1\kern 1.66702pt |\kern 1.66702pt k J\} \{\mathop{\mathop{…}}, -8, -3, 2, 7, 12, \mathop{\mathop{…}}\} = \{5k + 2\kern 1.66702pt |\kern 1.66702pt k J\} \{\mathop{\mathop{…}}, -7, -2, 3, 8, 13, \mathop{\mathop{…}}\} = \{5k + 3\kern 1.66702pt |\kern 1.66702pt k J\} \{\mathop{\mathop{…}}, -6, -1, 4, 9, 14, \mathop{\mathop{…}}\} = \{5k + 4\kern 1.66702pt |\kern 1.66702pt k J\}

We say that two numbers are in the same congruence class for a given a by

 b ≡ c\kern 18mu ({\rm mod}\kern 6mu a).

Or b is equivalent to c modulo a. A collection of one entry from each set is called a complete residue system. We typically select the least positive numbers, those in bold above.

We define arithmetic on congruence classes by arithmetic on the remainders. The remainders wrap around every multiple of the modulus. For example, addition modulo 4 and modulo 5 are defined as follows:

 +\kern 18mu ({\rm mod}\kern 6mu 4) 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2

 +\kern 18mu ({\rm mod}\kern 6mu 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

This works as you expect. Addition is commutative and associative. There is an additive identity, because b + 0 ≡ 0\kern 18mu ({\rm mod}\kern 6mu a). Unlike the positive integers, there also is an additive inverse for every residue because b + (a - b) ≡ 0\kern 18mu ({\rm mod}\kern 6mu a).

Multiplication likewise is commutative and associative, and there is a multiplicative identity, 1. The unusual aspect appears with the multiplicative inverse. Some residues have inverses, and some don’t:

 ×\kern 18mu ({\rm mod}\kern 6mu 4) 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1

 ×\kern 18mu ({\rm mod}\kern 6mu 5) 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1

The difference here is that 5 is prime while 4 is composite. Any factor of the modulus will not have a multiplicative inverse.

### 27.2 Divisibility rules

One common application of modular arithmetic (besides telling time) is in testing whether one integer divides another. We use modular arithmetic and positional notation. Both help us break the larger problem, testing divisibility of a potentially large number, into the smaller problems of breaking apart the number and evaluating expressions in modular arithmetic.

If a\mathrel{∣}b (a divides b), then b ≡ 0\kern 18mu ({\rm mod}\kern 6mu a). So we can test for divisibility by expanding b in positional notation and evaluating the operations modulo a.

When the divisor is small, a straight-forward evaluation is simplest. Because 10 ≡ 1\kern 18mu ({\rm mod}\kern 6mu 3), we can test for divisibility by 3 by adding the number’s digits modulo 3. For example,

\eqalignno{ 1234 & ≡ 1{0}^{3} + 2 ⋅ 1{0}^{2} + 3 ⋅ 10 + 4\kern 18mu ({\rm mod}\kern 6mu 3) & & \cr & ≡ {1}^{3} + 2 ⋅ {1}^{2} + 3 ⋅ 1 + 4\kern 18mu ({\rm mod}\kern 6mu 3) & & \cr & ≡ 1 + 2 + 3 + 4 ≡ 1 + 2 + 0 + 1 ≡ 1\kern 18mu ({\rm mod}\kern 6mu 3). & & }

Hence 3 ∤ 1234. The same “trick” applies to 9 because 10 ≡ 1\kern 18mu ({\rm mod}\kern 6mu 9).

When the divisor is closer to a power of 10, using a negative element of the congruence class may be useful. For 11, remember that 10 and - 1 are in the same congruence class because 10 = 0 ⋅ 11 + 10 and - 1 = -1 ⋅ 11 + 10. So 10 ≡-1\kern 18mu ({\rm mod}\kern 6mu 11) and we can expand the powers of ten,

\eqalignno{ 1234 & ≡ 1{0}^{3} + 2 ⋅ 1{0}^{2} + 3 ⋅ 10 + 4\kern 18mu ({\rm mod}\kern 6mu 11) & & \cr & ≡ {(-1)}^{3} + 2 ⋅ {(-1)}^{2} + 3 ⋅ (-1) + 4\kern 18mu ({\rm mod}\kern 6mu 11) & & \cr & ≡-1 + 2 + -3 + 4\kern 18mu ({\rm mod}\kern 6mu 11) ≡ 2\kern 18mu ({\rm mod}\kern 6mu 11). & & \cr & & }

Hence 11 ∤ 1234. Here, the “trick” form is that you start from the units digit and then alternate subtracting and adding digits.

For more complicated examples, we can factor the divisor. To test if a number is divisible by 72, factor 72 = {2}^{3} ⋅ {3}^{2} = 8 ⋅ 9. Then test if the number is divisible by 8 and by 9.

If a\mathrel{∣}b and c\mathrel{∣}b, then it may be true that ac\mathrel{∣}b. This is certainly true of a and b are powers of different primes. The key point is that a and b share no common divisors. Note that 72 = 6 ⋅ 12, 6\mathrel{∣}24, and 12\mathrel{∣}24, but obviously 72 ∤ 24 because 24 < 72.

### 27.3 Greatest common divisor

So finding common divisors is useful for testing divisibility. The greatest common divisor of numerator and denominator reduces a fraction into its simplest form. In general, common divisors help break problems apart.

Written (a,b) or \mathop{gcd}(a,b), the greatest common divisor of a and b is the largest integer d ≥ 1 that divides both a and b.

We’ll discuss a total of two methods for finding the greatest common divisor. The first uses the prime factorization, and the second uses the divisibility form in the Euclidean algorithm. Later we’ll extend the Euclidean algorithm to provide integer solutions x and y to equations ax + by = c.

The prime factorization method factors both a and b. Consider a = 1400 = {2}^{3} ⋅ {5}^{2} ⋅ 7 and b = 1350 = 2 ⋅ {3}^{3} ⋅ {5}^{2}.

Lining up the factorizations and remembering that {x}^{0} = 1, we have

 a = 1400 = {2}^{3} ⋅ {3}^{\mathbf{0}} ⋅ {5}^{\mathbf{2}} ⋅ {7}^{1}, and b = 1350 = {2}^{\mathbf{1}} ⋅ {3}^{3} ⋅ {5}^{\mathbf{2}} ⋅ {7}^{\mathbf{0}}.

Now chose the least exponent for each factor. Then

 d = {2}^{1} ⋅ {3}^{0} ⋅ {5}^{2} ⋅ {7}^{0} = 50

is the greatest common divisor. For more than two integers, factor all the integers and find the least exponents across the corresponding factors in all of the factorizations.

For an example use, reduce a fraction a∕b = 1350∕1400 to its simplest form. To do so, divide the top and bottom by d = 50. Then a∕b = 1350∕1400 = 27∕28.

Now we can state the requirement about divisibility given some factors:

If two relatively prime integers a and b both divide c, then ab divides c.

Some other properties of the gcd:

• Because the gcd is positive, (a,b) = (|a|,|b|).
• (a,b) = (b,a)
• If the gcd of two numbers is 1, or (a,b) = 1, then a and b are called relatively prime.

### 27.4 Least common multiple

Before the other method for finding the gcd, we consider one related quantity.

The least common multiple, often written \mathop{lcm}\nolimits (a,b), is the least number L ≥ a and L ≥ b such that a\mathrel{∣}L and b\mathrel{∣}L.

There are clear, every day uses. Think of increasing a recipe when you can only buy whole bags of some ingredient. You need to find the least common multiple of the recipe’s requirement and the bag’s quantity. Or when you need to find the next day two different schedules intersect.

Again, you can work from the prime factorizations

 a = 1400 = {2}^{\mathbf{3}} ⋅ {3}^{0} ⋅ {5}^{\mathbf{2}} ⋅ {7}^{\mathbf{1}}, and b = 1350 = {2}^{1} ⋅ {3}^{\mathbf{3}} ⋅ {5}^{\mathbf{2}} ⋅ {7}^{0}.

Now the least common multiple is the product of the larger exponents,

 \mathop{lcm}\nolimits (a,b) = {2}^{3} ⋅ {3}^{3} ⋅ {5}^{2} ⋅ {7}^{1} = 37\kern 1.66702pt 800.

And for more than two integers, take the maximum across all the exponents of corresponding factors.

Another relation for two integers a and b is that

 \mathop{lcm}\nolimits (a,b) = {ab\over d} .

So given a = 1350, b = 1400, and d = 50,

 \mathop{lcm}\nolimits (1350,1400) = {1350 ⋅ 1400\over 50} = {1\kern 1.66702pt 890\kern 1.66702pt 000\over 50} = 37\kern 1.66702pt 800.

This does not hold directly for more than two integers.

### 27.5 Euclidean GCD algorithm

Another method for computing the gcd of two integers a and b is due to Euclid. This often is called the first algorithm expressed as an abstract sequence of steps.

We start with the division form of b in terms of a\mathrel{≠}0,

 b = qa + r\text{ with }0 ≤ r < a.

Because (a,b) = (|a|,|b|), we can assume both a and b are non-negative. And because (a,b) = (b,a), we can assume b ≥ a.

Let d = (a,b). Last week we showed that if d|a and d|b, then d|ra + sb for any integers r and s. Then because d|a and d|b, we have d|b - qa or d|r. So we have that d = (b,a) also divides r. Note that any number that divides a and r also divides b, so d = (a,r).

Continuing, we can express a in terms of r as

 a = q'r + r'\text{ with }0 ≤ r' < r.

Now d|r' and d = (r,r'). Note that r' < r < a, so the problem keeps getting smaller! Eventually, some remainder will be zero. Then the previous remainder is the greatest common divisor.

1. Find {q}_{0} and {r}_{0} in b = {q}_{0}a + {r}_{0} with 0 ≤ {r}_{0} < a.
2. If {r}_{0} = 0, then (a,b) = a.
3. Let {r}_{-1} = a to make the loop easier to express.
4. Then for i = 1,\mathop{\mathop{…}}
1. Find {q}_{i} and {r}_{i} in {r}_{i-2} = {q}_{i}{r}_{i-1} + {r}_{i} with 0 ≤ {r}_{i} < {r}_{i-1}.
2. If {r}_{i} = 0, then (a,b) = {r}_{i-1} and quit.
3. Otherwise continue to the next i.

Consider calculating (53,77). Following the steps, we have

\eqalignno{ 77 & = 1 ⋅ 53 + 24, & & \cr 53 & = 2 ⋅ 24 + 5, & & \cr 24 & = 4 ⋅ 5 + 4, & & \cr 5 & = 1 ⋅ 4 + 1,\text{ and} & & \cr 4 & = 4 ⋅ 1 + 0. & & }

And thus (53,77) = 1.

For another example, take (128,308). Then

\eqalignno{ 308 & = 2 ⋅ 128 + 52, & & \cr 128 & = 2 ⋅ 52 + 24, & & \cr 52 & = 2 ⋅ 24 + 4,\text{ and} & & \cr 24 & = 6 ⋅ 4 + 0. & & }

So (128,308) = 4.

### 27.6 Linear Diophantine equations : Likely delayed

Later in the semester, we will examine linear equations ax + by = c over real numbers. But many every-day applications require integer solutions. We can use the Euclidean algorithm to find one integer solution to ax + by = c or prove there are none. Then we can use the computed gcd to walk along the line to all integer solutions.

Say we need to solve ax + by = c for integers a, b, and c to find integer solutions x and y. In general, equations over integers are called Diophantine equations after Diophantus of Alexandria (approx. 200AD-290AD). He was the first known to study these equations using algebra. The form ax + b = c describes linear Diophantine equations.

Let d = (a,b). Then, as before, d\mathrel{∣}ax + by for all integers x and y. So d\mathrel{∣}c for any solutions to exist. If d ∤ c, then there are no integer solutions. If a and b are relatively prime, then (a,b) = 1 and solutions exist for any integer c.

Consider solving ax + by = d. Because d\mathrel{∣}c, we can multiply solutions to ax + by = d by c∕d to obtain solutions of ax + by = c. To solve ax + by = d we work backwards after using the Euclidean algorithm to compute d = (a,b).

Say the algorithm required k steps, so d = {r}_{k-1}. Working backward one step,

\eqalignno{ d = {r}_{k-1} & = {r}_{k-3} - {q}_{k-1}{r}_{k-2} & & \cr & = {r}_{3} - {q}_{k-1}({r}_{k-4} - {q}_{k-2}{r}_{k-3}) & & \cr & = (1 + {q}_{k-1}{q}_{k-2}){r}_{3} - {q}_{k-1}{r}_{k-4}. & & \cr & & }

So d = {r}_{k-1} = i ⋅ {r}_{k-3} + j ⋅ {r}_{k-4} where i and j are integers. Continuing, the gcd d can be expressed as an integer combination of each pair of remainders.

Returning to the example of (77,53),

\eqalignno{ 1 & = 5 - 1 ⋅ 4, & & \cr & = 5 - 1 ⋅ (24 - 5 ⋅ 5) = 5 ⋅ 5 - 1 ⋅ 24 & & \cr & = 5 ⋅ (53 - 2 ⋅ 24) - 1 ⋅ 24 = 5 ⋅ 53 - 11 ⋅ 24 & & \cr & = 5 ⋅ 53 - 11 ⋅ (77 - 1 ⋅ 53) = 16 ⋅ 53 - 11 ⋅ 77. & & }

To solve 53x + 77y = 22, we start with 53 ⋅ 16 + 77 ⋅ (-1) = 1. Multiplying by 22,

 53 ⋅ (16 ⋅ 22) + 77 ⋅ (-1 ⋅ 22) = 22,

and x = 352, y = -22 is one solution.

But if there is one solution, there are infinitely many! Remember that d = (a,b), so a∕d and b∕d are integers. Given one solution x = {x}_{0} and y = {y}_{0}, try substituting x = {x}_{0} + t ⋅ (b∕d) and y = {y}_{0} - t ⋅ (a∕d) for any integer t. Then

\eqalignno{ a({x}_{0} + t ⋅ (b∕d)) + b({x}_{0} - t ⋅ (a∕d)) & = a{x}_{0} + b{x}_{0} + t ⋅ (ab∕d)) + -t ⋅ (ba∕d)) & & \cr & = a{x}_{0} + b{x}_{0} = c. & & }

Actually, all integer solutions to ax + by = c are of the form

 x = {x}_{0} + t ⋅ (b∕d),\quad \text{and}\quad y = {y}_{0} - t ⋅ (a∕d),

where t is any integer, d = (a,b), and {x}_{0} and {y}_{0} are a solution pair.

Another example, consider solving 12x + 25y = 331. First we apply the Euclidian algorithm to compute (12,25) = 1:

\eqalignno{ 25 & = 2 ⋅ 12 + 1,\text{ and} & & \cr 12 & = 12 ⋅ 1 + 0. & & }

Substituting back,

\eqalignno{ 12 ⋅ (-2) + 25 ⋅ 1 & = 1,\text{ and}12 ⋅ (-662) + 25 ⋅ 331 & = 331. & & & & }

So we can generate any solution to 12x + 25y = 331 with the equations

\eqalignno{ x = -662 + 25t\quad \text{and}\quad y = 331 - 12t. & & }

Using these, we can find a “smaller” solution. Try making x non-negative with

\eqalignno{ - 662 + 25t & ≥ 0, & & \cr 25t & ≥ 662,\text{ thus} & & \cr t & > 26. & & }

Substituting t = 27,