Euclid's Division Lemma

Theorem 2:  Euclid's Division Lemma

Given two integers $a$ and $b$ with $b \ne 0$, there exist unique integers $q$ and $r$ such that:

• $a = bq+r$
• $0 \le r < |b|$

Note:  Where $|b|$ is the absolute value of $b$.

Proof:

(1)  Case 1:  $a \ge 0$

(2)  Let $S$ be the set of all integers $a - bk$ where $k$ is an integer and $a - bk \ge 0$

(3)  $S$ is non-empty since either $a = a - b\times0 \ge 0$ which is in $S$

(4)  By the Well-Ordering Principle, there exists an integer $q$ such that $a - bq$ is the least element in $S$

(5)  Let $r = a - bq$.  $0 \le r$ by definition of $S$.  Further $r < b$ since if $r \ge b$, then it is not the least element since $r - b = a - bq - b = a - b(q+1) \ge 0$ would be less than $r$ and an element in $S$.

(6)  $r,q$ must be unique.  Assume that there exists $r', q'$ such that $a = qb + r = q'b + r'$  and $|r - r'| > 0$ and $|q - q'| > 0$.  Then, $b > |r - r'| = b|q - q'| > b$ which is impossible.

(7)  Case 2:  $a < 0$  In this case, let $a' = -a$.  It now follows that $a' \ge 0$ and there exists unique $r,q$.  It now follows that $a = -(bq +r) = b(-q) -r$  If $r > 0$, then $a = b(-q+1) + (b-r)$ with $0 < b-r < b$