← contents1.2 →

1.1. divisibility

The study of division 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 $

examples

  1. Does $ 15 $ divide $ 45 $?
    yes. $ 15 \mid 45 $ since $ 45 = 15 \cdot 3 $.
    • $ 15 $ divides $ 45 $
    • $ 15 $ is a divisor of $ 45 $
    • $ 45 $ is divisible by $ 15 $
    • $ 45 $ is a multiple of $ 15 $
  2. Does $ 10 $ divide $ 45 $?
    no. $ 10 \nmid 45 $ since $ 45 $ is strictly between $ 10 \cdot 4 $ and $ 10 \cdot 5 $.
    • $ 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 $
  3. Does divide ?

careful!

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.

exercises

  1. Write a naive divides function that takes two integer inputs and returns true if the first divides the second and returns false otherwise. 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
    solution
    module NumberTheory::Naive
  def divides(b, a)
    return false if b == 0
    return divides(-b, a) if b < 0
    return divides(b, -a) if a < 0
  
    multiple = 0
  
    while multiple < a
      multiple += b
    end
  
    multiple == a
  end
end

  2. 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 $.

  3. 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 $.

  4. 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 $.

  5. 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 . $$

  6. 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 $.

← contents1.2 →