← 1.1contents1.3 →

1.2. division with remainder

In the previous section, we wrote a naive loop to determine if an integer is divisible by another without proving that such a loop would terminate. Instead of proving that the loop we wrote will eventually terminate, in this section we consider division with remainder and prove a stronger result: that division of an integer by a nonzero integer results in a unique quotient and remainder.

division with remainder. For an integer $ a $ and a nonzero integer $ b $, there exist unique integers $ q $ and $ r $such that $ a = b \cdot q + r $ and $ 0 \le r < |b| $.

This is often called the division algorithm . In the output of the algorithm, the integer $ q $ is called the quotient and the integer $ r $ is called the remainder .

Case 1: when $ a $ is nonnegative. Consider the set $$ S = \{ a - b n \mid n \in \mathbb{Z} \} $$ consisting of all integers of the form $ a - b n $ where $ n $ is any integer. Now consider the subset $$ S_+ = \{ s \in S \mid s \ge 0 \} $$ of elements in $ S $ which are nonnegative.

Note that $ a $ is an element of $ S $ since $ a = a - b(0) $. And since $ a $ itself is nonnegative, it is in $ S_+$, which means that $ S_+ $ is nonempty. By the well-ordering principle, there is a smallest element of $ S_+ $. By definition, this smallest element is of the form $ r = a - b q $ for some integer $ q $.

We know that $ r $ is nonnegative, because it is an element in $ S_+ $. To complete the proof in this case, we need to show that $ r < |b| $ or equivalently that $ r - |b| $ is negative. This integer $ r - |b| $ is an element of $ S $ since it is equal to $ a - b (q \pm 1) $, depending on the sign of $ b $. However, it cannot be an element of $ S_+ $ since it is smaller than the smallest element $ r $. This is only possible if $ r - |b| $ is negative.

Case 2: $ a $ is negative. In this case, we know that $ -a $ is positive. Using the above, we can find unique integers $ Q $ and $ R $ such that $$ -a = bQ + R \quad \text{and} \quad 0 \le R < |b|. $$

If $ R = 0 $, we set $ r = 0 $ and $ q = -Q $, which gives $$ a = b(-Q) - 0 = bq + r. $$

Otherwise, we set $ r = -R + |b| $ and $ q = -Q - |b| / b $, which gives $$ a = b(-Q) - R = b(q + |b| / b) + (r - |b|) = bq + r. $$ Also, since $ R > 0 $, we know that $$ 0 < R < |b| \quad \longrightarrow \quad -|b| < -R < 0, $$ which implies that $$ 0 < -R + |b| < |b| \quad \longrightarrow \quad 0 < r < |b|. $$

examples

  1. What are the quotient and remainder when dividing $ 47 $ by $ 10$?
    The quotient is $ 4 $ and the remainder is $ 7 $ since $$ 47 = 10 (4) + 7 \quad \text{and} \quad 0 \le 7 < 10. $$
  2. What are the quotient and remainder when dividing $ 47 $ by $ -10$?
    The quotient is $ -4 $ and the remainder is $ 7 $ since $$ 47 = -10 (-4) + 7 \quad \text{and} \quad 0 \le 7 < 10. $$
  3. What are the quotient and remainder when dividing $ -47 $ by $ 10$?
    The quotient is $ -5 $ and the remainder is $ 3 $ since $$ -47 = 10 (-5) + 3 \quad \text{and} \quad 0 \le 3 < 10. $$
  4. What are the quotient and remainder when dividing $ -47 $ by $ -10$?
    The quotient is $ 5 $ and the remainder is $ 3 $ since $$ -47 = -10 (5) + 3 \quad \text{and} \quad 0 \le 3 < 10. $$
  5. What are the quotient and remainder when dividing by ?

exercises

  1. Write a naive div_rem function that takes two inputs (any integer, any nonzero integer) and returns a pair of integers consisting of the quotient and remainder resulting from dividing the first integer by the second. This function should only use addition, subtraction, multiplication, and comparison.

    Some test values:

    • div_rem(47, 10) = [4, 7]
    • div_rem(47, -10) = [-4, 7]
    • div_rem(-47, 10) = [-5, 3]
    • div_rem(-47, -10) = [5, 3]
    • div_rem(90, 10) = [9, 0]
    • div_rem(90, -10) = [-9, 0]
    • div_rem(-90, 10) = [-9, 0]
    • div_rem(-90, -10) = [9, 0]
    • div_rem(10, 47) = [0, 10]
    • div_rem(10, -47) = [0, 10]
    • div_rem(-10, 47) = [-1, 37]
    • div_rem(-10, -47) = [1, 37]
    • div_rem(0, 99) = [0, 0]
    • div_rem(0, -99) = [0, 0]
    solution
    module Naive
  def div_rem(a, b)
    raise ZeroDivisionError if b == 0
  
    if b < 0
      quotient, remainder = div_rem(a, -b)
      return [-quotient, remainder]
    end
  
    if a < 0
      quotient, remainder = div_rem(-a, b)
      return [-quotient, 0] if remainder == 0
      return [-quotient - 1, -remainder + b.abs]
    end
  
    quotient = 0
  
    until (remainder = a - quotient * b) < b.abs
      quotient += 1
    end
  
    [quotient, remainder]
  end
end
  2. If $ a $ is an integer and $ b $ is a nonzero integer, prove that $ b \mid a $ if and only if division of $ a $ by $ b $ yields a remainder of $ 0 $.
    solution

    Suppose that $ b \mid a $. Then $ a = b n $ for some integer $ n $, or equivalently that $ a = b n + 0 $. This satisfies the conditions for division with remainder, so we conclude that the remainder is equal to $ 0 $, since division with remainder yields a unique remainder.

    On the other hand, suppose that division with remainder gives a remainder of $ 0 $, ie, that $ a = b q + 0 $. Then $ a $ is a multiple of $ b $, hence $ b \mid a $.

← 1.1contents1.3 →