Divisibility and the Division Theorem

Divisibility

Definition

For integers $a$ and $b$, we say $a$ divides $b$, written $a \mid b$, if and only if there exists an integer $k$ such that $b = ak$.

$a \mid b \iff \exists k \in \mathbb{Z}. b = ak$

Terminology

• $a$ is a divisor or factor of $b$
• $b$ is a multiple of $a$
• If $a \nmid b$, then $a$ does not divide $b$

Examples

• $3 \mid 12$ since $12 = 3 \cdot 4$
• $-3 \mid 12$ since $12 = (-3) \cdot (-4)$
• $5 \nmid 12$ since no integer $k$ satisfies $12 = 5k$
• $a \mid 0$ for all $a \neq 0$ since $0 = a \cdot 0$

Properties of Divisibility

Reflexivity

$a \mid a \quad \text{for all } a \in \mathbb{Z}$

Transitivity

$a \mid b \land b \mid c \Rightarrow a \mid c$

Proof: If $b = ak$ and $c = b\ell$, then $c = ak\ell = a(k\ell)$.

Linearity

$a \mid b \land a \mid c \Rightarrow a \mid (bx + cy) \text{ for all } x, y \in \mathbb{Z}$

Proof: If $b = ak$ and $c = a\ell$, then $bx + cy = akx + a\ell y = a(kx + \ell y)$.

Antisymmetry (up to sign)

$a \mid b \land b \mid a \Rightarrow a = \pm b$

Proof: If $a \mid b$ and $b \mid a$, then $b = ak$ and $a = b\ell$ for integers $k, \ell$.

Hence $a = ak\ell$, so $a(1 - k\ell) = 0$.

If $a = 0$, then $b = 0$ and $a = b$.

If $a \neq 0$, then $k\ell = 1$. Since $k, \ell \in \mathbb{Z}$, we have $(k, \ell) = (1, 1)$ or $(-1, -1)$.

Thus $b = a$ or $b = -a$.

The Division Theorem

Statement

Theorem (Division Theorem): For any integer $a$ and positive integer $b > 0$, there exist unique integers $q$ and $r$ such that:

$a = bq + r \quad \text{with } 0 \leq r < b$

• $q$ is the quotient (how many times $b$ fits into $a$)
• $r$ is the remainder (what is left over)
• We write $r = a \bmod b$

Examples

$a$	$b$	$q$	$r$	Verification
17	5	3	2	$17 = 5 \cdot 3 + 2$
-17	5	-4	3	$-17 = 5 \cdot (-4) + 3$
20	7	2	6	$20 = 7 \cdot 2 + 6$
14	2	7	0	$14 = 2 \cdot 7 + 0$

Proof Outline

Existence:

Consider the set $S = \{a - bk : k \in \mathbb{Z}, a - bk \geq 0\}$.

This set is non-empty (take $k$ large and negative if $a < 0$, or $k = 0$ if $a \geq 0$).

Let $r$ be the smallest element of $S$. Then $r = a - bq \geq 0$ for some $q$.

If $r \geq b$, then $r - b = a - b(q+1) \geq 0$, contradicting minimality.

So $0 \leq r < b$.

Uniqueness:

If $a = bq_1 + r_1 = bq_2 + r_2$ with $0 \leq r_1, r_2 < b$:

Then $b(q_1 - q_2) = r_2 - r_1$.

We have $|r_2 - r_1| < b$, so $b \mid (r_2 - r_1)$ forces $r_2 - r_1 = 0$.

Thus $r_1 = r_2$ and hence $q_1 = q_2$.

Computing Quotient and Remainder

For Non-negative $a$

$q = \lfloor a/b \rfloor \quad \text{and} \quad r = a - bq$

For Negative $a$

Be careful: $-17 \bmod 5 = 3$, not $-2$.

The standard convention requires $0 \leq r < b$:

$r = a - b \cdot \left\lfloor \frac{a}{b} \right\rfloor$

Properties of Remainder

Invariance under Addition

If $a \equiv r \pmod{b}$ and $c \equiv s \pmod{b}$ with $0 \leq r, s < b$, then:

$a + c \equiv r + s \pmod{b}$

Invariance under Multiplication

If $a \equiv r \pmod{b}$ and $c \equiv s \pmod{b}$ with $0 \leq r, s < b$, then:

$ac \equiv rs \pmod{b}$

---

Summary

• $a \mid b$ means there exists $k$ with $b = ak$
• Divisibility is reflexive, transitive, and antisymmetric up to sign
• The Division Theorem: for $b > 0$, unique $q, r$ with $a = bq + r$ and $0 \leq r < b$
• Remainder satisfies $0 \leq r < b$ even for negative $a$