1.1. divisors

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

definition. For a nonzero integer $ a $, the set of divisors of $ a $ consists of the positive integers that divide $ a $.


Note that the set of divisors of $ 0 $ is undefined because every integer divides $ 0 $.

examples

  1. What are the divisors of $ 100 $?
    The divisors of $ 100 $ are $$ 1, 2, 4, 5, 10, 20, 25, 50, 100 . $$
  2. What are the divisors of $ 42 $?
    The divisors of $ 42 $ are $$ 1, 2, 3, 6, 7, 14, 21, 42 . $$
  3. What are the divisors of ?

exercises

  1. In the previous section, we wrote a naive divides function, which is non-performant. Most programming languages have an efficient built-in mechanism for computing divisibility using the modulus operator % (or something equivalent). Explicitly, an integer a is divisible by a nonzero integer b if and only if b % a == 0. Use this to write an improved divides function. It should pass all the same tests as the naive one.
    solution
    module Ebe
      def divides(b, a)
        b != 0 && a % b == 0
      end
    end
  2. 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 $.

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

    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 Ebe
      def divisors(a)
        return if a == 0
        (1..a.abs).select { |b| Ebe.divides(b, a) }
      end
    end
  4. If $ a $ and $ b $ are positive integers such that $ a \mid b $ and $ b \mid a $, prove that $ a = b $. (Hint: use exercise #2)

    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.