Definition: The theorem stating that for any integer N and positive integer b, there exist unique integers q (quotient) and r (remainder) such that N = qb + r, where 0 ≤ r < b. This proves Representational Uniqueness.
Chapter 1: The "Fair Shares" Rule (Elementary School Understanding)
Imagine you have a big pile of 17 cookies (N=17). You want to share them fairly among your 5 friends (b=5).
The Division Algorithm is the "Fair Shares" rule. It's a promise that when you do this, there is only one, single, correct way the sharing can turn out.
Give Everyone a Fair Share: You give each of your 5 friends one cookie, then another, then another. You find that each friend can get 3 cookies. This is the quotient (q).
Count the Leftovers: After you give everyone their 3 cookies (5 friends × 3 cookies = 15 cookies), you look at what's left. You have 17 - 15 = 2 cookies left over. This is the remainder (r). The number of leftovers must be smaller than the number of friends (otherwise you could have given out another round!).
The final result is: 17 = (3 × 5) + 2.
The Division Algorithm is the law that guarantees that for any number of cookies and any number of friends, there is always one, unique answer for how many shares each friend gets and how many leftovers there are. You can't have two different correct answers.
Chapter 2: The Quotient and Remainder Theorem (Middle School Understanding)
The Division Algorithm is a theorem, not an algorithm in the computer science sense. It doesn't tell you how to find the quotient and remainder (long division is the algorithm for that), but it guarantees that they always exist and are unique.
The Theorem: For any integer N (the dividend) and any positive integer b (the divisor), there exist unique integers q (the quotient) and r (the remainder) such that:
N = qb + r
and the remainder is constrained: 0 ≤ r < b.
Example: Let N = -26 and b = 7.
We are looking for q and r such that -26 = 7q + r and 0 ≤ r < 7.
If we guess q=-3, we get 7(-3) + r = -21 + r. -26 = -21 + r means r = -5. This is invalid because the remainder can't be negative.
We need to go "further down." Let's try q=-4. -26 = 7(-4) + r = -28 + r.
This gives r = -26 - (-28) = 2. This is valid, because 0 ≤ 2 < 7.
The unique solution is q=-4 and r=2.
Proving Representational Uniqueness:
This theorem is the foundation for proving that every number has a unique representation in any base. The process of converting a number to base b is just applying the Division Algorithm repeatedly. The remainders r you get at each step become the digits of the number in that base. Since the q and r are unique at every step, the final sequence of digits must also be unique.
Chapter 3: The Well-Ordering Principle and Uniqueness (High School Understanding)
The Division Algorithm is a fundamental theorem in number theory.
The Theorem: For any N ∈ ℤ and b ∈ ℤ⁺, there exist unique integers q, r such that N = qb + r and 0 ≤ r < b.
Proof of Existence (using the Well-Ordering Principle):
The Set: Consider the set S = {N - kb | k ∈ ℤ and N - kb ≥ 0}. This is the set of all non-negative numbers you can get by subtracting multiples of b from N. This set is non-empty.
The Well-Ordering Principle: This principle states that every non-empty set of non-negative integers must have a least element. Let this least element be r.
The Remainder: By definition, r = N - qb for some integer q, which means N = qb + r. And by the definition of our set, r ≥ 0.
The Bound: We must show r < b. Assume for contradiction that r ≥ b. Then r - b ≥ 0.
r - b = (N - qb) - b = N - (q+1)b.
This new number, r-b, is a member of our set S. But r-b < r, which contradicts our assumption that r was the least element.
Therefore, our assumption must be false, and r < b. This proves the existence of q and r.
Proof of Uniqueness:
Assume there are two different solutions: N = q₁b + r₁ and N = q₂b + r₂.
q₁b + r₁ = q₂b + r₂ → (q₁ - q₂)b = r₂ - r₁.
This means b divides r₂ - r₁. But we know 0 ≤ r₁, r₂ < b, which means -b < r₂ - r₁ < b.
The only multiple of b in the open interval (-b, b) is 0.
Therefore, r₂ - r₁ = 0, which means r₁ = r₂.
If r₁=r₂, then (q₁ - q₂)b = 0. Since b > 0, we must have q₁ - q₂ = 0, which means q₁ = q₂.
The quotient and remainder are unique.
Chapter 4: A Statement on Cosets of the Subgroup nℤ (College Level)
The Division Algorithm is the theorem that establishes the structure of the ring of integers ℤ as a Euclidean Domain. A Euclidean Domain is an integral domain equipped with a function (a "Euclidean function," in this case f(n)=|n|) that allows for a generalized notion of division with remainder.
The Structural Interpretation:
The theorem is a statement about the cosets of the subgroup bℤ (the set of all multiples of b) within the group of integers under addition (ℤ, +).
The congruence classes modulo b are precisely these cosets. A coset a + bℤ is the set of all integers {..., a-2b, a-b, a, a+b, a+2b, ...}.
The Division Algorithm proves that there are exactly b such distinct cosets, and that the set of remainders {0, 1, ..., b-1} forms a complete set of unique coset representatives.
Any integer N belongs to exactly one coset, and its remainder r is the canonical representative of that coset. N ∈ r + bℤ.
The Foundation of Modular Arithmetic:
This theorem is the absolute bedrock of modular arithmetic. The existence and uniqueness of the remainder r is what guarantees that the mod b function is well-defined. Without this, the entire structure of the ring ℤ/bℤ would collapse, as the operations [a]+[b]=[a+b] would not be consistent.
Proving Representational Uniqueness:
The treatise cites this theorem as the proof of Representational Uniqueness in any base b. The process of finding the base b digits of N is a recursive application of the algorithm:
N = q₀b + d₀
q₀ = q₁b + d₁
q₁ = q₂b + d₂
...
The sequence of digits is (...d₂d₁d₀)_b. Since the quotient q and remainder r are uniquely determined at every single step, the entire sequence of digits must also be unique.
Chapter 5: Worksheet - The Unique Answer
Part 1: The "Fair Shares" Rule (Elementary Level)
You have 23 toys to share among 4 friends.
What is the quotient q (the number of toys each friend gets)?
What is the remainder r (the number of toys left over)?
Write the result as an equation in the form N = qb + r.
Part 2: The Quotient and Remainder (Middle School Understanding)
For N=47 and b=6, find the unique integers q and r that satisfy the Division Algorithm.
For N=-10 and b=3, find the unique q and r. Remember that r cannot be negative.
How does this theorem prove that a number's representation in base-10 is unique?
Part 3: The Well-Ordering Principle (High School Understanding)
What is the Well-Ordering Principle?
The proof of existence for the Division Algorithm creates a special set S. What is this set, and what does the Well-Ordering Principle guarantee about it?
The proof of uniqueness starts by assuming there are two different solutions. What is the final contradiction that this assumption leads to?
Part 4: Cosets (College Level)
The Division Algorithm establishes ℤ as what kind of special ring?
What is a coset of a subgroup H in a group G?
How does the Division Algorithm prove that {0, 1, ..., b-1} is a complete set of unique representatives for the cosets of bℤ in ℤ?
Why is the Division Algorithm the absolute foundation for modular arithmetic and the ring ℤ/nℤ?