This study of integers begins with the notion of divisibility, whether the division of two integers results in an integer. Since division does not always yield a result at all, let alone an integer result, we frame this question in terms of multiplication.
definition. Given two integers $ a, b $, we say that $ b $ divides $ a $ if there is some integer $ n $ for which $ a = b \cdot n $. If $ b $ divides $ a $, we write $ b \mid a $. If $ b $ does not divide $ a $, we write $b \nmid a $.
The following statements are equivalent ways of describing that $ b \mid a $.
- $ b $ divides $ a $
- $ b $ is a divisor of $ a $
- $ a $ is divisible by $ b $
- $ a $ is a multiple of $ b $
- Does $ 15 $ divide $ 45 $?yes. $ 15 \mid 45 $ since $ 45 = 15 \cdot 3 $. In other words,
- $ 15 $ divides $ 45 $
- $ 15 $ is a divisor of $ 45 $
- $ 45 $ is divisible by $ 15 $
- $ 45 $ is a multiple of $ 15 $
- Does $ 10 $ divide $ 45 $?no. $ 10 \nmid 45 $ since $ 45 $ is strictly between $ 10 \cdot 4 $ and $ 10 \cdot 5 $, which shows that $ 45 = 10 \cdot n $ is impossible.
- $ 10 $ does not divide $ 45 $
- $ 10 $ is not a divisor of $ 45 $
- $ 45 $ is not divisible by $ 10 $
- $ 45 $ is not a multiple of $ 10 $
This notation $ a \mid b $ is sometimes confused with notation for the division operation. If you see $ 15 / 45 $, it is the division 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.
- Write a naive
dividesfunction that takes two integer inputs and returns
trueif the first divides the second and returns
falseotherwise. This naive function should only use addition, subtraction, multiplication, and comparison.
Some test values:
divides(15, 45) ~> true
divides(-15, 45) ~> true
divides(15, -45) ~> true
divides(-15, -45) ~> true
divides(10, 45) ~> false
divides(-10, 45) ~> false
divides(10, -45) ~> false
divides(-10, -45) ~> false
divides(7, 0) ~> true
divides(7, 7) ~> true
divides(7, -7) ~> true
divides(1, 7) ~> true
divides(-1, 7) ~> true
divides(0, 7) ~> false
module Naive def divides(b, a) return false if b == 0 multiple = 0 direction = a * b < 0 ? -1 : 1 while multiple.abs < a.abs multiple += direction * b end multiple == a end end
Prove that every nonzero integer divides 0.solution
For any nonzero integer $ b $, we can express $ 0 $ as $ 0 = b \cdot 0 $, which proves that $ b \mid 0 $.
Prove that every integer is divisible by both $ 1 $ and $ -1 $.solution
Let $ a $ be any integer. We can express $ a $ as $ a = 1 \cdot a $, which shows that $ 1 \mid a $. We can also express $ a $ as $ a = -1 \cdot (-a) $, which shows that $ -1 \mid a $.
Prove that every nonzero integer divides itself.solution
For any nonzero integer $ a $, we can express $ a $ as $ a = a \cdot 1 $, which shows that $ a \mid a $.
If $ b \mid a $, prove that $ -b \mid a $ and $ b \mid -a $.solution
Since $ b \mid a $, there is an integer $ n $ such that $ a = b \cdot n $. Then $$ a = (-b) \cdot (-n) \quad \implies \quad -b \mid a $$ and $$ -a = b \cdot (-n) \quad \implies \quad b \mid -a . $$
Prove that the "divides" relation is transitive. In other words, if $ c \mid b $ and $ b \mid a $, prove that $ c \mid a $.solution
The first assumption, that $ c \mid b $, means that we can write $ b = c \cdot m $ for some integer $ m $. The second assumption, that $ b \mid a $, means that we can write $ a = b \cdot n $ for some integer $ n $. Substituting the first equation in for $ b $ in the second equation yields \[ a = (c \cdot m) \cdot n \quad \implies \quad a = c \cdot (m \cdot n). \] Since we have expressed $ a $ as an integer multiple of $ c $, we conclude that $ c \mid a $.