Mathematics for the liberal arts (2013)
Part II. TWO PILLARS OF MATHEMATICS
Chapter 5. NUMBER THEORY
5.4 Greatest Common Divisors
Definitions and Examples
Definition. Let a and b be integers, not both 0. The greatest common divisor (gcd) of a and b is an integer d that satisfies the following two conditions.
i. d | a and d | b, i.e., d is a common divisor of a and b.
ii. If c | a and c | b, then c ≤ d, i.e., of all common divisors, d is the largest.
We will write the gcd of a and b as gcd (a, b).
EXAMPLE 5.9
Find the greatest common divisors.
(a) gcd(15, 12)
(b) gcd(37, 64)
(c) gcd(– 14, 49)
(d) gcd(100, 1000)
(e) gcd(0,1203)
Solution: For (a), let us list all the divisors of 12 and 15. The set of divisors of 12 is {±1, ±2, ±3, ±4, ±6, ±12}, and the set of divisors of 15 is {±1, ±3, ±5, ±15}. From this, we see that the greatest common divisor is 3.
(b) Check that 37 cannot be factored into smaller numbers, and 64 is a power of 2. Since they have no common factors, the highest common divisor must be 1; therefore gcd(37, 64) = 1.
(c) This one is easy. Spend a moment to convince yourself that gcd(– 14, 49) = 7.
(d) Since 100|1000, we have gcd(100,1000) = 100.
(e) Since 1203|1203 and 1203|0, the greatest common divisor of 1203 and 0 is 1203.
Note, for future use, that the last argument generalizes: gcd(0, a) = a for any positive integer a. This is important in the following discussion.
Computing GCDs: The Euclidean Algorithm
How do we find gcd’s? You may have learned a method that involves finding the prime factorizations of a and b. We will take a look at that method later, but now we examine another method, one that goes all the way back to Euclid. In fact, this method is called the Euclidean Algorithm. It is based on the next theorem.
Let a and b be integers, not both 0. If a = bq + r, then gcd(a, b) = gcd(b, r).
Proof. We will show that the set of common divisors of a and b is identical to the set of common divisors of b and r. This implies that the greatest common divisor of a and b is equal to the greatest common divisor of b and r.
First, suppose that x is a divisor of both a and b. We want to show that x | b and x | r. We already know that x | b, so we need only show that x | r. Since x | a and x | b, there are integers c and d such that xc = a and xd = b. Using these and a = bq + r, we have
So r = x(c – dq); hence x | r. Therefore x is a common divisor of b and r.
Finally, suppose that y is a common divisor of b and r. We need only show that y is a common divisor of a and r, i.e., that y | a. We can use the properties of divisibility from Section 5.2. Since y divides b, then y divides every multiple of b. So, in our case, y divides bq. From Section 5.2 we also know that, if y divides two numbers, then y divides their sum. In our case, y | bq and y | r, so y | (bq + r), i.e., y | a. This completes our proof.
EXAMPLE 5.10
Find gcd(116,34).
Solution: We will use the last theorem to find the gcd, with a = 116 and b = 34. What are q and r? By the Division Theorem of Section 5.2, the quotient and remainder work. (That is of course why we call them q and r.) So let us divide 116 by 34:
Hence the last theorem tells us that gcd(116, 34) = gcd(34,14). We can repeat this argument:
Finally gcd(2,0) = 2. Putting this all together, gcd(116, 34) = 2.
This method is called the Euclidean Algorithm.
The Euclidean Algorithm. Let a and b be positive integers. Define integers q1,…, qt and r1,…, rt by successive divisions:
Then gcd(a, b) = rt. In other words, keep on dividing until the remainder is 0. The gcd is the last nonzero remainder.
EXAMPLE 5.11
Find gcd(93,37).
Solution:
So gcd(93, 37) = 1.
Why does the Euclidean Algorithm work? It is simply the gcd relation applied over and over again. In the notation of the algorithm,
Why is the Euclidean Algorithm important? Because it is fast. The other popular method of finding gcd’s is based on factoring numbers, which is slow. But division is fast. The difference in speed becomes evident when computers try to find gcd’s of very large numbers. The computers available to Euclid were of course cruder than ours, but the problem of finding fast ways to do computations is very old.
EXERCISES
5.14 Find the gcd’s.
a) gcd(11, 22)
b) gcd(12,32)
c) gcd(314,159)
d) gcd(4144,7696)
e) gcd(480097,48)
f) gcd(480099,48)
5.15 Let a = bx + 1. Show that gcd(a, b) = 1. (Hint: run the Euclidean Algorithm.)
5.16 In the definition of greatest common divisor, we insist that a and b cannot both be 0. Why do you think this condition is there?
The rest of the exercises concern least common multiples. The least common multiple of integers a and b, written lcm(a, b), is the smallest positive integer d such that both a and b divide d. It is denoted by lcm(a, b).
5.17 Fill in the table below.
5.18 Least common multiples arise in the handling of different calendars. This is why the Chinese and the Mayans were masters of the 1cm.
a) Suppose we have two calendars: a solar calendar with 365 days, and a lunar calendar of 30 days. Suppose that today is June 5 and day 23 of the lunar calendar. How long would it take before we again have the next day 23 of the lunar calendar on June 5? (Ignore leap days.)
b) The Mayans used two different calendars, the 260-day almanac and a 365-day year. The time it took to cycle both calendars, to come around to the same date in both, was called the “calendar round.” How long was the calendar round?
5.19 There is a formula relating least common multiples and greatest common divisors. See if you can find it. (Hint: look for a pattern in the table above.)
5.20 Suppose that we have a pool table divided into 24 = 4 × 6 squares (Figure 5.2). We start a ball from the lower left, aiming it to cross each little square on its diagonal. The ball continues, perhaps bouncing off some sides, until it hits a comer, as in the figure. This problem asks you to explore similar tables, to find some patterns. In the process, you will fill in the table below.
Figure 5.2 A number-theoretic pool table.
a) The second column of the table is for the number of little squares the ball crosses before ending in a comer. You can check that this number is 12 for the 4 × 6 table. Fill in this column, for every row but the last. Try to find the pattern, then use it to fill in the value for the last row.
b) The third column of the table is for the comer the ball ends up in. See if you can fill this column. [Hint: consider first when it ends up left or right (using the number of little squares crossed), then whether it ends up top or bottom.]
c) The fourth column of the table is for the number of sides the ball hits, including the starting and ending comers. See if you can fill this column. (Hint: first consider how many times it crosses between left and right, then top and bottom.)
