Advanced High-School Mathematics

56 CHAPTER 2 Discrete Mathematics

2.1.1 The division algorithm

Very early on, students learn the arithmetic of integers, namely, that
of addition, subtraction, multiplication, and division. In particular,
students learn (in about the fifth or sixth grade) that a positive integer
acan be divided into a non-negative integerb, resulting in aquotient
qand a remainderr:

b=qa+r, 0 ≤r < a.

For instance, the following division of 508 by 28 should serve as an
ample reminder.

18

28 | 508

28

228

224

4

In this case the quotient is 18 and the remainder is 4:

508 = 18·28 + 4.

The fact that the above is always possible is actually atheorem:

Theorem. (Division Algorithm)Let a, b ∈Z, where a > 0 , b ≥ 0.
Then there existuniqueintegersqandr such that

b=qa+r, where 0 ≤r < a.

Proof. LetSbe the following subset of the setZof integers:

S = {b−xa|x∈Zandb−xa≥ 0 }.