definition.Thegreatest common divisorof 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

- 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. $$
- 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. $$
- 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. $$

## exercises

- For a nonzero integer $ a $, prove that $ \gcd(a, 0) = \gcd(0, a) = |a| $.solutionSince 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| $.
- 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 $.