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