Divisibility and the Division Algorithm

Divisibility & the Division Algorithm

Number theory begins with divisibility. An integer $a$ divides $b$ (written $a \mid b$) if $b = ak$ for some integer $k$, meaning $b$ is a multiple of $a$ with no remainder. For example, $3 \mid 12$ because $12 = 3 \cdot 4$, but $3 \nmid 13$.

When $a$ does not divide $b$ exactly, the division algorithm governs the outcome. For any integer $b$ and positive integer $a$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that:

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

Divisibility is simply the special case where $r = 0$.

For $b = 17$ and $a = 5$, we write $17 = 5 \cdot 3 + 2$, yielding quotient $q = 3$ and remainder $r = 2$.

Rules & Pitfalls

Divisibility relies on algebraic properties that streamline proofs and form the backbone of modular arithmetic:

Common Pitfall: A remainder must strictly satisfy $0 \le r < a$. It is never negative and never equals or exceeds the divisor.

Writing $17 = 5 \cdot 2 + 7$ is incorrect even though the arithmetic checks out, because $7 \ge 5$. The correct form is $17 = 5 \cdot 3 + 2$.