The Division Algorithm for Positive Integers
The Division Algorithm for Positive Integers
Theorem 1 (The Division Algorithm): If $a$ and $b$ are positive integers where $b \neq 0$ then there exists unique integers $q$ and $r$ such that $a = bq + r$ and $0 \leq r < b$. |
- Proof: Consider the set of integers $S = \{a, a-b, a-2b, a-3b, ...\}$. This set $S$ contains a subset $T \subset S$ of nonnegative integers. By the Well-Ordering principle, the subset $T$ must contain a least element $r$, and so $T$ can be written as $T = \{ a, a-b, a-2b, ..., a-qb \}$ where $r = a - qb \geq 0$ is the least element and where $a - (q+1)b < 0$, and so:
\begin{align} \quad a = bq + r \end{align}
- Now if $r > b$ then this implies that $a - qb > b$ so $a - qb - b > 0$ and $a - (q + 1)b > 0$ which is a contradiction. Therefore $0 \leq r < b$. So we have proven that $a$ can be written in the form proposed by the theorem. We will now show that the integers $q$ and $r$ are unique. Suppose that $a = bq + r$ and $a = bq_1 + r_1$. Subtracting the second equation from the first yields:
\begin{align} \quad 0 = bq + r - (bq_1 + r_1) \\ \quad 0 = b(q - q_1) + (r - r_1) \end{align}
- Now $b \mid 0$ and $b \mid (q - q_1)$ so $b \mid r - r_1$. So $b$ is a divisor of the difference $r - r_1$. Now since $0 \leq r < b$ and $0 \leq r_1 < b$ we have that $-b < r - r_1 < b$. For $b \mid (r - r_1)$ we therefore must have that $r - r_1 = 0$ so $r = r_1$.
- Substituting this back into the earlier equation gives us:
\begin{equation} 0 = b(q - q_1) \end{equation}
- We are given that $b \neq 0$ which implies that $q - q_1 = 0$ so $q = q_1$. Therefore for $a = bq + r$ and $0 \leq r < b$ we have that the integers $q$ and $r$ are unique. $\blacksquare$
Lemma 1: If $a = bq + r$ where $0 \leq r < b$ then $(a, b) = (b, r)$. |
- Proof: By the definition of the greatest common divisor, there exists an integer $d \geq 1$, such that $d = (a , b)$. So $d \mid a$ and $d \mid b$. Therefore in the equation $a = bq + r$ we must also have that $d \mid r$. Now let $c = (b, r)$. Then $c \mid b$ and $c \mid r$ and so $c \mid a$ as well. Since $c$ is a common divisor of $a$ and $b$ we must have that $c \leq d$. Therefore $d$ is the greatest such divisor of $b$ and $r$, so:
\begin{align} \quad (a, b) = d = (b, r) \quad \blacksquare \end{align}