division algorithm

Long division from grade school always ends with a quotient and a leftover remainder: 17 divided by 5 is 3 with 2 to spare. The division algorithm is the precise promise that this always works and always gives exactly one answer — there is never ambiguity about the quotient and remainder.

The statement: given integers a and a positive integer b, there exist unique integers q (the quotient) and r (the remainder) such that a = b times q + r, with the remainder confined to 0 ≤ r < b. The remainder being smaller than the divisor, and nonnegative, is what pins down a single answer. For example 17 = 5 times 3 + 2, and no other choice keeps r in that range.

Despite its name it is a theorem, not a step-by-step recipe — the word algorithm is historical. A subtlety: with negative dividends you must still keep r nonnegative, so -17 divided by 5 gives q = -4 and r = 3, since -17 = 5 times (-4) + 3. This guaranteed remainder is the foundation of the Euclidean algorithm and the whole machinery of congruence and modular arithmetic.