Divisibility and the Division Algorithm

We prove each part directly from the definition $a \mid b \iff \exists c \in \mathbb{Z}, b = ac$.

(1) Since $a = a \cdot 1$ and $1 \in \mathbb{Z}$, we have $a \mid a$.

(2) Suppose $a \mid b$, so $b = ak$ for some $k \in \mathbb{Z}$. Then for any $c \in \mathbb{Z}$, $bc = (ak)c = a(kc)$, and $kc \in \mathbb{Z}$, so $a \mid bc$.

(3) Suppose $a \mid b$ and $b \mid c$. Then $b = ak$ for some $k \in \mathbb{Z}$, and $c = bm$ for some $m \in \mathbb{Z}$. Substituting, $c = (ak)m = a(km)$, and $km \in \mathbb{Z}$, so $a \mid c$. (Note this holds even if $b = 0$: then $a \mid 0$ forces nothing extra, and $b \mid c$ with $b=0$ forces $c = 0$, and indeed $a \mid 0$.)

(4) Suppose $a \mid b$ and $a \mid c$, so $b = ak$ and $c = am$ for some $k, m \in \mathbb{Z}$. For any integers $x, y$,

and $kx + my \in \mathbb{Z}$, so $a \mid (bx+cy)$.

(5) Suppose $a \mid b$, so $b = ac_0$ for some $c_0 \in \mathbb{Z}$. Then $b = (-a)(-c_0)$, and $-c_0 \in \mathbb{Z}$, so $(-a) \mid b$. The converse follows by applying the same argument with $-a$ in place of $a$ (since $-(-a) = a$). Similarly, $b = ac_0$ gives $-b = a(-c_0)$, so $a \mid (-b)$; and the converse is symmetric.

(6) Suppose $a \mid b$ with $b \neq 0$, so $b = ac$ for some $c \in \mathbb{Z}$. Since $b \neq 0$ and $b = ac$, neither $a$ nor $c$ can be $0$ (a product with a zero factor is $0$). Hence $a \neq 0$ and $c \neq 0$ are integers, so $|c| \ge 1$. Taking absolute values, $|b| = |a||c| \ge |a| \cdot 1 = |a|$.

(7) Suppose $a \mid b$ and $b \mid a$. If $a = 0$: then $b \mid a = 0$ is automatic, and $a \mid b$ with $a=0$ forces (by the convention that $0$ divides only $0$) $b = 0$; so $a = b = 0 = \pm b$, and the claim holds. If $a \neq 0$: since $b \mid a$ and $a \neq 0$, property (6) gives $|b| \le |a|$. If $b = 0$, then $a \mid b = 0$ is automatic but $b \mid a$ with $b = 0$ forces $a = 0$, contradicting $a \ne 0$; so $b \neq 0$ too, and property (6) applied to $a \mid b$ gives $|a| \le |b|$. Combining, $|a| = |b|$, hence $a = b$ or $a = -b$, i.e. $a = \pm b$. $\blacksquare$

We prove existence and uniqueness separately. The proof technique for existence is the well-ordering principle: every nonempty set of nonnegative integers has a least element. This is a foundational property of $\mathbb{Z}_{\ge 0}$ (equivalent to the principle of induction) and is taken as known background about the integers.

Existence. Define the set

That is, $S$ is the set of all nonnegative integers of the form $a - bk$ as $k$ ranges over $\mathbb{Z}$. Step 1: $S$ is nonempty. We must exhibit at least one $k \in \mathbb{Z}$ with $a - bk \ge 0$.

• If $b > 0$: take $k = -|a|$. Then $a - bk = a + b|a|$. Since $b \ge 1$, $b|a| \ge |a| \ge -a$, so $a + b|a| \ge a + (-a) = 0$. Thus $a - bk \ge 0$.
• If $b < 0$: take $k = |a|$. Then $a - bk = a - b|a| = a + |b| \cdot |a|$ (since $-b = |b|$). As $|b| \ge 1$, $|b||a| \ge |a| \ge -a$, so $a + |b||a| \ge 0$.

In both cases we produced an integer $a - bk \ge 0$, so $S \neq \varnothing$. Step 2: apply well-ordering. Since $S$ is a nonempty subset of $\mathbb{Z}_{\ge 0}$, by the well-ordering principle $S$ has a least element. Call it $r$, and let $q \in \mathbb{Z}$ be an integer with $r = a - bq$ (such $q$ exists by definition of $S$). Rearranged, this is exactly

Step 3: show $r < |b|$. Suppose, for contradiction, that $r \ge |b|$. Define $r' = r - |b|$; since $r \ge |b| \ge 0$ (as $|b|\ge 1$ because $b\ne0$), we have $r' \ge 0$, so $r'$ is a nonnegative integer. We claim $r' \in S$: indeed,

If $b > 0$, then $|b| = b$, so $r' = a - bq - b = a - b(q+1)$, which is of the required form $a - bk$ with $k = q+1 \in \mathbb{Z}$. If $b < 0$, then $|b| = -b$, so $r' = a - bq + b = a - b(q - 1)$, of the form $a - bk$ with $k = q - 1 \in \mathbb{Z}$. Either way $r' \in S$. But $r' = r - |b| < r$ (since $|b| \ge 1 > 0$), contradicting that $r$ is the least element of $S$. Hence the assumption $r \ge |b|$ is false, and we conclude

This establishes existence of $q, r$ satisfying $a = bq + r$ and $0 \le r < |b|$.

Uniqueness. Suppose $q, r$ and $q', r'$ are both pairs of integers satisfying

Subtracting the two equations,

From $0 \le r < |b|$ and $0 \le r' < |b|$, we get

i.e. $|r - r'| < |b|$. But $r - r' = b(q' - q)$, so

Since $b \neq 0$, we may divide both sides by $|b| > 0$ to get $|q' - q| < 1$. As $q' - q$ is an integer, the only integer with absolute value strictly less than $1$ is $0$. Hence $q' - q = 0$, i.e. $q = q'$. Substituting back into $b(q'-q) = r - r'$ gives $r - r' = 0$, i.e. $r = r'$. Thus $(q,r) = (q',r')$, proving uniqueness.

The last claim. If $r = 0$ then $a = bq$, so $b \mid a$ by definition. Conversely, if $b \mid a$, then $a = bk$ for some $k \in \mathbb{Z}$; writing $a = bk + 0$ with $0 \le 0 < |b|$ exhibits a valid quotient-remainder pair with remainder $0$, and by the uniqueness just proved, this must be the pair produced by the algorithm, so its remainder $r = 0$. $\blacksquare$