The Division Algorithm

Number Theory · Axiom Academy

A foundational theorem in number theory that guarantees unique quotients and remainders 1. The Division Algorithm Statement Let a be an integer and b be a positive integer. Then there exist unique integers q (quotient) and r (remainder) such that: The beauty of this theorem lies in two parts: Existence: Such integers q and r always exist Uniqueness: These integers q and r are the only ones satisfying both conditions Let a = 23 and b = 5. The Division Algorithm guarantees: Here q = 4 (quotient) and r = 3 (remainder), with 0 ≤ 3 < 5. We prove that for any integers a and positive integer b, there exist integers q and r satisfying the Division Algorithm. Step 1: Show that S is non-empty and contains at least one non-negative integer. If a ≥ 0, choose k = 0, giving a - b(0) = a ≥ 0, so a ∈ S If a < 0, choose k = a (which is negative), then a - ba = a(1 - b) ≥ 0 since a < 0 and (1 - b) ≤ 0 Step 2: Apply the Well-Ordering Principle. Since S is a non-empty set of non-negative integers, by the Well-Ordering Principle, S has a smallest element. Call this smallest element r , and let it correspond to some integer q : By definition of S, we have r ≥ 0 Suppose r ≥ b. Then r - b ≥ 0, and: This means (r - b) ∈ S, but r - b < r, contradicting the fact that r is the smallest element of S. Conclusion: We have found integers q and r such that a = bq + r with 0 ≤ r < b. ∎

This is the written version of the interactive lesson above. See the full Number Theory course.