Division Algorithm — Definition, Formula & Example
The division algorithm is the theorem that says dividing any integer by a positive integer always gives exactly one integer quotient and one remainder. The quotient may be negative. The remainder is never negative and is always smaller than the divisor.
For all integers and with , there exist unique integers and such that and . Here . A common extension allows any and requires . Despite its name, the statement is a theorem (existence and uniqueness), not a step-by-step procedure.
Key Formula
Where:
- = the dividend, any integer
- = the divisor, a positive integer
- = the quotient, an integer (can be negative)
- = the remainder, an integer with 0 ≤ r < b
Worked Example
Problem: Use the division algorithm to find the quotient q and remainder r when a = -17 is divided by b = 5.
Step 1: The quotient is the floor of a/b, which is the greatest integer less than or equal to -3.4. That integer is -4, not -3, because -3 is greater than -3.4.
Step 2: Solve a = bq + r for the remainder.
Step 3: Check both conditions. The equation holds, and the remainder satisfies 0 ≤ 3 < 5.
Answer: q = -4 and r = 3, so -17 = 5(-4) + 3.
Why It Matters
The Euclidean algorithm for computing greatest common divisors is just the division algorithm applied repeatedly. In an introductory number theory or discrete math course, the theorem also underlies modular arithmetic. It explains why every integer is congruent mod b to exactly one of 0, 1, ..., b − 1, so the remainders form the residue classes of an equivalence relation.
Common Mistakes
Mistake: Writing -17 = 5(-3) + (-2) and calling -2 the remainder, because a calculator truncates -3.4 toward zero.
Correction: The equation is true, but -2 breaks the condition 0 ≤ r < b. Round the quotient down (take the floor), not toward zero. That gives q = -4 and r = 3.
