← 1.3contents1.5 →

1.4. divisors

We saw that a negative integer can be a divisor of another integer. However, when discussing the divisors of an integer we will often restrict ourselves to its positive divisors.

definition. For a nonzero integer $ a $, the divisors of $ a $ are of the positive integers that divide $ a $, ie, $$ \{ n \in \mathbb{Z} \mid n > 0 \text{ and } n \mid b \}. $$

Note that we do not define the set of divisors of $ 0 $ because every integer divides $ 0 $.

examples

  1. What are the divisors of $ 47 $?
    The divisors of $ 47 $ are $$ 1, 47 . $$
  2. What are the divisors of $ 48 $?
    The divisors of $ 48 $ are $$ 1, 2, 3, 4, 6, 8, 12, 16, 24, 48 . $$
  3. What are the divisors of $ 49 $?
    The divisors of $ 49 $ are $$ 1, 7, 49 . $$
  4. What are the divisors of $ 50 $?
    The divisors of $ 50 $ are $$ 1, 2, 5, 10, 25, 50 . $$
  5. What are the divisors of $ 51 $?
    The divisors of $ 51 $ are $$ 1, 3, 17, 51 . $$
  6. What are the divisors of ?

exercises

  1. If $ a $ and $ b $ are positive integers such that $ b \mid a $, prove that $ b \le a $.

    solution

    Since $ b \mid a $, there is an integer $ n $ such that $ a = b \cdot n $. Since both $ a $ and $ b $ are positive, then $ n $ must be as well, because if $ n $ were zero or negative, then multiplying by $ b $ would result in zero or a negative number, which is impossible. Therefore, we can be sure that $ 1 \le n $. Multiplying both sides of this inequality by the positive integer $ b $ results in $ b \le b \cdot n $, which can be rewritten as $ b \le a $.

  2. Write a divisors function that takes an integer input and returns the sorted array of its divisors. (Hint: use exercise #1)

    Some test values:

    • divisors(25) ~> [1, 5, 25]
    • divisors(27) ~> [1, 3, 9, 27]
    • divisors(29) ~> [1, 29]
    • divisors(30) ~> [1, 2, 3, 5, 6, 10, 15, 30]
    • divisors(32) ~> [1, 2, 4, 8, 16, 32]
    • divisors(34) ~> [1, 2, 17, 34]
    • divisors(36) ~> [1, 2, 3, 4, 6, 9, 12, 18, 36]
    solution
    module NumberTheory::Division
  def divisors(a)
    return if a == 0
    (1..a.abs).select { |b| divides(b, a) }
  end
end

  3. If $ a $ and $ b $ are positive integers such that $ a \mid b $ and $ b \mid a $, prove that $ a = b $. (Hint: use exercise #1)

    solution

    Since $ b \mid a $, the previous exercise implies that $ b \le a $. Similarly, since $ a \mid b $, the previous exercise implies that $ a \le b $. This is only possible if $ a $ and $ b $ are actually equal.

← 1.3contents1.5 →