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
- [math]a = qb + r
[/math]
- [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]:
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).
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.
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 \gt 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 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!).
