Proof:Euclidean division algorithm

From CS2800 wiki
For all [math]a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] and all [math]b \gt 0 [/math], there exists numbers [math]q [/math] and [math]r \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] such that
  1. [math]a = qb + r [/math]
  2. [math]0 \leq r \lt b [/math]

Here [math]q [/math] and [math]r [/math] are the quotient and remainder of [math]a [/math] over [math]b [/math]:

Definition: Quotient
We say [math]q \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ} [/math] is a quotient of [math]a [/math] over [math]b [/math] if [math]a = qb + r [/math] for some [math]r \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ} [/math] with [math]0 \leq r \lt b [/math]. We write [math]q = quot(a,b) [/math] (note that quot is a well defined function).
Definition: Remainder
We say [math]r \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ} [/math] is a remainder of [math]a [/math] over [math]b [/math] if [math]a = qb + r [/math] for some [math]q \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ} [/math] and [math]0 \leq r \lt b [/math]. We write [math]r = rem(a,b) [/math] (note that rem is a well defined function).

Note that all this is a theorem, it is called the "Euclidean division algorithm" because its proof contains an algorithm.

Proof:
We prove this by weak induction on [math]a [/math]. Let [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(a)} [/math] be the statement "for all [math]b \gt 0 [/math], there exists [math]q, r \href{/cs2800/wiki/index.php/%E2%88%88}{∈} ℕ [/math] satisfying (1) and (2) above." We will show [math]P(0) [/math] and [math]P(a+1) [/math] assuming [math]P(a) [/math].


Base case: We want to show P(0). Let [math]q = r = 0 [/math]. Then [math]qb + r = 0b + 0 = 0 = a [/math] and [math]0 \leq r \lt b [/math] since [math]r = 0 [/math].


Inductive step: Assume [math]P(a) [/math]; we want to show [math]P(a+1) [/math]. By [math]P(a) [/math], we know that there exists numbers [math]q' [/math] and [math]r' [/math] such that [math]a = q'b + r' [/math]. We want to show that there exists numbers [math]q [/math] and [math]r [/math] such that [math]a + 1 = qb + r [/math].

Since [math]r' \lt b [/math], we know that either [math]r' + 1 \lt b [/math] or [math]r' + 1 = b [/math]. In the former case, we can let [math]q = q' [/math] and [math]r = r' + 1 [/math]. Then [math]qb + r = q'b + r' + 1 = a + 1 [/math] (and clearly [math]0 \leq r \lt b [/math]).

In the latter case, we can let [math]q = q' + 1 [/math] and [math]r = 0 [/math]. Then [math]qb + r = (q' + 1)b + 0 = q'b + (r' + 1) = a + 1 [/math]. Again it is clear that [math]0 \leq r \lt b [/math].

In either case, we have shown that there exist [math]q [/math] and [math]r [/math] satisfying (1) and (2), as required.