Euclidean division algorithm

From CS2800 wiki
(Redirected from Quot)

While studying number theory, we will be primarily interested in the properties of the integers and natural numbers. This means that if we want to write something like "[math]a/b [/math]", we'll have to be very careful to check that [math]b [/math] divides [math]a [/math]. This makes everything very complicated, so instead, we'll avoid dividing natural numbers.

We can, however, do division with remainder. The Euclidean division algorithm is just a fancy way of saying this:

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.