← 1.4contents1.6 →

1.5. common divisors

this section we discuss the notion of two integers having a common divisor.

definition. A common divisor of two integers is an integer that divides them both. The common divisors of 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

  1. 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 . $$
  2. 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 . $$
  3. 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 . $$
  4. What are the common divisors of and ?

exercises

  1. 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
  2. If $ d $ is a common divisor of $ a $ and $ b $, prove that $ d $ divides the sum $ a + b $.
    solution
    As 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) $.
  3. 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 $.
    solution
    Let $ 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.
  4. If $ d $ is a common divisor of $ a $ and $ b $, prove that $ d $ divides the difference $ a - b $.
    solution
    As 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) $.
  5. 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 $.
    solution
    Let $ 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.
← 1.4contents1.6 →