\documentstyle[11pt]{report}
\oddsidemargin=.35in
\textwidth=6.15in
\topmargin=-.25in
\textheight=8.75in
\begin{document}
\vspace*{1in}
\begin{center}
{\large\bf Chapter 1}\\
\vspace*{.1in}
{\small \em Minus times minus is plus.\\
The reason for this we need not discuss.}\\
\hspace*{1.75in}-W.H. Auden
\end{center}
\vspace*{.4in}
{\bf 1.1 Properties of Integers:} If $x$, $y$, and $z$ are arbitrary integers, then all of the following are true:
$
\begin{array}{cl}
(a) & x+y=y+x\\
(b) & (x+y)+z=x+(y+z) \\
(c) & xy=yx \\
(d) & x(yz)=(xy)z \\
(e) & x+0=x \\
(f) & 1 \cdot x =x \\
(g) & x(y+z)=xy+xz \\
(h) & -1\cdot x = -x\\
(i) & x \cdot 0 = 0
\end{array}
$
\vspace*{.3in}
{\bf 1.2 Mathematical Induction}
Strong and weak mathematical induction are two closely related proof techniques. Both are used to prove assertions about all positive integers. One begins either kind of induction argument by proving that the assertion in question is true for the integer 1. In the case of weak induction one proceeds by assuming that the assertion is true for some arbitrary integer, $n$, and proving that this assumption implies that the assertion is true for $n+1$. This establishes the truth of the assertion for {\em all} positive integers. The logic is simple. The first step establishes the result for $n=1$, the second step shows that if the assertion is true for some integer it is true for the next integer, combining these two establishes the truth of the assertion for $n=2$. Combining this conclusion with the second step establishes the truth of the assertion for $n=3$. Now, combining this conclusion with the second step \ldots, but you see where we're going. It's beautiful, it's simple, it's magic. A little like lifting yourself by your own bootstraps--or maybe watching an infinitely long row of dominoes falling. Strong induction differs from weak only slightly. In the second step one assumes that the assertion to be proved is true for {\em all} integers less than or equal some arbitrary $n$ and then proves that the truth of the assertion for $n+1$ follows. Sometimes this slightly stronger assumption makes the proof easier.
\vspace*{.1in}
\begin{center}
\begin{tabular}{llcl}
& {\it Basis Step} & {\it Inductive Step} & \\
{\it Weak (PMI):} & Show S($n_0$) is true & Show: S($n$)& $\Rightarrow$ S($n+1$) \\
& & & \\
{\it Strong (PSI):} & Show S($n_0$) is true & $ \left. \begin{array}{c}
\mbox{Show: S($n_0$)}\\
\mbox{S($n_0$+1)} \\
. \\
. \\
. \\
S($n$)
\end{array} \right\} $ & $\Rightarrow$ S($n+1$)
\end{tabular}
\end{center}
\vspace*{.15in}
PMI stands for principle of mathematical induction.
PSI stands for principle of strong induction. (This chart copied, more or less, from {\it Introduction to Mathematical Structures}, Steven Galovich.)
\vspace*{.15in}
\noindent {\bf Example 1.1} The sum of all odd numbers less than a particular integer is a perfect square. In particular,
\hspace*{2in} {\it 1+3+$\cdot\cdot\cdot$+(2n-1)=$n^2$}
\vspace*{.2in}
\begin{quote}
\noindent{Proof:} By weak induction.
Define S(n): 1+3+$\cdot\cdot\cdot$+(2n-1)=$n^2$.
{\it Basis Step:}
$$S(1):\,\,\,\, 1=1.$$
This is true. Therefore, S(1) holds.
{\it Inductive Step:} We show that for each positive integer k, S(k) implies S(k+1).
We assume (the induction hypothesis) $1+3+\ldots +(2k-1)=k^2$. Adding 2(k+1)-1 to each side of the previous equation gives: $$1+3+\ldots+(2k-1)+(2(k+1)-1)=k^2+2(k+1)-1.$$
A little bit of algebra gives:
$$1+3+\ldots+(2k-1)+(2k+1)=k^2+2k+1.$$
This is S(k+1).
Therefore, by PMI, 1+3+$\cdot\cdot\cdot$+(2n-1)=$n^2.$
\end{quote}
\vspace*{.1in}
The Hungarian peripatetic mathematician Paul Erd{\" o}s liked to talk about ``The Book." The Book has no physical existence, but he imagined it to contain all the ``best" proofs possible; those that immediately make clear why the statement they are proving is true. When you die, if you've been good, the Supreme Fascist ({\em i.e.,} god) lets you look at The Book.
A proof of this kind exists for the theorem we just proved by induction, and is as follows:
$$
\begin{array}{c}
\bigcirc
\end{array}
\hspace*{.4in}
\begin{array}{cc}
\bigcirc & \rule{.08in}{.08in}\\[6pt]
\rule{.08in}{.08in} & \rule{.08in}{.08in}
\end{array}
\hspace*{.4in}
\begin{array}{ccc}
\bigcirc & \rule{.08in}{.08in} & \triangle\\[6pt]
\rule{.08in}{.08in} & \rule{.08in}{.08in} & \triangle\\[6pt]
\triangle & \triangle & \triangle
\end{array}
\hspace*{.4in}
\ldots
\hspace*{.4in}
\begin{array}{cccccc}
\bigcirc & \rule{.08in}{.08in} & \triangle & \clubsuit & \diamondsuit & \spadesuit\\[6pt]
\rule{.08in}{.08in} & \rule{.08in}{.08in} & \triangle & \clubsuit & \diamondsuit & \spadesuit\\[6pt]
\triangle & \triangle & \triangle & \clubsuit & \diamondsuit & \spadesuit\\[6pt]
\clubsuit & \clubsuit & \clubsuit & \clubsuit & \diamondsuit & \spadesuit\\[6pt]
\diamondsuit & \diamondsuit & \diamondsuit & \diamondsuit & \diamondsuit & \spadesuit\\[6pt]
\spadesuit & \spadesuit & \spadesuit & \spadesuit & \spadesuit & \spadesuit
\end{array}
\hspace*{.4in}
\ldots
$$
\vspace*{.07in}
\hspace*{2in} First day, September 9, notes scribed by {\it Marie Hill}
\vspace*{.1in}
\noindent {\bf Well-Ordering Principle} If $S$ is a nonempty set of positive integers, then $S$ has a least element.
This is a useful axiom. Don't believe it? Check out the next proof!
\vspace*{.2in}
\noindent{\bf Theorem 1.1 The Division Algorithm} If $a$ and $b$ are integers, such that $b>0$, then there exist unique integers $q$ and $r$ such that $a=qb+r$ and $0\leq r**0\}$$
\begin{enumerate}
\item Proof that $S$ is not empty:
Since $b \geq 1$, if we take $x=-a$, we get:
$$a-(-a)b\geq 0$$
So,
$$a-(-a)b+b>0$$
$$a-(-a-1)b>0$$
For example, these are all members of the set, where $a=42$ and $b=5$:
\begin{center}
$42-(-1)5$\\
$42-(0)5$\\
$42-(1)5$\\
$42-(2)5$\\
\end{center}
By the Well-Ordering Principle, $S$ has a least element. We will call it $r$. There is some integer that will give this $r$. We will call it $q$:
$$a-qb=r$$
So,
$$a=qb+r$$
\vspace*{.1in}
\item Proof that $0\leq r**** 0\}$. $S$ is the set of all positive integers of the form $au + bv$ for fixed $a$ and $b$. Our first job is to show that $S$ is nonempty. If we let $u = a, v = b$, we have $a^2 + b^2$. Since $a^2 + b^2$ must be positive, it is in $S$. Now that we know we have a nonempty set, we can apply the Well-Ordering Principle, which tells us that $S$ must have a least element. Call this element $d$. We'll now show that $d = $gcd$(a, b)$.
Since $d \in S, d = ax_0 + by_0$ for some integers $x_0$, $y_0$. By the Division Algorithm, $a = qd+r, 0 \leq r < d$ for integers $q$ and $r$. Then
$$a-qd = r$$
Substituting for $d$,
$$a-q(ax_0+by_0) = r$$
$$a(1-qx_0) - qby_0 = r$$
Since we can write $r$ in this form, either $r \in S$ or $r = 0$. (Recall that $r$ cannot be negative). Now, $r$ is strictly less than $d$, and we chose $d$ to be the minimal element of $S$, so $r \not\in S$. Therefore, $r = 0$ and $d\mid a$.
A similar argument tells us $d\mid b$.
Now we know that $d$ is a common divisor of $a$ and $b$. It remains to be shown that $d$ is their {\em greatest} common divisor. To see this, suppose that $c$ is a greater common divisor: $c\mid a$ and $c\mid b$ with $c > d$. But since $d=ax_0 + by_0$, $c\mid d$ by 1.2.7. From this fact and 1.2.5, $c \leq d$. This contradicts our assumption that $c > d$.
\end{quote}
\noindent {\bf Corollary 1.3.1} If $a, b$ are integers, $a, b$ not both zero, then $T = \{ax + by \mid x, y \in {\cal Z} \}$ is precisely the multiples of gcd$(a,b)$.
\begin{quote}
\noindent Proof: We must show double containment.
All multiples of gcd$(a,b) \in T$: \newline
From the previous theorem, we can write gcd$(a,b)$ as $ax_0 + by_0$ for some $x_0, y_0$. Then any multiple of gcd$(a,b)$ can be written $k(ax_0 + by_0) = kax_0 + kby_0$, which is in $T$.
All elements of $T$ are multiples of gcd$(a,b)$: \newline
Take $ax_0 + by_0 \in T$. Let $g = $gcd$(a,b)$. Then, since $g$ divides both $a$ and $b$, Theorem 1.2.7 tells us that $g$ divides $ax_0 + by_0$ as well. So $ax_0 + by_0$ is a multiple of gcd$(a,b)$.
\end{quote}
\vspace*{.08in}
\noindent {\bf Definition} Two integers are {\em relatively prime} if their greatest common divisor is 1.
\vspace*{.08in}
\noindent {\bf Corollary 1.3.2} (Euclid's lemma) If $a\mid bc$ and gcd$(a,b) = 1$, then $a\mid c$. \\
\begin{quote}
Proof: By the previous theorem, $\exists x, y$ such that
$$1 = ax + by.$$
$$\mbox{or, } c = acx + bcy$$
Since $a\mid ac$ and $a\mid bc$, we can use Theorem 1.2.7 to say that $a\mid c$.
\end{quote}
\vspace*{.08in}
\noindent {\bf Theorem 1.4} (The Euclidean Algorithm) Given two integers $x$ and $y$, with $x > y$, use the following process to find gcd$(x,y)$:
$$x=q_1y+r_1$$
$$y=q_2r_1+r_2$$
$$r_1=q_3r_2+r_3$$
$$...$$
$$r_{k-1}=q_{k+1}r_k+r_{k+1}$$
$$r_k=q_{k+2}r_{k+1}+0$$
The process continues until we have a remainder of zero; gcd$(x,y)$ is the last non-zero remainder, $r_{k+1}$.
\begin{quote}
Proof: We'll first show that $r_{k+1}$ is a divisor of $x$ and $y$, and then show that it is the greatest common divisor. Finally, we'll show that the algorithm must terminate.
From the last line, $r_{k+1} \mid r_k$, so r$_{k+1} \mid q_{k+1} r_k$. Also, $r_{k+1} \mid r_{k+1}$. Then from Theorem 1.2.7 and the next-to-last line, $r_{k+1} \mid r_{k-1}$. We can then use Theorem 1.2.7 on each preceding line until we've shown that $r_{k+1}$ divides each of the remainders, as well as $x$ and $y$. This shows that $r_{k+1}$ is a common divisor of $x$ and $y$.
Now suppose that $x$ and $y$ have a greater common divisor, $z$. If $z$ divides $x$ and $y$, then, by the first line and Theorem 1.2.7, it must divide $r_1$. Given this, $z$ must also divide $q_2 r_1$, so the second line and 1.2.7 tell us that that $z\mid r_2$. Eventually, we will find that $z\mid r_{k+1}$. But $z > r_{k+1}$, which is a contradiction. Therefore, $r_{k+1}$ must be the greatest common divisor of $x$ and $y$.
We still need to show that we are guaranteed an eventual remainder of zero. This occurs because of the restrictions on $r$ in the division algorithm. The division algorithm states that any integer can be written in the form $qb + r$, with $0\leq r < b$. This means that our remainders decrease with each step and are bounded below by zero. They must eventually hit zero.
\end{quote}
\vspace*{.08in}
The Euclidean Algorithm provides us with a tool for expressing the gcd$(a,b)$ as the linear combination guaranteed to exist by Theorem 1.3. We can work backwards and rearrange terms as follows:
$$r_{k+1}=r_{k-1}-q_{k+1}r_k$$
$$ =r_{k-1}-q_{k+1}[r_{k-2}-q_kr_{k-1}]$$
$$ =r_{k-1}(1-q_k)-q_{k+1}r_{k-2}$$
Then substitute for r$_{k-1}$, etc, until what is left is an expression in terms of $x$ and $y$.
\vspace*{.08in}
\noindent Tantalizing Tidbit: Math and stand-up comedy have a lot in common.
Let's do a specific example...
\vspace*{.08in}
\noindent {\bf Example 1.2} Find gcd(963,657).
$$963=1\times 657 + 306$$
$$657=2\times 306 + 45$$
$$306=6\times 45 + 36$$
$$45=1\times 36 + 9$$
$$36=4\times 9 +0$$
So gcd(963,657) = 9.
\vspace*{.08in}
\noindent {\bf Example 1.3} Express 9 as a linear combination of 963 and 657.
\begin{eqnarray*}
9& =& 45-1\times 36 \\
& = & 45-(306 - 6\times 45) \\
& = & 7\times 45 - 306 \\
& =& 7(657 - 2\times 306) - 306 \\
& = & 7\times 657 - 15\times 306 \\
& =& 7\times 657 - 15(963 - 1\times 657) \\
9 & = & 22\times 657 - 15\times 963 \\
\end{eqnarray*}
\vspace*{2in}
\hspace*{1in} Second day, September 11, notes scribed by {\em Krista Caner} and {\em Mimi Cukier}
\end{document}**