SP20:Lecture 13 prep

From CS2800 wiki

Here are the notes for last semester.

We'll start lecture 13 by fixing the broken proof that every number has a prime decomposition that we started in lecture 12.

Be sure you understand why we are stuck at the end of that lecture.

We'll also prove the existence and uniqueness of the quotient and remainder. Come to lecture knowing the following definitions and how they relate to your existing notion of quotient and remainder:

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).

Time permitting, we may start discussion the base b representation of a number; for this we will need the following definitions:

Definition: Digit
numbers [math]d [/math] satisfying [math]0 \leq d \lt b [/math] are called base b digits.
If [math]d_k, d_{k-1}, \dots, d_1, d_0 [/math] are all natural numbers satisfying [math]0 \leq d_i \lt b [/math] for all [math]i [/math], then the base b interpretation of [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(d_i)} [/math], written [math](d_kd_{k-1}\cdots{}d_1d_0)_b [/math] is given by [math]\href{/cs2800/wiki/index.php/Base}{(d_i)_b} := \sum_{i} d_ib^i [/math]