Division Algorithm

Discrete Math · Axiom Academy

Every integer division produces a unique quotient and remainder. This fundamental theorem underlies modular arithmetic and number theory. The theorem has two parts: existence (such q and r always exist) and uniqueness (there's only one valid pair). On a number line, dividing a by b means finding how many "jumps" of size b we can make from 0 to reach or pass a , plus the leftover distance. Starting at 0, we can jump by 5 four times: 0 → 5 → 10 → 15 → 20 We land at 20, which is 3 units away from 23 So 23 = 5(4) + 3, giving us q = 4 and r = 3 3. Working with Negative Numbers The Division Algorithm works for negative values of a too, but the remainder r must still satisfy 0 ≤ r b . We need -23 = 5 q + r where 0 ≤ r < 5 Jumping backwards: 0 → -5 → -10 → -15 → -20 → -25 We overshoot to -25, then come forward 2 to reach -23 So -23 = 5(-5) + 2, giving us q = -5 and r = 2 We prove that q and r always exist by construction. Consider the set of all non-negative integers of the form a - bk : The set S is non-empty (we can choose k small enough that a - bk ≥ 0) By the Well-Ordering Principle, S has a smallest element, call it r Let q be the value of k that gives this minimum r Then a = bq + r by construction, and r ≥ 0 by definition of S We must show r b . If r ≥ b , then a - b ( q + 1) = r - b ≥ 0, contradicting minimality of r To prove uniqueness, suppose there are two representations: Subtracting the equations: b ( q 1 - q 2 ) = r 2 - r 1 This means b divides ( r 2 - r 1 )

This is the written version of the interactive lesson above. See the full Discrete Math course.