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 thequotientand the integer $ r $ is called theremainder.

**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

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

## exercises

- 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`

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