## Reading

These notes and
closely review

Unit 3
Sections 1 through 3.4.

## Quiz questions

Finish those problem sets!

## Review quiz questions

We went over the best-case time analysis for mergesort, and
decided that with an input of all equal values, mergesort runs
in $O(n)$ time, so the best case running time function is
$\Theta(n)$.

## Why number theoretic algorithms? A look at simple factorization

See Unit notes.

## Modular airthmetic

We saw the "integers mod $n$" ($Z_n$) as its own number system, with +,
and *. We saw that we have "-" as well, because we saw that
every element of $Z_n$ has an "additive inverse", and that gives
us subtraction. Finally, we saw that often, but not always, we
can find a multiplicative inverse of an element of $Z_n$, which
means we can do division. Our next job will be to characterize
when this is possible!