Greatest Common Divisors

The greatest common divisor of two integers is the largest integer that is a divisor of both. For example, gcd(14, 6) = 2, and the gcd(-10, 15) = 5. The greatest common divisor is always positive (why?).

There are several methods for computing greatest common divisors. One is to factor both numbers into primes. Multiplying the primes that are common to both numbers gives the gcd. For example, to calculate gcd(396, 120), we factor 396 and 120 into primes, getting

396 = 2 × 2 × 3 × 3 × 11
120 = 2 × 2 × 2 × 3 × 5

The primes common to both 396 and 120 are 2, 2, 3. Therefore, gcd(396,120) = 2 × 2 × 3 = 12.

This method of factoring can be slow because, in general, factoring numbers is time consuming. Here is an easy and quick method of finding greatest common divisors. Given two integers a and b with a > b, subtract b from a and replace the larger number b by a - b. Repeat this process on the new pair. Continue repeating until both numbers are equal. This is then the gcd of a and b. For example, to find gcd(396, 120), we would have the following list of numbers

smaller number larger number difference
120 396 276
120 276 156
120 156 36
36 120 84
36 84 48
36 48 12
12 36 24
12 24 12
12 12 finished!

We ended with 12, so that is the gcd of 120 and 396. As you can see from this example, you may need to subtract the same number several times. On a TI-108 this process can be done very quickly because after doing a subtraction, hitting the equal sign again subtracts the number again. This method works because of a nice property of gcd: if a and b are integers, then gcd(a, b) = gcd(a - b, b). Therefore, each pair we write down has the same gcd as the previous pair, and so has the same gcd as the original pair.

Problem 1. Calculate the following greatest common divisors by both methods. Show all the steps you took to calculate the gcd.

  1. gcd(20, 75)
  2. gcd(495, 440)
  3. gcd(294, 98)
Problem 2. Calculate the following greatest common divisors by the repeated subtraction method. For one of the three, write down the pairs you got during the calculation only when the smallest number changes. In other words, don't write down the intermediate steps, as was done in the example above..
  1. gcd(1830, 10553)
  2. gcd(11211, 100900)
  3. gcd(13475, 23485)