# division with remainder

In the divides function from the last section, we employed a while loop. The eventual termination of the loop depends on the following principle.

Archimedes' principle. For an integer $$a$$ and a nonzero integer $$b$$, there exists a multiple of $$b$$ which is greater than or equal to $$a$$.

This principle is equivalent to the division algorithm, which we will prove.

proposition 2 (division algorithm). For an integer $$a$$ and a nonzero integer $$b$$, there are unique integers $$q$$ and $$r$$ such that $$a = bq + r$$ and $$0 \le r < |b|.$$

Terminology:

• $$a$$ is called the dividend.
• $$b$$ is called the divisor.
• $$q$$ is called the quotient.
• $$r$$ is called the remainder.

Before proving the division algorithm, here are a few examples.

• Dividing $$71$$ by $$20$$ gives $$71 = 20(3) + 11$$
• Dividing $$71$$ by $$-20$$ gives $$71 = -20(-3) + 11$$
• Dividing $$-71$$ by $$20$$ gives $$-71 = 20(-4) + 9$$
• Dividing $$-71$$ by $$-20$$ gives $$-71 = -20(4) + 9$$

proof of division algorithm: If $$a \ge 0$$, consider the set $$S$$, consisting of integers of the form $$a - bn$$ where $$n$$ is an integer, ie, $S = { a - bn: n \in \mathbf{Z} }.$ The intersection of $$S$$ the with nonnegative integers is non-empty, since $$a$$ itself is nonnegative. By the well-ordering principle, there must be a unique smallest nonnegative element of $$S$$, say $$r = a - bq$$. Since $$r - |b|$$ is a smaller element of $$S$$, it must be negative, hence $$r < |b|$$.

If $$a < 0$$, then $$-a$$ is positive, which was proven above to be expressable as $$-a = bQ + R.$$ If $$R = 0$$, set $$q = -Q$$ and $$r = 0.$$ Otherwise, set $$r = -R + |b|$$ and $$q = -Q - |b| / b.$$ In either case, we have $a = -bQ - R = bq + r$ with $$0 \le r < |b|.$$

## in code

In most programming languages, the implementation of a division and remainder (modulus) operator likely will not match the specification given by the division algorithm: when the dividend or divisor is negative, it may result in a negative remainder.

In ruby, for example, integer division is floor division, so the quotient a / b is computed by rounding down the rational number $$a / b$$. Therefore, the sign of the remainder a % b is the same as the sign of the divisor b.

aba / ba % b
7120311
71-20-4-9
-7120-49
-71-203-11

In rust, on the other hand, integer division is truncation, so the quotient a / b is computed by rounding the rational number $$a / b$$ toward zero. Therefore, the sign of the remainder a % b is the same as the sign of the dividend a.

aba / ba % b
7120311
71-20-311
-7120-3-11
-71-203-11

exercise: Write a div_rem function that takes a dividend a and a nonzero divisor b as inputs, and outputs a quotient q and a remainder r satisifying the division algorithm.

The division algorithm itself gives the specifications to validate that div_rem is implemented correctly. Following is a test in ruby that asserts the properties from the division algorithm and its terminal output.

DIV_REM_TEST_INPUTS = [
[6723, 220],
[-2392, 183],
[788, -93],
[-5853, -11],
[46 * 82, 82],
]

class TestDivRem < Test::Unit::TestCase
def test_div_rem
DIV_REM_TEST_INPUTS.each do |(a, b)|
quo, rem = div_rem(a, b)

assert 0 <= rem
assert rem < b.abs
assert_equal a, b*quo + rem

puts "#{a} == #{b} * #{quo} + #{rem}"
end
end
end

6723 == 220 * 30 + 123
-2392 == 183 * -14 + 170
788 == -93 * -8 + 44
-5853 == -11 * 533 + 10
-3772 == 82 * 46 + 0

1 tests, 15 assertions, 0 failures, 0 errors


Click the expand button to see an implementation of div_rem in ruby.

## divisibility and remainders

The division algorithm is an extension of the idea of divisibility, as this proposition makes clear.

proposition 3. A nonzero integer $$b$$ divides an integer $$a$$ if and only if the division of $$a$$ by $$b$$ yields a remainder of $$0$$.

proof: If the division algorithm gives $$a = bq + r$$ with $$r = 0$$, then $$a = bq$$, which implies the $$b \mid a$$.

Conversely, if $$b \mid a$$, then $$a = bn$$ for some $$n$$. Since the division algorithm produces a unique quotient and remainder, it must be true that $$q = n$$ and $$r = 0$$.

## exercises

Compute by hand the quotient and remainder when dividing:

1. $$345$$ by $$14$$

2. $$-872$$ by $$77$$

3. $$7373$$ by $$-205$$

4. $$-762$$ by $$-11$$