Engineering / Mathematics — Integer Foundations
Division with Remainder for Integers
The division algorithm for integers, the uniqueness of quotient and remainder, and the role of well-ordering in establishing it.
Executive summary
Division with remainder is the operation that makes the integers computationally tractable. It converts the divisibility relation from a yes-or-no question into a quantitative one, producing not just a verdict but a measure of failure — the remainder.
Its uniqueness is what allows algorithms to be built on it, and its guaranteed decrease in remainder size is what makes the Euclidean algorithm terminate.
Learning objectives
- State the division theorem with its exact range condition on the remainder.
- Prove existence and uniqueness of quotient and remainder.
- Recognise why the range convention matters computationally.
01The division theorem
Division with remainder
For integers a and b with b ≠ 0, there exist unique integers q and r satisfying
a = bq + r and 0 ≤ r < |b|.
Existence follows from well-ordering. Consider the set of non-negative integers of the form a − bq as q ranges over the integers. This set is non-empty, so it has a least element r. If r ≥ |b| then r − |b| would be a smaller non-negative member, contradicting minimality.
Uniqueness follows by subtraction. If a = bq₁ + r₁ = bq₂ + r₂ then b(q₁ − q₂) = r₂ − r₁. The right side has absolute value strictly less than |b| while the left is a multiple of b, so both are zero.
02The range convention
The condition 0 ≤ r < |b| is a choice. Two other conventions are in use and both appear in practice.
| Convention | Range of r | Used for |
|---|---|---|
| Non-negative | 0 ≤ r < |b| | The standard for number theory; matches residue classes |
| Symmetric | −|b|/2 < r ≤ |b|/2 | Reduces operand magnitude; used in lattice and continued fraction work |
| Truncated | sign follows a | What C-family languages implement for the % operator |
03Why this operation is foundational
Three consequences follow immediately and each supports a large body of later theory.
Residue classes exist
Every integer reduces to exactly one value in {0, 1, ..., |b|−1}, which is what makes the integers modulo b a well-defined finite set.
Euclid terminates
Each step of the Euclidean algorithm replaces a pair by a strictly smaller remainder, and a strictly decreasing sequence of non-negative integers must stop.
Base representation works
Repeated division by a base produces the digits of a positional representation, uniquely and terminating.
The same theorem, with degree replacing absolute value, holds for polynomials over a field. That parallel is not a coincidence: both are instances of a Euclidean domain, and every algorithm resting on division with remainder transfers between the two settings essentially unchanged.
04Frequently asked questions
Why require b ≠ 0?
Because with b = 0 the equation a = 0·q + r forces r = a, and the range condition 0 ≤ r < 0 is unsatisfiable. Division by zero fails here for the same structural reason it fails in the rationals.
Does the theorem hold for negative divisors?
Yes, which is why the range is stated with |b| rather than b. For a = 7 and b = −3 the result is q = −2 and r = 1, since 7 = (−3)(−2) + 1 and 0 ≤ 1 < 3.
Is the symmetric convention ever preferable?
Yes, when operand size drives cost. Keeping remainders in a symmetric range roughly halves their magnitude, which measurably speeds up continued-fraction-style algorithms and is standard in lattice basis reduction.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 1-4.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.