# divisibility

This study of integers begins with the notion of divisibility: whether the division of two integers results in an integer. Because of the volatile nature of division, we frame this question in terms of integer multiplication.

A nonzero integer $$b$$ divides an integer $$a$$ if there exists some integer $$n$$ such that $$a = bn$$.

Here are a few examples:

• 15 divides 45 since $$45 = 15 \cdot 3$$
• 9 divides 45 since $$45 = 9 \cdot 5$$
• 10 does not divide 45 since 45 is between $$40 = 10 \cdot 4$$ and $$50 = 10 \cdot 5$$

The above definition is synonymous with saying that $$b$$ may be expressed as a multiple of $$a$$. In fact, the following statements are equivalent and mean that $$a$$ is can be expressed as $$bn$$.

• $$b$$ divides $$a$$
• $$b$$ is a divisor of $$a$$
• $$a$$ is divisible by $$b$$
• $$a$$ is a multiple of $$b$$

The notation for this concept is $$b \mid a$$, which reads "$$b$$ divides $$a$$". Using this notation, the examples above become:

• $$15 \mid 45$$ since $$45 = 15 \cdot 3$$
• $$9 \mid 45$$ since $$45 = 9 \cdot 5$$
• $$10 \nmid 45$$ since $$10 \cdot 4 < 45 < 10 \cdot 5$$

Be careful! This notation may sometimes be confused with the division operation. If you see $$15 / 45$$, it is the operation that returns the rational number $$1/3$$. If you see $$15 \mid 45$$, it is the statement that $$45$$ is divisible by $$15$$, ie, that $$45 / 15$$ is an integer.

exercise. Using only addition, multiplication, and comparison, write a divides function that takes as input two positive integers b and a and returns true if b divides a and false otherwise.

With such a divides? function in ruby, the following code should yield the terminal output below.

  [
[25, 0],
[31, 432],
[87, 87*58],
[99, 9900],
[9900, 99],
].each do |(b, a)|
if divides?(b, a)
puts "#{b} divides #{a}"
else
puts "#{b} does not divide #{a}"
end
end

25 divides 0
31 does not divide 432
87 divides 5046
99 divides 9900
9900 does not divide 99


Click the button below to show an implementation of a simple divides? function in ruby.

## linear combinations

An integer linear combination of integers $$a$$ and $$b$$ is an integer of the form $$ax + by$$ where $$x$$ and $$y$$ are integers.

For example, 11 through 15 can all be expressed as linear combinations of 5 and 6. Here are two examples of each.

\begin{align} 5(1) + 6(1) &= 11 = 5(7) + 6(-4) \\ 5(0) + 6(2) &= 12 = 5(6) + 6(-3) \\ 5(-1) + 6(3) &= 13 = 5(5) + 6(-2) \\ 5(-2) + 6(4) &= 14 = 5(4) + 6(-1) \\ 5(-3) + 6(5) &= 15 = 5(3) + 6(0) \\ \end{align}

The following proposition about integer linear combinations will be used often.

proposition 1. If $$d$$ is a common divisor of $$a$$ and $$b$$, then $$d$$ divides any integer linear combination of $$a$$ and $$b$$.

proof: Suppose that $$d$$ divides $$a$$ and $$b$$. By definition, there exist integers $$m, n$$ such that $$a = dm$$ and $$b = dn$$. Let $$c = ax + by$$ be an integer linear combination of $$a$$ and $$b$$. For any linear combination $$ax + by$$, $ax + by = (dm)x + (dn)y = d(mx + ny).$ Since $$mx + ny$$ is an integer, the linear combination is divisible by $$d$$.

## exercises

1. Prove that any nonzero integer divides 0.

2. Prove that 1 and -1 divide any integer.

3. Prove that any nonzero integer divides itself.

4. If $$a$$ and $$b$$ are positive integers and $$b$$ divides $$a$$, prove that $$b \le a$$.

5. Prove that two positive integers that divide each other must be equal.

6. Prove that the divides relation is transitive: if $$c \mid b$$ and $$b \mid a$$, prove that $$c \mid a$$.

7. If $$d$$ divides both $$a$$ and $$b$$, prove that $$d$$ divides their sum $$a + b$$.

8. Disprove the converse of the previous exercise by producing a counter-example.

9. If $$d$$ divides either $$a$$ or $$b$$, prove that $$d$$ divides their product $$ab$$.

10. Disprove the converse of the previous exercise by producing a counter-example.