\newlec
\hdc

 A statement $P(n)$ is proved true for all $n \in \mathbb{N}$ by induction.\\[2mm]
 
 In this proof, for some natural number $k$, we might:\\[2mm]
 
\begin{enumerate}[A)]
\item Prove $P(1)$. Prove $P(k)$. Prove $P(k+1)$.
\item Assume $P(1)$. Prove $P(k)$. Prove $P(k+1)$.
\item Prove $P(1)$. Assume $P(k)$. Prove $P(k+1)$.
\item Prove $P(1)$. Assume $P(k)$. Assume $P(k+1)$.
\item Assume $P(1)$. Prove $P(k)$. Assume $P(k+1)$.
\end{enumerate}

\vskip3em
\soln  Prove $P(1)$. Assume $P(k)$. Prove $P(k+1)$.

\ic{This is the 5 minute mark.}

\newpage

\ic{This is the last induction example - something slightly different.}

Prove that an $m \times n$ chocolate bar consisting of unit squares can be broken into unit squares using $$mn-1$$ breaks.
\ic{Mention below that the base case should be formally proven using induction but that we want. It will help to draw pictures as well. This is the first time that an induction question has two variables.}
\pf Let $m \in \mathbb{N}$ be fixed. We proceed by induction on $n$.
\vskip1em
\textbf{Base Case:} When $n=1$, we have an $m \times 1$ chocolate bar. This requires $m-1$ breaks to get $m$ unit squares (can prove formally by induction).
\vskip0.1em
\textbf{Inductive hypothesis:} Assume that an $m \times k$ chocolate bar can be broken into unit squares using $mk-1$ breaks for some $k \in \mathbb{N}$.
\vskip0.1em
\textbf{Inductive step:} For an $m \times (k+1)$ sized chocolate bar, we see that by breaking off the top row, gives a $m \times 1$ sized chocolate bar and a $m \times k$ sized chocolate bar. The first we know can be broken into unit squares using $m-1$ breaks (this was the base case) and the latter can be broken into unit squares using $mk-1$ breaks via the induction hypothesis. Hence, the total is
\[
1 + m-1 + mk-1 = m(k+1)-1
\]
as required. Hence, the claim is true for all $n \in \mathbb{N}$ by the Principle of Mathematical Induction.

%Wrote it twice...
%\newpage
%\ic{Only do this if you have time. This one is fine to skip. It's important to spend a lot of time on the Fundamental Theorem of Arithmetic.}
%One final induction question:
%\vskip1em
%\qn Exactly $mn-1$ breaks are always needed to break a $m \times n$ chocolate rectangle into unit squares.
%\vskip1em
%\pf Fix $m \in \mathbb{N}$. We use induction on $n$
%\begin{enumerate}
%\item When $n=1$, we have a $m\times 1$ rectangle. This needs $m-1$ breaks and this value is $mn-1$.
%\item Assume that a $m \times k$ chocolate bar requires $mk-1$ breaks.
%\item With a $m \times (k+1)$ chocolate bar, first break off a $m \times 1$ chocolate bar. This takes 1 break. Then with the $m \times 1$ chocolate bar, we use the $n=1$ case to see that this takes $m-1$ breaks. Lastly, the remaining $m \times k$ chocolate bar requires $mk-1$ breaks by the induction hypothesis. Hence, the total number of breaks is given by
%\begin{align*}
%1 + (m-1) + (mk-1) = m + mk - 1 = m(k+1)-1
%\end{align*}
%which is what we wanted to prove.
%\end{enumerate}



\ic{Again it helps to draw a picture above. We finish induction with the Fundamental Theorem of Arithmetic. Technically we can't prove it now but I will prove it up to Euclid's Lemma. This basically marks the midterm exam line in Fall2015 and Winter 2016.}

\ic{What you might want to do is do the following proof more informally and then return to it at the end of the term after more mathematical maturity has been developed and then redo this proof.}

\thm (Euclid's Lemma [PAD - Primes and Divisibility]) Suppose $a,b\in\mathbb{Z}$ and $p$ is a prime number. Show that if $p \mid ab$ then $p \mid a$ or $p \mid b$.
\vskip1em
\cor (Generalized Euclid's Lemma) Suppose $a_{1}, a_{2}, ..., a_{n} \in\mathbb{Z}$ and $p$ is a prime number. Show that if $p \mid a_{1}a_{2}...a_{n}$ then $p \mid a_{i}$ for some integer $1 \leq i \leq n$.
\vskip1em
\note The proof of this lemma will be delayed until after we do some techniques through greatest common divisors. For now we will take this for granted and prove our first major theorem of the course. The generalization follows immediately.
\vskip1em
\thm (Fundamental Theorem of Arithmetic) (UFT)
\vskip1em
Every integer $n > 1$ can be factored uniquely as a product of prime numbers, up to reordering.
\vskip1em
\note Prime numbers are just the product of a single number. 
\vskip1em
\pf \textbf{Existence.}
\vskip1em
Assume towards a contradiction that not every number can be factored into prime numbers. Let $n$ be the smallest such number (which exists by WOP). Then either $n$ is prime, a contradiction, or $n=ab$ with $1 < a,b < n$. However, since $a,b<n$, the numbers $a$ and $b$ can be written as a product of primes (since $n$ was minimal). Thus $n = ab$ is a product of primes, contradicting the definition of $n$.
\vskip1em
\textbf{Uniqueness}
\vskip1em
Assume towards a contradiction that there exists a natural number $n > 1$ such that 
\[
n = p_{1}p_{2}...p_{k} = q_{1}q_{2}...q_{m}
\]
where each $p_{i}$ and $q_{j}$ are primes (not necessarily distinct) and further assume that this $n$ is minimal (WOP). By definition, $p_{1} \mid n = q_{1}q_{2}...q_{m}$. Hence, by the generalized Euclid's Lemma, we see that $p_{1} \mid q_{j}$ for some $1 \leq j \leq m$. Hence, since $p_{1}$ and $q_{j}$ are prime numbers, we have that $p_{1} = q_{j}$. Without loss of generality, we may reorder the primes $q_{j}$ so that $q_{j}$ is the first prime, that is, $p_{1} = q_{1}$. Canceling out these primes gives
\[
N_{0} := p_{2}...p_{k} = q_{2}...q_{m}
\]
Now $N_{0}<n$ and so, the above representations must be equal up to reordering by the minimality of $n$. Hence, $k=m$ and we may reorder so that
\[
p_{\ell} = q_{\ell} \quad\quad \text{ for all $2 \leq \ell \leq k$}
\]
Multiplying $N_{0}$ by $p_{1}$ shows that the two representations of the factorizations of $n$ are the same up to reordering. This contradicts the existence of $n$ hence all numbers can be written uniquely as a product of primes up to reordering of primes.
\ic{This is a difficult proof. I would advise taking some time and really going through it. If you're lucky this will take you to just the 50 minute mark.}



