Discrete Mathematics and Proof

The division algorithm

Dividing 389 by 14 gives 27 with 11 left over. Does every integer, negative ones included, split this way against every positive divisor, and in only one way?

You need

Divisibility as a relationDiscrete Mathematics and Proof Remainders and what they meanGrade 4

Unlocks

Congruence modulo n and its arithmeticDiscrete Mathematics and Proof Numbers in other basesDiscrete Mathematics and Proof

Where you are 8 in Introductory number theory

Logic, proof and discrete math6

Introductory number theory8

Divisibility as a relation Modular arithmetic7

The division algorithm

Numbers in other bases The Euclidean algorithm and coprime numbers ▾ Show all 8 (3 more)

Why this exists

Grade-school division already answers “how many times, and how much is left”: 389 \div 14 is 27 with 11 left over, because 389 = 14 \cdot 27 + 11 (Remainders and what they mean, The standard long division algorithm). A proof needs a statement that holds for every integer, negative ones included, and it needs the remainder to be one definite number, so that “the remainder of a on division by b” means something.

Divisibility asks a yes or no question: is a = bk for some integer k? The division algorithm says what happens when the answer is no. The proofs by cases in Proof by cases used the forms 3k, 3k + 1, 3k + 2 on the strength of this theorem, stated there without proof. This lesson proves it.

Definition

The division theorem. Let a be an integer and b a positive integer. Then there is exactly one pair of integers q and r with

a = bq + r \quad \text{and} \quad 0 \le r < b.

The number a is the dividend, b the divisor, q the quotient and r the remainder. The remainder is written a \bmod b, read “a mod b”. So 389 \bmod 14 = 11. The result is a theorem; the name “division algorithm” is traditional.

The floor of a real number x, written \lfloor x \rfloor, is the greatest integer that is at most x. So \lfloor 3.7 \rfloor = 3, \lfloor 5 \rfloor = 5 and \lfloor -7.8 \rfloor = -8.

Intuition

The multiples of b, namely \ldots, -2b, -b, 0, b, 2b, \ldots, sit b apart along the number line. They cut it into blocks, each running from one multiple bq up to, but not including, the next one bq + b. Every integer lies in exactly one block. The quotient q names the block, and the remainder r is how far a sits past the block’s left end, a distance from 0 to b - 1.

Figure 1The multiples of 6 cut the line into blocks of length 6. The integer -47 lies in the block that starts at 6(-8) = -48, one step in, so q = -8 and r = 1.

Take a = -47 and b = 6. The multiple of 6 just at or below -47 is -48 = 6(-8), so

-47 = 6(-8) + 1,

with q = -8 and r = 1. The equation -47 = 6(-7) + (-5) is also true; it is what you get by dividing 47 by 6 and negating everything. It does not give the quotient and remainder, because -5 is outside the range 0 \le r < 6. The range is the whole content of the theorem: without it, every integer q gives a true equation a = bq + (a - bq).

Results

1. The division theorem. For every integer a and every positive integer b there are unique integers q and r with a = bq + r and 0 \le r < b.

2. The quotient is a floor. The quotient is q = \lfloor a/b \rfloor, and so the remainder is a \bmod b = a - b \lfloor a/b \rfloor.

3. Remainder zero means divisible. b \mid a if and only if a \bmod b = 0.

4. The forms. For each positive integer b, every integer has exactly one of the forms bq, bq + 1, \ldots, bq + (b - 1) for some integer q. This is what licenses a proof that splits into b cases by remainder.

Why it is true

Result 1, existence. Proof. Fix the positive integer b. First we prove, by induction on a, that every integer a \ge 0 has a pair. For a = 0, take q = 0 and r = 0: then 0 = b \cdot 0 + 0 and 0 \le 0 < b.

Suppose a \ge 0 has a pair, a = bq + r with 0 \le r < b. Then a + 1 = bq + (r + 1). Since r is an integer below b, r + 1 \le b, and there are two cases. If r + 1 < b, the pair q, r + 1 works for a + 1. If r + 1 = b, then a + 1 = b(q + 1) + 0, and the pair q + 1, 0 works. Either way a + 1 has a pair, which completes the induction.

Now let a < 0. Then -a > 0, so by the first part -a = bq' + r' with 0 \le r' < b, and a = b(-q') - r'. If r' = 0, then a = b(-q') + 0 is a pair. If 0 < r' < b, then

a = b(-q' - 1) + (b - r'),

and 0 < b - r' < b, so this is a pair. Every integer has a pair. \square

A second route to existence takes the least member of the set of nonnegative numbers a - bq by the well-ordering principle; that is Strong induction and well-ordering, Exercise 17, for a \ge 0.

Result 1, uniqueness. Proof. Suppose a = bq + r and a = bq' + r', with 0 \le r < b and 0 \le r' < b. Subtracting, b(q - q') = r' - r. From the two ranges, -b < r' - r < b, so \lvert b(q - q') \rvert < b, and dividing by b > 0 gives \lvert q - q' \rvert < 1. The only integer with absolute value below 1 is 0, so q = q', and then r = r'. \square

The range does its work here: two numbers in a run of b consecutive integers differ by less than b, so they cannot differ by a nonzero multiple of b.

Result 2. Proof. Divide a = bq + r by b > 0: a/b = q + r/b. From 0 \le r < b we get 0 \le r/b < 1, so q \le a/b < q + 1. So q is an integer at most a/b and q + 1 is above it, which makes q the greatest integer at most a/b: q = \lfloor a/b \rfloor. \square

Result 3. Proof. If a \bmod b = 0, then a = bq, so b \mid a. Conversely, if b \mid a, then a = bk + 0 for an integer k, a pair with 0 \le 0 < b. By uniqueness it is the pair, so a \bmod b = 0. \square

Result 4. Proof. Write a = bq + r with 0 \le r < b. Then r is one of 0, 1, \ldots, b - 1, so a has the form bq + r. It has only one of the forms: if a = bq_1 + r_1 = bq_2 + r_2 with r_1 and r_2 both in the range, uniqueness gives r_1 = r_2. \square

Worked examples

Example 1

Quotients and remainders by the floor

Find the quotient and remainder of a on division by b = 33 for a = 2{,}000, a = 20 and a = -2{,}000.

Solution

By Result 2, q = \lfloor a/33 \rfloor and r = a - 33q.

For a = 2{,}000: 2{,}000/33 \approx 60.6, so q = 60 and r = 2{,}000 - 1{,}980 = 20.

For a = 20: 20/33 \approx 0.61, so q = 0 and r = 20. A dividend already in the range is its own remainder.

For a = -2{,}000: -2{,}000/33 \approx -60.6, and the greatest integer at most -60.6 is -61, not -60. So q = -61 and r = -2{,}000 + 2{,}013 = 13. Check: 33(-61) + 13 = -2{,}000, and 0 \le 13 < 33.

Example 2

Why the range leaves one pair

Find every pair of integers q, r with 389 = 14q + r, and show that only one of them has 0 \le r < 14.

Solution

One pair is known: 389 = 14 \cdot 27 + 11. If 389 = 14q + r is any pair, subtracting gives 14(27 - q) = r - 11, so r - 11 is a multiple of 14. Write r = 11 + 14t for an integer t; then q = 27 - t. Conversely every integer t gives a true equation, since 14(27 - t) + (11 + 14t) = 389. So the pairs are exactly

q = 27 - t, \quad r = 11 + 14t

for t \in \mathbb{Z}. For example, t = 1 gives 389 = 14 \cdot 26 + 25 and t = -1 gives 389 = 14 \cdot 28 - 3. Both are true, and both fail the range: 25 \ge 14 and -3 < 0. In general, 0 \le 11 + 14t < 14 means -11 \le 14t < 3, and the only multiple of 14 in that stretch is 0, so t = 0.

Example 3

A case split by four remainders

Prove that for every integer n, the remainder of n^4 on division by 16 is 0 or 1.

Solution

Proof. By Result 4 with b = 4, every integer n has one of the forms 4k, 4k + 1, 4k + 2, 4k + 3 for some integer k. Since 4k + 3 = 4(k + 1) - 1, the two odd forms can be handled together as 4m \pm 1 for an integer m.

Case n = 4k: n^4 = 256k^4 = 16(16k^4) + 0.

Case n = 4k + 2: n = 2(2k + 1), so n^4 = 16(2k + 1)^4 + 0.

Case n = 4m \pm 1: expanding by the binomial theorem,

\begin{aligned} n^4 &= 256m^4 \pm 256m^3 + 96m^2 \pm 16m + 1 \\ &= 16(16m^4 \pm 16m^3 + 6m^2 \pm m) + 1. \end{aligned}

In each case n^4 = 16Q + r with Q an integer and r equal to 0 or 1, inside the range 0 \le r < 16. By the uniqueness in Result 1, that r is the remainder. \square

So n^4 + 7 has remainder 7 or 8, and is never a multiple of 16.

Example 4

Negating the dividend

Let b be a positive integer and a an integer with quotient q and remainder r on division by b. Find the quotient and remainder of -a, then use the answer on -47 and -389.

Solution

From a = bq + r with 0 \le r < b, we get -a = b(-q) - r.

If r = 0, then -a = b(-q) + 0, which is in range: the quotient is -q and the remainder 0.

If 0 < r < b, borrow one more b:

-a = b(-q - 1) + (b - r).

Since 0 < r < b, the number b - r also lies strictly between 0 and b, so by uniqueness the quotient of -a is -q - 1 and its remainder is b - r.

For -47: 47 = 6 \cdot 7 + 5, so -47 = 6(-8) + 1, matching the figure. For -389: 389 = 14 \cdot 27 + 11, so -389 = 14(-28) + 3. Check: 14(-28) = -392, and -392 + 3 = -389.

Boundaries

The divisor must be positive. For b = 0 the range 0 \le r < 0 is empty, so no pair exists; for negative b the range 0 \le r < b is empty too. Some books, Levin’s among them, allow any nonzero b with the range 0 \le r < \lvert b \rvert: then 47 = (-6)(-7) + 5. This lesson fixes b > 0.
The range must hold exactly b consecutive integers. A range of b + 1 integers, such as 0 \le r \le b, loses uniqueness; a range of b - 1, such as 0 < r < b, loses existence (Exercises 15 and 16). “The remainder” in this course always means 0 \le r < b.
q and r must be integers. If q could be any real number, q = a/b and r = 0 would always work and the theorem would say nothing.

Where this goes next

Repeating the division, dividing the divisor by the remainder and so on, is the The Euclidean algorithm and coprime numbers. Grouping integers by their remainder leads to congruence and Modular arithmetic, where only the remainder matters. Dividing repeatedly by a base produces the digits of a number in that base (Numbers in other bases). And Long division is the place-by-place procedure that finds q and r for large numbers.

Exercises

Finding quotients and remainders

Find the quotient and remainder on division by b: (a) a = 500, b = 23; (b) a = -500, b = 23; (c) a = 23, b = 500; (d) a = -23, b = 500.
Find 1{,}000 \bmod 37 and (-1{,}000) \bmod 37.
Find \lfloor -73/8 \rfloor and -73 \bmod 8.
Use Result 2 to find the quotient and remainder of 5{,}555 and of -5{,}555 on division by 64.
Torsten numbers the days of the week Monday 0 through Sunday 6. Today is a Wednesday. What day of the week will it be 1{,}000 days from today, and what day was it 500 days ago?

The range makes the pair unique

Each equation is true. Say whether it gives the quotient and remainder of the left side on division by 7, and if not, give the correct pair: (a) 100 = 7 \cdot 13 + 9; (b) 100 = 7 \cdot 15 - 5; (c) -100 = 7(-15) + 5.
List every pair of integers q, r with 61 = 9q + r and \lvert r \rvert < 20. Which one gives the quotient and remainder?
An integer a has a \bmod 12 = 7. Find (a + 20) \bmod 12, (3a) \bmod 12 and (-a) \bmod 12.

Splitting by remainders

Prove that 7 \nmid n^2 + 1 for every integer n.
Prove that every integer of the form 6q + 5 also has the form 3m + 2, and show that the converse fails.
Prove that if an integer n is divisible by neither 2 nor 3, then n has the form 6q + 1 or 6q + 5.

Reasoning and proof

True or false for every integer a and positive integer b? Prove or give a counterexample. (a) (a \bmod b) \bmod b = a \bmod b. (b) \lfloor (a + b)/b \rfloor = \lfloor a/b \rfloor + 1. (c) (2a) \bmod b = 2(a \bmod b).
Prove that b \nmid a if and only if there is an integer q with bq < a < bq + b.
Prove the uniqueness in Result 1 without absolute values: assume q > q' and reach a contradiction.
Let c be any integer. Prove that for every integer a and positive integer b there is exactly one pair of integers q, r with a = bq + r and c \le r < c + b.
For which of these ranges does every integer a have exactly one pair with a = bq + r? (a) 0 \le r \le b; (b) 0 < r < b; (c) 1 \le r \le b; (d) -b < r \le 0.
Give a second proof of existence for negative a: show that a(1 - b) \ge 0, apply the case a \ge 0 to it, and recover a pair for a.
Prove that among any b consecutive integers, each of the remainders 0, 1, \ldots, b - 1 occurs exactly once.

Answers

(a) q = 21, r = 17: 500 = 23 \cdot 21 + 17. (b) q = -22, r = 6, since -506 + 6 = -500. (c) q = 0, r = 23. (d) q = -1, r = 477: -23 = 500(-1) + 477.
1{,}000 = 37 \cdot 27 + 1, so 1{,}000 \bmod 37 = 1, and by Example 4, (-1{,}000) \bmod 37 = 36, with -1{,}000 = 37(-28) + 36.
-73/8 = -9.125, so \lfloor -73/8 \rfloor = -10, and -73 \bmod 8 = -73 + 80 = 7.
5{,}555/64 \approx 86.8: q = 86, r = 5{,}555 - 5{,}504 = 51. -5{,}555/64 \approx -86.8: q = -87, r = -5{,}555 + 5{,}568 = 13.
Wednesday is day 2. 1{,}002 = 7 \cdot 143 + 1: day 1, a Tuesday. 2 - 500 = -498 = 7(-72) + 6: day 6, a Sunday.
(a) No, 9 \ge 7; the pair is q = 14, r = 2, since 100 = 7 \cdot 14 + 2. (b) No, -5 < 0; again q = 14, r = 2. (c) Yes: 7(-15) = -105 and 0 \le 5 < 7.
From 61 = 9 \cdot 6 + 7 the pairs are q = 6 - t, r = 7 + 9t, and \lvert r \rvert < 20 allows t = -2, -1, 0, 1: (8, -11), (7, -2), (6, 7), (5, 16). Only (6, 7) has 0 \le r < 9.
Write a = 12q + 7. Then a + 20 = 12(q + 2) + 3, 3a = 12(3q + 1) + 9 and -a = 12(-q - 1) + 5, all in range, so the answers are 3, 9 and 5.
Split n into 7k, 7k \pm 1, 7k \pm 2, 7k \pm 3 (since 7k + 4 = 7(k + 1) - 3, and so on). Then n^2 + 1 is 7(7k^2) + 1, 7(7k^2 \pm 2k) + 2, 7(7k^2 \pm 4k) + 5 or 7(7k^2 \pm 6k + 1) + 3. The remainders are 1, 2, 5, 3, never 0, so by Result 3 7 \nmid n^2 + 1.
6q + 5 = 3(2q + 1) + 2, so m = 2q + 1. The converse fails for 2 = 3 \cdot 0 + 2: on division by 6, 2 = 6 \cdot 0 + 2, so by uniqueness 2 is not of the form 6q + 5.
Write n = 6q + r with 0 \le r \le 5. Then r = 0, 2, 4 give 6q, 2(3q + 1), 2(3q + 2), all even, and r = 3 gives 3(2q + 1). Only r = 1 and r = 5 remain.
(a) True: r = a \bmod b satisfies r = b \cdot 0 + r with 0 \le r < b, so r \bmod b = r. (b) True: a + b = b(q + 1) + r, so its quotient is q + 1. (c) False: a = 5, b = 6 gives 10 \bmod 6 = 4, but 2(5 \bmod 6) = 10.
If b \nmid a, then r = a \bmod b \ne 0 by Result 3, so 0 < r < b and bq < a < bq + b. Conversely, if bq < a < bq + b, then r = a - bq satisfies 0 < r < b; by uniqueness it is the remainder, which is not 0, so b \nmid a.
From bq + r = bq' + r', r' - r = b(q - q'). If q > q', then q - q' \ge 1, so r' - r \ge b. But r' < b and r \ge 0 give r' - r < b, a contradiction. By symmetry q < q' fails too, so q = q' and r = r'.
Apply Result 1 to a - c: a - c = bq + s with 0 \le s < b. Then a = bq + (s + c) with c \le s + c < c + b. If a = bq + r = bq' + r' with both in the range, then r - c and r' - c are remainders of a - c, so they are equal by uniqueness, and q = q'.
(c) and (d) work: both are ranges of b consecutive integers (c = 1 and c = 1 - b in Exercise 15). (a) fails uniqueness: b = b \cdot 1 + 0 = b \cdot 0 + b. (b) fails existence: for a = b, every r = b - bq is a multiple of b, and none lies strictly between 0 and b.
Since a < 0 and 1 - b \le 0, a(1 - b) \ge 0. So a(1 - b) = bq + r with 0 \le r < b. Adding ab: a = bq + r + ab = b(q + a) + r, a pair for a.
If m + i and m + j, with 0 \le i < j \le b - 1, had the same remainder s, then j - i = b(q_2 - q_1) would be a positive multiple of b below b, which is impossible. So the b integers have b different remainders, drawn from the b values 0, \ldots, b - 1, and each value occurs exactly once.