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 integersb
anda
and returnstrue
ifb
dividesa
andfalse
otherwise.
With such a divides?
function in ruby, the following code should yield the
terminal output below.
DIVIDES_TEST_INPUTS = [
[25, 0],
[31, 432],
[87, 87*58],
[99, 9900],
[9900, 99],
]
DIVIDES_TEST_INPUTS.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

Prove that any nonzero integer divides 0.

Prove that 1 and 1 divide any integer.

Prove that any nonzero integer divides itself.

If \( a \) and \( b \) are positive integers and \( b \) divides \( a \), prove that \( b \le a \).

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

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

If \( d \) divides both \( a \) and \( b \), prove that \( d \) divides their sum \( a + b \).

Disprove the converse of the previous exercise by producing a counterexample.

If \( d \) divides either \( a \) or \( b \), prove that \( d \) divides their product \( ab \).

Disprove the converse of the previous exercise by producing a counterexample.