← 1.5contentsa.1 →

1.6. greatest common divisor

pair of integers has a common divisor (since $ 1 $ divides every). And the set of divisors of a nonzero integer are bounded above byinteger. Therefore, every pair of integers (not both zero) has acommon divisor.

definition. The greatest common divisor of two integers (not both zero) is the largest positive integer that divides them both.

We write $ \gcd(a, b) $ for the greatest common divisor of $ a $ and $ b $.

examples

  1. What is the greatest common divisor of $ 30 $ and $ 42 $ ?
    The common divisors of $ 30 $ and $ 42 $ are $$ 1, 2, 3, 6 $$ so the greatest common divisor is $$ \gcd(30, 42) = 6. $$
  2. What is the greatest common divisor of $ 21 $ and $ 231 $ ?
    The common divisors of $ 21 $ and $ 231 $ are $$ 1, 3, 7, 21 $$ so the greatest common divisor is $$ \gcd(21, 231) = 21. $$
  3. What is the greatest common divisor of $ 130 $ and $ 2401 $ ?
    The common divisors of $ 130 $ and $ 2401 $ are $$ 1 $$ so the greatest common divisor is $$ \gcd(130, 2401) = 1. $$
  4. What is the greatest common divisor of and ?

exercises

  1. For a nonzero integer $ a $, prove that $ \gcd(a, 0) = \gcd(0, a) = |a| $.
    solution
    Since every integer divides $ 0 $, the common divisors of $ a $ and $ 0 $ are the divisors of $ a $. The largest positive divisor of $ a $ is $ |a| $, therefore $ \gcd(a, 0) = |a| $.
  2. If $ a = b q + r $ with $ b \ne 0 $, prove that $ \gcd(a, b) = \gcd(b, r) $.
    solution

    Let $ C_{a, b} $ be the common divisors of $ a, b $ and $ C_{b, r} $ the common divisors of $ b, r $. We will prove these sets are equal.

    First, we show that $ C_{b, r} $ is a subset of $ C_{a, b} $ by proving that every common divisor of $ b $ and $ r $ is also a divisor of $ a $. Let $ d $ be any element of $ C_{b, r} $. Since it is a common divisor of $ b, r $, we can write $ d = b m $ and $ d = r n $ for some integers $ m, n $. Substituting these equations into the original relation, we get $$ a = b q + r = (d m) q + (d n) = d(m q + n), $$ which indeed shows that $ d $ is a divisor of $ a $.

    Next, we show that $ C_{a, b} $ is a subset of $ C_{b, r} $ by proving that every common divisor of $ a, b $ is also a divisor of $ r $. Letting $ d $ be any element of $ C_{a, b} $, we can write $ a = d m $ and $ b = d n $ for some integers $ m, n $ since $ d $ is a divisor of both $ a $ and $ b $. Solving the original relation for $ r $ and substituting, we get $$ r = a - b q = (d m) - (d n) q = d (m - n q). $$ This shows that $ d $ is also a divisor of $ r $.

    Since $ C_{a, b} = C_{b, r} $, the maximum of $ C_{a, b} $ is equal to the maximum of $ C_{b, r} $. In other words, the greatest common divisor of $ a, b $ is equal to the greatest common divisor of $ b, r $.

← 1.5contentsa.1 →