\documentstyle[12pt,twoside,amsfonts,amstex]{article}
\input{macros-course-lectures}

\parskip1.5ex
\parindent0pt
\newtheorem{falsethm}{False Theorem}


\begin{document}

Okay, you've been moved to 24-115, F1 and F2 and you'll be in 36-156 F1.

One other useful def:
\begin{defin}
If $x$ and $y$ are integers, where $y > 0$, then
$x \bmod y$ is the remainder on division of $x$ by $y$. 
\end{defin}

$x \bmod y$ is well defined by the division algorithm.  \\
$0 \le x \bmod y < y$. 

\subsection{Divisibility and Primes}

\begin{defin}
If $a$ and $b$ are integers, $a \neq 0$, then $a$ {\em divides} $b$
(written $a \mid b$) if $(\exists c)$, $c$ an integer, such that
$b = a c$.
\\
We say $a$ {\em goes into} $b$ (in elementary school), or $b$ is {\em
divisible} by $a$.
\end{defin}

This means remainder 0 in division algorithm.

Makes sense even for negative integers, but we'll mainly think of
positive integers.

\begin{defin}
If $a$ is a natural number $\geq 2$, then
$a$ is {\em prime} if the only natural numbers dividing $a$ are $1$
and $a$.
\end{defin}

\begin{defin}
If $a$ is a natural number $\geq 2$, then
$a$ is {\em composite} if $a=bc$ for natural numbers $b,c \ne 1,a$.
\end{defin}

Basic divisibility properties:

\begin{theorem}
\label{additive}
\label{multiply}
\begin{enumerate}
\item
If $a \mid b$ and $a \mid c$, then $a \mid (b+c)$ and $a \mid (b-c)$.
\item
If $a \mid b$ then $a \mid bc$ for any $c$.
\item
If $a \mid b$ and $b \mid c$ then $a \mid c$.
\end{enumerate}
\end{theorem}

\begin{proof}
(Of part 1)
By definition of divisibility, 
$(\exists t) b = at$ and $(\exists s) c = as$.\\  
Therefore, $b+c = at+as = a(t+s)$.\\  
Therefore, by definition, $a \mid b+c$. \\
\\
Parts 2 and 3 are similar (use 2 to prove 3).
\end{proof}

Already did some results about these notions -- e.g., the division
algorithm, and half of the Fundamental Theorem of Arithmetic:

\begin{theorem}
(Fundamental Theorem of Arithmetic) \\
Every natural number $\geq 1$ has a factorization into primes. \\
Moreover, the factorization is unique (except for reordering the factors)
\end{theorem}

We proved existence using well ordering. \\
Later today, we will also prove uniqueness. \\

\subsection{GCDs and LCMs}

Remember Die Hard?  \\
Why did $5$ and $3$ buckets work but $6$ and $3$ not?  \\
What if buckets are $21$ and $133$, and goal is $13$ gallons?

\begin{defin}
Let $a$, $b$ be integers, not both $0$.
The {\em greatest common divisor} of $a$ and $b$, written
$\gcd{a}{b}$, is the largest natural number $g$ such that $g \mid a$
and $g \mid b$.
\end{defin}

We can prove GCD is well defined: \\ Can use well-ordering to prove
that any nonempty finite set has a {\em largest} element. \\ The set
of common divisors includes $1$, and is finite because it is bounded
above by either number. \\ 

Note GCD is always positive. \\
\\
GCD of $24$ and $36$? $21$ and $133$? \\
\\
It turns out that in Die Hard, buckets of size $a$, $b$ always produce
numbers divisible by $\gcd{a}{b}$. \\
Q: Can all such numbers in range $0, \ldots, \max{(a,b)}$ be
produced? \\
\\
Here is an interesting theorem that shows that a GCD is always
expressible as a sum.  \\
This theorem will be used for many purposes, e.g., to help in proving
the uniqueness part of the Fundamental Theorem of Arithmetic.

\begin{theorem}
Let $x$ and $y$ be integers, not both $0$. \\
Then $\gcd{x}{y}$ can be expressed in the form $ax+by$ 
for some integers $a$ and $b$.
\end{theorem}

Examples:
$x = 22$, $y = 16$ \\
Then GCD is $2$, express as $2 = 3 (22) + (-4) (16)$.
Note can use negative integers. \\
\\
$x = -22$, $y = 16$ \\
Again, GCD is $2$, express as $2 = (-3) (-22) + (-4) (16)$.
(The GCD is always nonnegative.)

\begin{proof}
  This is a nontrivial proof.  Until now, we've been looking at
  mechanics of poving things.  This proof also requires some
  creativity.


Assume wlog that $x, y \geq 0$.  (Otherwise, use negative coefficients
as above.) \\
If either is $0$, then the GCD is defined to be the other -- unwind
the definition, which is certainly expressible in this way. \\
So we're left with the case where $x$ and $y$ are both positive. \\
\\
Let $S$ be the set of positive integers expressible in the form $ax +
by$, where $a$ and $b$ are integers. \\
Fix $l$ to be the smallest element in $S$ -- exists by well-ordering,
$S$ is nonempty since $x \in S$. \\
Fix $a$ and $b$ such that $l = ax + by$. \\
\\
As an example, let $x=22$, and $y=16$. $S$ includes all numbers 
$ax+by$, for all integers $x$ and $y$. It includes:
\begin{eqnarray*}
0x + 1y &= 16\\
1x + (-1)y &= 8\\
(-1)x + 2y &= 10\\
2x + (-2)y &= 12\\
3x + (-4)y &= 2
\end{eqnarray*}
and many others. $l=2$ turns out to be the smallest element in $S$.
We claim $l$ is what we want, {\em i.e.}, $\gcd{x}{y}$. We need to show: 
\begin{enumerate}
\item
$l$ is a common divisor of $x$ and $y$. \\
\item
Any common divisor of $x$ and $y$ also divides $l$ (so $l$ is the
greatest -- if a number $c$ goes into a positive number $l$, then $c
\leq l$).
\end{enumerate}

\begin{enumerate}
\item 
$l$ is a common divisor of $x$ and $y$. \\

First show $l \mid x$. \\
Write $x = ql+r$ by division algorithm, where $0 \leq r < l$. \\
Then rewrite:
\begin{eqnarray*}
r &= &x-ql\\
  &= &x - q(ax+by)\\
  &= &(1-qa)x + (-qb)y
\end{eqnarray*}
So $r$ is also expressible in the sum form. \\
We know $0 \leq r < l$. \\
If $r$ were positive, it would be in $S$, and would be smaller than
$l$, which would contradict our choice of $l$ as the smallest
element of $S$. \\
So it must be that $r = 0$. \\
So $x = q l$, which says that $l \mid x$. \\
\\
Similarly, $l \mid y$. 

\item
Any common divisor of $x$ and $y$ also divides $l$. \\

Easy: $c \mid x$ and $c \mid y$ imply $c \mid ax+by=l$.
\end{enumerate}
\end{proof}

The symmetric concept to GCD is LCM:

\begin{defin}
Let $a$, $b$ be positive integers. 
The {\em least common multiple} of $a$ and $b$, written
$\lcm{a}{b}$, is the smallest natural number $l$ such that 
$a \mid l$ and $b \mid l$.
\end{defin}

Why do we know this is well defined?

\subsection{Fundamental Theorem of Arithmetic}

With the addition characterization we just proved for the GCD, we are
finally ready to prove the Fundamental Theorem. \\
\\
Recall statement.  Already proved existence.
So remains to prove uniqueness. \\
For this, use basic number theory lemmas: 

\begin{lemma}
Let $p$ be a prime, and $a$ and $b$ any integers.  
If $p \mid ab$, then $p \mid a$ or $p \mid b$.   
\end{lemma}

\begin{proof}
If $p \mid a$, we are done, so assume not. \\
Then $\gcd{p}{a} = 1$. \\
(Because the only positive divisors of $p$ are $p$ and $1$, 
and $p$ doesn't divide $a$.) \\
So by the addition form above, can write $1$ as a sum of the form
$1 = sa + tp$, where $s$ and $t$ are integers. \\
Multiplying by $b$: \\
$b = sab + tpb$. \\
We have $p \mid sab$, since $p \mid ab$. \\
Also, $p \mid tpb$. \\
So $p \mid b$ (by Theorem~\ref{additive}).
\end{proof}

\begin{corollary}
Let $p$ be a prime, and $a_1, \cdots, a_k$ any integers. \\
If $p \mid a_1 a_2 \cdots a_k$, then $(\exists i) p\mid a_i$.
\end{corollary}

Now prove uniqueness, in Fundamental Theorem:

\begin{proof} 
(Uniqueness of prime decomposition)
We argue by (strong) induction.  
The base case $n=1$ is trivial -- the product of no factors is defined
to be $1$. \\
INDUCTIVE STEP: \\
Suppose the claim true for all numbers less than $n$. \\
Now show for $n$. \\
Suppose for contradiction that there are two different factorizations,
$n=p_1p_2\cdots p_k$ and $n=q_1q_2\cdots q_l$.  \\
Assume that the primes in each factorization are written in
nondecreasing order. \\
Then $p_1 \mid q_1\cdots q_l$. \\
By corollary, $(\exists i) p_1 \mid q_i$. \\
But since $q_i$ is prime, $p_1 = q_i$. \\
Divide both sides, and get two factorizations of $n/p_1$.  \\
This contradicts our inductive
hypothesis, so the theorem is proved.
\end{proof}

Unique factorization gives a method for computing GCD: \\
Factor both numbers, and then multiply out all their common factors 
(watch multiplicities). \\

Example:
100 vs. 120: \\
$100 = 2 \times 2 \times 5 \times 5$ \\
$120 = 2 \times 2 \times 2 \times 3 \times 5$ \\
Common factors (including multiplicities): $2$, $2$, $5$. \\
Product $2 \times 2 \times 5 = 20$ is GCD.

Taking min number of occurrences of each prime. \\

\subsection{Why do Proofs?}

\begin{itemize}
\item
Convince yourself that your reasoning is correct -- that you haven't
made mistakes.
\item
Convince others. 
\item
A good proof has considerable structure, like a good program.
Much of it can be reused for other related results (like a
well-written program).
\item
A proof pins down {\em why} something is true, so you can know whether
it will stay true when things change.
\item
A failure to prove something often reveals the reason it is false.
\end{itemize}

Program verification: proof that a program does the right thing.
\begin{itemize}
\item Pentium
\item Airbus A300 (earily version of control software had a bug that
  caused plane to head straight down if a certain configuration was reached)
\item Therac 25
\end{itemize}

In programming, the current state of the art is that people do not
actually prove correctness of running programs.
There has been a lot of research directed toward making this possible,
but it hasn't yet gotten far enough to be practical.
The problem is that the concepts that have to be reasoned about seem
too low-level, complicated in their details.

In contrast, people do know how to model programs/systems 
abstractly, and prove correctness of the abstract versions.
E.g., the {\em algorithm} used in a communication protocol can be
described formally, and its correctness proved.
But there is still a gap between what is verified and the actual code
that runs on real systems -- programmers implement algorithms in a
rather ad hoc manner, and errors can creep in there.
There isn't much available now to help programmers bridge this gap.

The high-level algorithm proofs are usually done as sketches.
Some are very complicated, and some errors have been found in
published proofs.
There is also considerable research in actually doing complete
algorithm proofs axiomatically, and having a computer tool (an
``automatic theorem-prover'') help in checking or even filling in the
low-level steps.
This sort of work is becoming practical.

Whether done by hand or with computer assistance, algorithm proofs are
of great help in getting your programs right (and understanding why).
I think this will be done much more in the future.
It will become an important part of quality assurance for programs.
It takes a lot of work to do it,
and you have to understand formal logic proofs before you do it.

Other examples:
\begin{itemize}
\item
Kaashoek's Orca system, for which Alan Fekete and I helped to verify
the main algorithm (and found a significant logical error in the
process of doing the proof).
\item 
Current chip designs -- companies like Intel, HP are now
investing in verification people and computer tools.
\item
Communication protocols, AT\&T. 
\item
Practical verification efforts are also beginning for real-time
process control systems, e.g., those systems that control nuclear
power plants and airplanes.  Still preliminary.
\end{itemize}

Program verification is a nice complement to testing -- testing can
often detect bugs quickly.  Verification is harder, but it does help
to find deeper logical mistakes.  And when you're done, you know there
are {\em no more} errors (which testing alone can never guarantee).

(From homework)

Likewise, unique factorization gives a method for computing LCM:
Factor both, then multiply the max number of occurrences of each
prime:

Example:
100 vs. 120: \\
Product $2 \times 2 \times 2 \times 3 \times 5 \times 5 = 600$ is LCM.

These observations lead to the following nice connection between GCD
and LCM:

\begin{theorem}
Let $a$, $b$ be positive integers.
Then $a b = \gcd{a}{b} \times \lcm{a}{b}$

Example:
100 vs. 120: \\
$100 \times 120 = 20 \times 600$\\
$2^2 \cdot 5^2 \times 2^3 \cdot 3 \cdot 5 = 2^2 \cdot 5 \times 2^3 \cdot 3 \cdot 5^2$
\end{theorem}

\begin{proof}
For each distinct prime in the prime factorizations,
the LHS uses the sum of occurrences in $a$ and $b$, \\
while the RHS uses the min plus the max occurrences. \\
Same (sum of two numbers is the same as their min plus their max). 
\end{proof}

\subsection{Algorithm Verification}

A final use of induction today -- verifying iterative algorithms.

Algorithm for multiplying $a \times b$, where $a$ and $b$ are
arbitrary length positive integers represented in binary, and result
is to be represented in binary. \\
Assume that we have integer addition available, \\
and can examine individual bits. \\
$b(k)$ denotes $k$th high order bit of $b$. \\
\\
Algorithm: \\
Maintain accumulator $\ms{acc}$, initially set to $a$. \\
Suppose that $b$ has $n$ bits. \\
For $k = 1$ to $n-1$ do: \\
if $b(k+1) = 0$ then $\ms{acc} := 2 \ms{acc}$ \\
else $\ms{acc} := 2 \ms{acc} + a$ \\
\\
At end, result is in $\ms{acc}$. \\
\\
Example: $a = 5$, $b = 13 = 1101$. \\
\begin{tabbing}
XXX\=XXX\=XXX\= \kill
$k$ \> $\ms{acc}$ \> $\ms{high}(b,k+1)$ \\
$0$ \> $5$        \> $1$ \\
$1$ \> $15$       \> $3 = 11$ \\
$2$ \> $30$       \> $6 = 110$ \\
$3$ \> $65$       \> $13 = 1101$ 
\end{tabbing}

How do we know this is correct?  \\
Can prove, by induction. \\
For every $k$, $0 \leq k \leq n-1$, $P(k)$, where \\
$P(k)$: After $k$ iterations, $\ms{acc}$ is equal to $a \times
\ms{high}(b,k+1)$. \\
\\
Writing $\ms{high}(b,m)$ for the integer defined by the $m$
highest-order bits of $b$.) \\
\\
BASE: $k = 0$. \\
The highest-order bit is $1$, so $\ms{high}(b,1) = 1$. \\
Initially, $\ms{acc}$ contains $a = a \times 1$, as needed. \\
INDUCTIVE STEP: \\
Assume for $k$.  After $k$ iterations, $\ms{acc}$ contains 
$a \times \ms{high}(b,k+1)$. \\
Show after one more iteration, $\ms{acc}$ contains $a \times
\ms{high}(b,k+2)$. \\
\\
Depends on examining the $k+1$st iterative step. \\
At this step, examine $k+2$nd bit of $b$. \\
Rule says if $0$, double, else double and add $a$. \\
Check cases to see this is the right thing to do: \\
If $0$, new desired number is just double the old. \\
If $1$, new desired number is double plus $a$, ... \\
\\
Why does this say that the final answer is correct? \\
\\
Specialize the result to $k = n-1$, $P(n-1)$: \\
After $n-1$ iterations, $\ms{acc}$ is equal to 
$a \times \ms{high}(b,n) = b$. 


\end{document}
% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
