Divisibility and the Division Algorithm

⚡ Key Takeaways

Divisibility is the relation " $a$ divides $b$ " (written $a \mid b$ ), meaning $b$ is an exact integer multiple of $a$ . The Division Algorithm guarantees that for any integer $a$ and positive integer $b$ , there exist unique integers $q$ (quotient) and $r$ (remainder) with $a = bq + r$ and $0 \le r < b$ . This pair of ideas underpins all of elementary number theory — gcd computation, modular arithmetic, primes, and congruences. The concepts trace to Euclid (c. 300 BCE) and were axiomatized in the 19th century.

💡 The Core Insight

Every integer, when measured against a positive "ruler" $b$ , lands in exactly one of the half-open intervals $[bq, b(q+1))$ . The integer $bq$ is the largest multiple of $b$ not exceeding $a$ , and the leftover distance $r = a - bq$ is the remainder, forced to satisfy $0 \le r < b$ . Divisibility is precisely the special case $r = 0$ . Thus the whole arithmetic of factors collapses into one clean equation $a = bq + r$ with a tightly constrained remainder.

DefinitionDivisibility

Let $a, b \in \mathbb{Z}$ . We say $a$ divides $b$ , written $a \mid b$ , if there exists $k \in \mathbb{Z}$ such that

1

\quad b = a k.

Derivation hint: This is the definition itself — $a \mid b$ means $b$ is an integer multiple of $a$ . Here $a$ is the divisor, $b$ the dividend (or multiple), and $k$ the cofactor. When no such $k$ exists, we write $a \nmid b$ . Note $a \mid 0$ for every $a$ (take $k = 0$ ), while $0 \mid b$ only when $b = 0$ .

DefinitionBasic Properties of Divisibility

For all integers $a, b, c$ :

2

\quad a \mid b \ \text{and}\ b \mid c \ \Longrightarrow\ a \mid c \quad(\text{transitivity}).

Derivation hint: From $b = ak_1$ and $c = bk_2$ , substitute to get $c = a(k_1 k_2)$ , an integer multiple of $a$ .

3

\quad a \mid b \ \text{and}\ a \mid c \ \Longrightarrow\ a \mid (bx + cy) \quad \text{for all } x, y \in \mathbb{Z}.

Derivation hint: Write $b = a k_1$ , $c = a k_2$ ; then $bx + cy = a(k_1 x + k_2 y)$ , again a multiple of $a$ . The combination $bx+cy$ is an integer linear combination.

4

\quad a \mid b \ \text{and}\ b \mid a \ \Longrightarrow\ a = \pm b.

Derivation hint: $b = ak$ , $a = bm$ give $a = akm$ , so $km = 1$ (if $a \ne 0$ ), forcing $k = m = \pm 1$ . The zero case gives $a=b=0$ .

5

\quad a \mid b \ \text{and}\ b \ne 0 \ \Longrightarrow\ |a| \le |b|.

Derivation hint: $b = ak$ with $b \ne 0$ forces $k \ne 0$ , so $|k| \ge 1$ , hence $|b| = |a||k| \ge |a|$ .

TheoremThe Division Algorithm

Let $a \in \mathbb{Z}$ and $b \in \mathbb{Z}$ with $b > 0$ . Then there exist unique integers $q$ (the quotient) and $r$ (the remainder) satisfying

6

\quad a = b q + r, \qquad 0 \le r < b.

Derivation hint: Existence comes from the Well-Ordering Principle applied to the set of non-negative values $a - bq$ ; uniqueness from the tight bound $0 \le r < b$ . See the proof below. More generally, for $b \ne 0$ (allowing $b<0$ ) one requires $0 \le r < |b|$ , and $q, r$ are again unique.

DefinitionThe mod operator and quotient

Given the unique $q, r$ from [6], define

7

\quad a \bmod b := r, \qquad a \div b := q = \left\lfloor \frac{a}{b} \right\rfloor.

Derivation hint: $r$ is what remains after removing the largest multiple $bq \le a$ ; the quotient is the floor of the real-number ratio because $bq \le a < b(q+1)$ rearranges to $q \le a/b < q+1$ . Then by construction $b \mid a \iff (a \bmod b) = 0$ .

ProofExistence and Uniqueness in the Division Algorithm

Setup. Fix $a \in \mathbb{Z}$ , $b > 0$ . Consider the set of non-negative "shifted" values

8

\quad S = \{\, a - b q : q \in \mathbb{Z},\ a - bq \ge 0 \,\} \subseteq \mathbb{Z}_{\ge 0}.

Derivation hint: We collect all candidate remainders; the smallest will be the true remainder.

Step 1 — $S$ is non-empty. Choosing $q = -|a|$ gives $a - bq = a + b|a| \ge a + |a| \ge 0$ (since $b \ge 1$ ). So $S$ contains at least one non-negative integer.

Step 2 — $S$ has a least element. By the Well-Ordering Principle, every non-empty subset of $\mathbb{Z}_{\ge 0}$ has a smallest element. Let $r$ be the least element of $S$ , attained at some $q$ , so $a = bq + r$ with $r \ge 0$ .

Step 3 — $r < b$ . Suppose for contradiction $r \ge b$ . Then

9

\quad a - b(q+1) = (a - bq) - b = r - b \ge 0,

Derivation hint: Subtracting one more copy of $b$ keeps the value non-negative if $r \ge b$ . so $r - b \in S$ . But $r - b < r$ contradicts minimality of $r$ . Hence $r < b$ . This establishes existence with $0 \le r < b$ .

Step 4 — Uniqueness. Suppose $a = bq_1 + r_1 = bq_2 + r_2$ with $0 \le r_1, r_2 < b$ . Subtracting,

10

\quad b(q_1 - q_2) = r_2 - r_1.

Derivation hint: Equate the two representations and isolate the multiple of $b$ . Now $|r_2 - r_1| < b$ because both lie in $[0, b)$ . Thus $b \mid (r_2 - r_1)$ with $|r_2 - r_1| < b$ forces $r_2 - r_1 = 0$ , so $r_1 = r_2$ , and then $b(q_1 - q_2) = 0$ with $b > 0$ gives $q_1 = q_2$ . $\blacksquare$

∎

⚠️ Floor convention for negative dividends

The standard theorem requires $0 \le r < b$ even when $a < 0$ . For $a = -17$ , $b = 5$ the correct output is $q = -4$ , $r = 3$ (since $-17 = 5(-4) + 3$ ), not $q=-3, r=-2$ . Many programming languages' `%` operator instead returns a remainder with the sign of $a$ (so `-17 % 5 == -3` in C/Java). The mathematical "mod" is the non-negative representative.

mathematician · Euclid of Alexandria | fl. c. 300 BCE

Euclid's Elements, Book VII, lays out the first systematic theory of divisibility for the ancient Greeks, who treated numbers as lengths of line segments. Propositions VII.1 and VII.2 present what we now call the Euclidean Algorithm — anthyphairesis, "reciprocal subtraction" — for finding the greatest common measure of two magnitudes. Euclid did not have the modern symbolic Division Algorithm, but his repeated-subtraction method is its iterated application. The conceptual leap to a stand-alone existence-and-uniqueness theorem with explicit quotient and remainder came much later, crystallizing in the 19th-century arithmetization of number theory by Gauss and Dirichlet.

🧠 Intuition

Picture the integer number line and lay down evenly spaced fence posts at every multiple of $b$ : $\dots, -b, 0, b, 2b, 3b, \dots$ . Your number $a$ sits somewhere on this line. The quotient $q$ tells you which fence post is immediately at or to the left of $a$ , and the remainder $r$ is how far past that post you have to walk to reach $a$ . Because consecutive posts are exactly $b$ apart, you can never have to walk a full $b$ or more to reach the next number — that would mean you'd passed a post — so $0 \le r < b$ is geometrically inevitable. Divisibility ( $b \mid a$ ) is the case where $a$ lands exactly on a post, with nothing left over.

Figure

Division Algorithm as fence posts: a = bq + r on the number line

```svg

```

ExamplePositive dividend

Given: $a = 247$ , $b = 13$ . Find $q$ , $r$ , and decide whether $13 \mid 247$ .

Steps: 1. Estimate the quotient: $247 / 13 \approx 19.0$ , so try $q = 19$ . 2. Compute $bq = 13 \times 19 = 247$ . 3. Remainder: $r = a - bq = 247 - 247 = 0$ . 4. Check the bound: $0 \le 0 < 13$ . ✓ Since $r = 0$ , the dividend is an exact multiple.

\boxed{q = 19,\quad r = 0,\quad 13 \mid 247}

ExampleNegative dividend (the subtle case)

Given: $a = -100$ , $b = 7$ . Find the mathematical $q$ , $r$ with $0 \le r < 7$ .

Steps: 1. Real ratio: $-100 / 7 \approx -14.2857$ . 2. Quotient is the floor: $q = \lfloor -14.2857 \rfloor = -15$ (round down, toward $-\infty$ ). 3. Compute $bq = 7 \times (-15) = -105$ . 4. Remainder: $r = a - bq = -100 - (-105) = 5$ . 5. Check the bound: $0 \le 5 < 7$ . ✓ And verify: $7(-15) + 5 = -105 + 5 = -100$ . ✓

\boxed{q = -15,\quad r = 5,\quad -100 \bmod 7 = 5}

Note: a naive truncation toward zero would give $q=-14, r=-2$ , which violates $r \ge 0$ — wrong by the theorem's convention.

⚠️ Divisor versus dividend, and the

0

confusions

" $a \mid b$ " means $a$ is the smaller-or-equal factor and $b$ the multiple — students frequently invert the bar's direction. Read " $\mid$ " as "divides into": $3 \mid 12$ is true ("3 divides into 12"), $12 \mid 3$ is false.
$a \mid 0$ is true for all $a$ (including $a$ negative), since $0 = a \cdot 0$ . In particular $0 \mid 0$ is true.
$0 \mid b$ is false unless $b = 0$ . Dividing by zero is undefined, but the divisibility relation " $0 \mid b$ " is a perfectly well-formed (usually false) statement.
Divisibility is not the fraction $b/a$ ; it is a yes/no relation on integers. $\frac{12}{5}$ exists as a rational number even though $5 \nmid 12$ .

CounterexampleWhy

b>0

matters for uniqueness without absolute value

If we drop the constraint $0 \le r < b$ and merely demand $a = bq + r$ , representations are wildly non-unique. With $a = 17, b = 5$ :

17 = 5\cdot 3 + 2 = 5\cdot 2 + 7 = 5\cdot 4 + (-3) = 5\cdot 0 + 17.

All are valid as equations, but only $q=3, r=2$ obeys $0 \le r < 5$ . The remainder bound is precisely what pins down a unique answer — it is not decorative.

CounterexampleTransitivity does not run backward

From $4 \mid 12$ it does not follow that $4 \mid 6$ even though $6 \mid 12$ . Divisibility of a common multiple by $a$ says nothing about the intermediate factor: $6 \mid 12$ and $4 \mid 12$ but $4 \nmid 6$ . (Transitivity flows $a\mid b \mid c \Rightarrow a \mid c$ , not sideways.)

connection

The Division Algorithm is the engine driving the entire elementary theory:

Iterating it on $(a,b)$ , then $(b,r)$ , then $(r, r')$ , ... is exactly the Euclidean Algorithm, whose final non-zero remainder is $\gcd(a,b)$ .
The relation $a \equiv a' \pmod b \iff (a \bmod b) = (a' \bmod b)$ launches Modular Arithmetic and the ring $\mathbb{Z}/n\mathbb{Z}$ .
Divisibility plus the Fundamental Theorem of Arithmetic reduces every divisibility question to comparing prime exponents.
Abstracting "a division algorithm exists" gives the notion of a Euclidean Domain, a special class of integral domain where unique factorization is guaranteed.
The set of integer linear combinations $\{ax + by\}$ from property [3] is the ideal $(a,b) = (\gcd(a,b))$ , the entry point to ring theory.

🔬 Where this appears

⏳ History

- c. 300 BCE — Euclid's Elements, Book VII. Anthyphairesis (mutual subtraction) for the greatest common measure; the algorithmic seed of division with remainder.

- c. 250 CE — Diophantus, Arithmetica. Systematic study of integer and rational solutions, sharpening interest in factors and divisibility.

- c. 500–600 CE — Aryabhata & Brahmagupta (India). The kuṭṭaka ("pulverizer") method solves linear Diophantine equations via iterated division, anticipating the extended Euclidean algorithm.

- 1202 — Fibonacci's Liber Abaci. Brings Hindu–Arabic numerals and remainder arithmetic to Europe, popularizing practical division.

- 1801 — Gauss's Disquisitiones Arithmeticae. Formalizes congruence notation

a \equiv b \pmod m

, founded directly on remainders, and elevates divisibility to a rigorous discipline.

- 1837 — Dirichlet. Uses divisibility and arithmetic progressions to prove infinitely many primes in

a + nd

, deepening the structural role of remainders.

- 1888 — Dedekind & Peano. The Peano axioms and the Well-Ordering Principle give the Division Algorithm its modern, fully rigorous proof foundation.

- 1960s — Knuth, The Art of Computer Programming, Vol. 2. Treats the Division Algorithm and Euclid's method as cornerstone computational objects, analyzing complexity precisely.

- Late 20th c. — Euclidean domains. Abstract algebra generalizes the Division Algorithm to polynomial rings and Gaussian integers, unifying integer and polynomial division.

open-problem

While the Division Algorithm itself is settled, the divisibility questions it spawns include some of mathematics' deepest open problems. Factoring — given $n$ , find its divisors — has no known polynomial-time classical algorithm, and its presumed hardness secures RSA; whether $\mathrm{P} = \mathrm{NP}$ or a sub-exponential classical factoring algorithm exists remains open. The distribution of divisors fuels the Erdős–Straus conjecture (is $4/n = 1/x + 1/y + 1/z$ solvable for all $n \ge 2$ ?) and the still-open question of whether there exist odd perfect numbers (an integer equal to the sum of its proper divisors). In ring theory, classifying which number rings admit a Euclidean function (are norm-Euclidean) is unresolved in general — e.g., $\mathbb{Z}[\sqrt{14}]$ was only relatively recently shown Euclidean by a non-norm function.

Divisibility and the Division Algorithm

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also