Difference between revisions of "Euclidean division algorithm"

From CS2800 wiki
(Created page with "While studying Category:number theory, we will be primarily interested in the properties of the integers and natural numbers. This means that if we want to writ...")
 
 
(3 intermediate revisions by the same user not shown)
Line 4: Line 4:
  
 
{{:Proof:Euclidean division algorithm}}
 
{{:Proof:Euclidean division algorithm}}
 
Note that even though this is a proof, it also contains an ''algorithm'' for finding the [[quotient]] and [[remainder]].  If <math>a = 0</math>, follow the instructions in the base case; if <math>a > 0</math>, then first find the quotient q' and remainder r' for <math>a' = a-1</math> and <math>b</math>, then follow the instructions in the inductive step.
 
 
This is a general pattern: most [[specific|proofs that something exists]] give you instructions for finding it.  In fact, there are whole programming languages where instead of writing a program, you write a proof; after the computer checks your proof, it extracts a program for you (which is guaranteed to be correct!).
 

Latest revision as of 15:19, 8 October 2018

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.