Divisibility and the Division Algorithm

Dividing with Remainders

Number theory begins with divisibility. An integer $a$ divides $b$ (written $a \mid b$) if $b = a k$ for some integer $k$ — that is, $b$ is a multiple of $a$ with no remainder. So $3 \mid 12$ (since $12 = 3 \cdot 4$) but $3 \nmid 13$. Divisibility is the backbone of primes, factorization, and congruences.

When $a$ does not divide $b$ exactly, the division algorithm captures what happens. For any integer $b$ and positive integer $a$, there exist unique integers $q$ (the quotient) and $r$ (the remainder) with $$b = a q + r, \qquad 0 \le r < a.$$ The key constraint is $0 \le r < a$: the remainder is non-negative and strictly less than the divisor. For $b = 17, a = 5$: $17 = 5 \cdot 3 + 2$, so $q = 3$ and $r = 2$. Divisibility is exactly the case $r = 0$.

Divisibility has clean properties that make proofs easy:

• If $a \mid b$ and $a \mid c$, then $a \mid (b + c)$ and $a \mid (b - c)$ — a divisor of two numbers divides their sum and difference.
• If $a \mid b$ and $b \mid c$, then $a \mid c$ (transitivity).
• If $a \mid b$ then $a \mid bc$ for any integer $c$.

These properties, together with the division algorithm, are the tools behind the Euclidean algorithm, modular arithmetic, and the theory of primes that follow. The remainder, in particular, is the seed of modular arithmetic: "the remainder of $b$ on division by $a$" is exactly $b \bmod a$.

Common pitfall: allowing a remainder that is negative or as large as the divisor. In the division algorithm the remainder must satisfy $0 \le r < a$ — it is never negative and never equals or exceeds the divisor. Writing $17 = 5 \cdot 2 + 7$ is wrong even though the arithmetic checks out, because $7 \ge 5$; the correct remainder is $2$ with quotient $3$.

A row of b unit blocks grouped into equal piles of size a; the q full piles form the quotient and the accent leftover blocks (fewer than a) form the remainder — the division algorithm made visible.

$$b = aq + r,\quad 0 \le r < a$$