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.
[
[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
-
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 counter-example.
-
If \( d \) divides either \( a \) or \( b \), prove that \( d \) divides their product \( ab \).
-
Disprove the converse of the previous exercise by producing a counter-example.