definition.Acommon divisorof two integers is an integer that divides them both. Thecommon divisorsof two integers (not both zero) are the positive integers that divide both them both.Since every integer divides $ 0 $, the common divisors of a nonzero integer $ a $ and $ 0 $ is equal to the divisors of $ a $.

## examples

- What are the common divisors of $ 30 $ and $ 42 $?The divisors of $ 30 $ are $$ 1, 2, 3, 5, 6, 10, 15, 30 . $$ The divisors of $ 42 $ are $$ 1, 2, 3, 6, 7, 14, 21, 42 . $$ The common divisors of $ 30 $ and $ 42 $ are $$ 1, 2, 3, 6 . $$
- What are the common divisors of $ 21 $ and $ 231 $?The divisors of $ 21 $ are $$ 1, 3, 7, 21 . $$ The divisors of $ 231 $ are $$ 1, 3, 7, 11, 21, 33, 77, 231 . $$ The common divisors of $ 21 $ and $ 231 $ are $$ 1, 3, 7, 21 . $$
- What are the common divisors of $ 130 $ and $ 2401 $?The divisors of $ 130 $ are $$ 1, 2, 5, 10, 13, 26, 65, 130 . $$ The divisors of $ 2401 $ are $$ 1, 7, 49, 343, 2401 . $$ The common divisors of $ 130 $ and $ 2401 $ are $$ 1 . $$

## exercises

- Write a
`common_divisors`

function that takes two integer inputs (not both zero) and returns the sorted array of their common divisors.Some test values:

`common_divisors(0, 25) ~> [1, 5, 25]`

`common_divisors(25, 0) ~> [1, 5, 25]`

`common_divisors(25, 30) ~> [1, 5]`

`common_divisors(23, 30) ~> [1]`

`common_divisors(30, 90) ~> [1, 2, 3, 5, 6, 10, 15, 30]`

`common_divisors(50, 70) ~> [1, 2, 5, 10]`

`common_divisors(11, 13) ~> [1]`

`common_divisors(12, 14) ~> [1, 2]`

solution`module NumberTheory::Division def common_divisors(a, b) return divisors(a) if b == 0 return divisors(b) if a == 0 upper = [a.abs, b.abs].min (1..upper).select { |d| divides(d, a) && divides(d, b) } end end`

- If $ d $ is a common divisor of $ a $ and $ b $,
prove that $ d $ divides the sum $ a + b $.solutionAs a common divisor, we know that $ d \mid a $ and $ d \mid b $. Therefore we can write $ a = d \cdot m $ and $ b = d \cdot n $ for some integers $ m $ and $ n $. The sum $ a + b $ can then be expressed as $$ a + b = (d \cdot m) + (d \cdot n) = d \cdot (m + n), $$ which shows that $ d \mid (a + b) $.
- Disprove the converse of the previous exercise by finding a counterexample.
In other words, find three integer $ a, b, d $ such that $ d $ divides the
sum $ a + b $, but where $ d $ is not a common divisor of $ a $ and $ b $.solutionLet $ a = 13 $ and $ b = 7 $. The sum $ a + b = 20 $ is divisible by $ d = 5 $, but this $ d $ is not a divisor of either $ a $ or $ b $, therefore not a common divisor.
- If $ d $ is a common divisor of $ a $ and $ b $,
prove that $ d $ divides the difference $ a - b $.solutionAs a common divisor, we know that $ d \mid a $ and $ d \mid b $. Therefore we can write $ a = d \cdot m $ and $ b = d \cdot n $ for some integers $ m $ and $ n $. The difference $ a - b $ can then be expressed as $$ a - b = (d \cdot m) - (d \cdot n) = d \cdot (m - n), $$ which shows that $ d \mid (a - b) $.
- Disprove the converse of the previous exercise by finding a counterexample.
In other words, find three integer $ a, b, d $ such that $ d $ divides the
sum $ a + b $, but where $ d $ is not a common divisor of $ a $ and $ b $.solutionLet $ a = 13 $ and $ b = 7 $. The difference $ a - b = 6 $ is divisible by $ d = 6 $, but this $ d $ is not a divisor of either $ a $ or $ b $, therefore not a common divisor.