SP20:Lecture 14 prep

From CS2800 wiki

We will show that [math]\href{/cs2800/wiki/index.php/Quot}{quot} [/math] and [math]\href{/cs2800/wiki/index.php/Rem}{rem} [/math] are functions. We will also use these to define the Base b representation (which is an important bijection between the natural numbers and the set of strings of digits).

Here are last semester's notes

I will use the following notation:

We often want to prove that there exists a sequence of values [math]a_0, a_1, \dots, a_k [/math], all in [math]X [/math], satisfying some property. Formally, we would say "there exists [math]k \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] and values [math]a_0, a_1, \dots, a_k \href{/cs2800/wiki/index.php/%E2%88%88}{∈} X [/math] such that [math]\dots [/math]".

This takes a lot of writing, and also requires us to introduce the variable [math]k [/math] (which often just adds complexity). So, we will abbreviate this to "there exists [math](a_i) \href{/cs2800/wiki/index.php/%E2%88%88}{∈} X [/math] such that [math]\dots [/math]".

We will also abbreviate sums and products of all the values: [math]\sum_i a_i [/math] denotes the sum of the [math]a_i [/math] and [math]\prod_i a_i [/math] denotes their product. We won't worry too much about the indices; unless otherwise specified, we just mean add (or multiply) all of them.

Note: there is ambiguity in this notation about whether we allow finite or infinite sequences. I will only use this notation for finite sequences.

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