\documentclass{article}
\input{preamble.tex}
\usepackage{url}
\title{Day 13}
\date{Friday June 8, 2012}
\newcommand{\df}{\textbf}
\def\Display{\@empty}
\newcommand{\Hide}[2]{\ifx \Display\undefined \strut \\ \vspace{#1} \\ \strut \else {\color{blue} #2} \fi }
\begin{document}
\maketitle
\section{Motivating Example: Modular Arithmetic}
We are going to define a very useful equivalence relation that you have problem seen before. First we need some background however:
\begin{lem}
Fix $n > 0$, and $a,b,c\in\Z$. If $a + b$ is divisible by $n$ and $a$ is divisible by $n$ then $b$ is divisible by $n$.
\end{lem}
\begin{proof}
Suppose that $a+b$ and $a$ are divisible by $n$. Then we get $k$ and $l$ in the integers such that $a+b = kn$ and $a=ln$ Substituting, we get $ln + b = kn$, ie. we have $b = n(k-l)$, which of course means $b$ is divisible by $n$.
\end{proof}
\begin{dfn}
We say $\E ! x \st \phi(x)$ to stand for ``there exists a unique $x$ such that $\phi(x)$''; that is there is an $x$, and it is the only one with that property. To express this using the notation we already know:
\[
(\E ! x \st \phi(x)) \iff (\E x \st \left(\phi(x) \oand ( \A y \st \phi(y) \to x=y) \right))
\]
That is, there is an $x$ that satisfies the property, and if there were any other $y$ that satisfies it, then it is the same as $x$
\end{dfn}
\begin{thm}[Division Algorithm]
\[
\A d\in \Z^+ \st \A n\in \Z \stt \E! q,r\in\Z \stt ( (n = dq + r) \oand (0 \leq r < d) )
\]
\end{thm}
\begin{proof}
Fix $d\in\Z^+$. Our strategy will be to show that there is a $q$ and an $r$ and then show they must be unique.
We will prove the statement for $n\in \N$; it is not hard to extend this to all $n\in\Z$, and you can think about why it is true.
We do many base cases in one step: for any $n < d$, we can be done instantly as we can take $q = 0$ and $r = n$. This obviously satisfies the properties.
So, for our induction hypothesis, let $n$ be an arbitrary natural such that $n\geq d$. Assume that we can get integers $q_m$ and $r_m$ for all $m < n$ such that $m = d q_m + r_m$ and $0 \leq r_m < d$.
Now, we seek to show it's true for $n$. Well, consider $n - d$. As $n\geq d$, we know this is a natural number smaller than $n$. Thus we get $q_{n-d}$ and $r_{n-d}$ by our induction hypothesis. So $0\leq r_{n-d}< d$ and $n-d = dq_{n-d} - r_{n-d}$. Adding $d$ to both sides, we get $n = d(q_{n-d} + 1) - r_{n-d}$. So $q = q_{n-d} + 1$ and $r = r_{n-d}$ work.
Thus by induction it is true for all $n\in \N$.
Now we show uniqueness. Suppose we had two sets of $q$'s and $r$'s that satified this property. Then we would have
\[
q_1 d + r_1 = n = q_2 + r_2
\]
for some $q_1,q_2,r_1,r_2\in\Z$ where $0\leq r_1