Course contentsShow
← Mathematics
Lesson 2710 of 3,12154. Number TheoryFree lesson

Division Algorithm

Understand how any integer can be expressed as a quotient and remainder when divided by a positive integer.

Division Algorithm

You'll learn how every integer can be uniquely broken down into a quotient and remainder when divided by any positive integer.

The Core Idea

Think of dividing cookies among friends. If you have 23 cookies and 5 friends, each friend gets 4 cookies (the quotient), and you have 3 cookies left over (the remainder). The Division Algorithm formalizes this everyday experience mathematically.

For any integer a and positive integer d, there exist unique integers q (quotient) and r (remainder) such that:

a = d · q + r,  where 0 ≤ r < d

The beauty is in the constraint on r: the remainder must be non-negative and strictly less than the divisor d. This uniqueness is powerful—there's exactly one way to write a in this form for a given d.

Examples

  • Dividing 23 by 5: 23 = 5 · 4 + 3 (quotient = 4, remainder = 3)
  • Dividing 17 by 6: 17 = 6 · 2 + 5 (quotient = 2, remainder = 5)
  • Dividing -17 by 5: -17 = 5 · (-4) + 3 (quotient = -4, remainder = 3)

Notice in the negative example, we still ensure 0 ≤ r < 5. We adjust the quotient downward to keep the remainder in the valid range.

Why It Matters

The Division Algorithm is foundational in number theory. It establishes that integers have a predictable structure when divided, which underpins modular arithmetic, the Euclidean algorithm for finding greatest common divisors, and countless proofs involving divisibility properties.

Key Takeaway: The Division Algorithm guarantees that any integer a can be uniquely written as a = d · q + r with 0 ≤ r < d, providing a standard form for understanding division with remainder.