\input{header.tex} 
\togglefalse{IC} 
\begin{document} 
\textbf{Lecture 2} \vskip1em
\textbf{Stewart's Theorem}
Let $ABC$ be a triangle with $AB=c$, $AC=b$ and $BC=a$.\\
If $P$ is a point on $BC$ with $BP=m$, $PC=n$ and $AP=d$,\\
then $dad + man = bmb + cnc$.


\begin{center}
\includegraphics[scale=0.50]{StewartsTheorem.png}
\end{center}

\begin{proof}{\textbf{Proof A}
\vspace{1em}
\[c^2=m^2+d^2-2md\cos{\theta} \] 
\[b^2=n^2+d^2-2nd\cos{\theta'} \]
\[b^2=n^2+d^2+2nd\cos{\theta} \]
\[\frac{m^2-c^2+d^2}{-2md} = \frac{b^2-n^2-d^2}{2nd} \]
\[nc^2-nm^2-nd^2=-mb^2+mn^2+md^2\]
\[nc^2-mb^2=mn^2+md^2+nm^2+nd^2\]
\[cnc+bmb=nm(n+m)+d^2(m+n)\]
\[cnc+bmb=man+dad\]}
\end{proof}

\note Unclear what $\theta$ and $\theta'$ are. No explanation. Division by variables should be careful about 0.

\newpage
\hdc 
\textbf{Stewart's Theorem}
Let $ABC$ be a triangle with $AB=c$, $AC=b$ and $BC=a$.\\
If $P$ is a point on $BC$ with $BP=m$, $PC=n$ and $AP=d$,\\
then $dad + man = bmb + cnc$.

\begin{center}
\includegraphics[scale=0.50]{StewartsTheorem.png}
\end{center}


\begin{proof}{\textbf{Proof B}
\vskip1em
\noindent The Cosine Law on $\triangle APB$ tells us that \[c^2=m^2+d^2-2md\cos{(\angle APB)}.\]
Subtracting $c^2$ from both sides gives \[0=-c^2+m^2+d^2-2md\cos{(\angle APB)}.\]
Adding $2md\cos{\angle APB}$ to both sides gives \[2md\cos{(\angle APB)}=-c^2+m^2+d^2.\]
Dividing both sides by $2md$ gives \[ \cos{(\angle APB)} = \frac{-c^2+m^2+d^2}{2md}.\]
Now, the Cosine Law on $\triangle APC$ tells us that \[b^2=n^2+d^2-2nd\cos{\angle APC}.\]
Since $\angle APC$ and $\angle APB$ are supplementary angles, then \[ \cos{\angle APC} = \cos{(\pi - \angle APB)} = -\cos{(\angle APB)}.\]
Substituting into our previous equation, we see that \[b^2=n^2+d^2+2nd\cos{\angle APB}.\]
Subtracting $n^2$ from both sides gives \[b^2-n^2=d^2+2nd\cos{(\angle APB)}.\]
Then subtracting $d^2$ from both sides gives \[b^2-n^2-d^2=2nd\cos{(\angle APB)}.\]
Dividing both sides by $2nd$ gives \[\frac{b^2-n^2-d^2}{2nd}=\cos{(\angle APB)}.\]
Now we have two expressions for $\cos{(\angle APB)}$ and equate them to yield
\[ \frac{-c^2+m^2+d^2}{2md}=\frac{b^2-n^2-d^2}{2nd}.\]
Multiplying both sides by $2mnd$ shows us that
\[ n(-c^2+m^2+d^2)=m(b^2-n^2-d^2).\]
Next we distribute to get
\[ -nc^2+nm^2+nd^2=mb^2-mn^2-md^2.\]
Adding $nc^2+mn^2+md^2$ to both sides gives
\[ nm^2+mn^2+nd^2+md^2=mb^2+nc^2.\]
Factoring twice gives:
\[ nm(m+n)+d^2(m+n)=mb^2+nc^2.\]
Since $P$ lies on $BC$, then $a=m+n$ so we substitute to yield
\[ nma+d^2a=mb^2+nc^2.\]
Finally, we can rewrite this as $bmb+cnc=dad+man. $.}
\end{proof}

\note Too verbose. Can shorten the explanation by not writing out every algebraic manipulation.

\newpage
\hdc
\textbf{Stewart's Theorem}
Let $ABC$ be a triangle with $AB=c$, $AC=b$ and $BC=a$.\\
If $P$ is a point on $BC$ with $BP=m$, $PC=n$ and $AP=d$,\\
then $dad + man = bmb + cnc$.

\begin{center}
\includegraphics[scale=0.50]{StewartsTheorem.png}
\end{center}


\begin{proof}{\textbf{Proof C}
\vskip1em
\noindent Using the Cosine Law for supplementary angles $\angle APB$ and $\angle APC$, and then
clearing denominators and simplifying gives $dad + man = bmb + cnc$ as required. }
\end{proof}

\note No details given. Need to provide some evidence of algebraic manipulation.

\newpage
\hdc
\textbf{Stewart's Theorem}
Let $ABC$ be a triangle with $AB=c$, $AC=b$ and $BC=a$.\\
If $P$ is a point on $BC$ with $BP=m$, $PC=n$ and $AP=d$,\\
then $dad + man = bmb + cnc$.


\begin{center}
\includegraphics[scale=0.50]{StewartsTheorem.png}
\end{center}



\begin{proof}{\textbf{Proof D}
\vskip1em
\noindent The Cosine Law on $\triangle APB$ tells us that \[c^2=m^2+d^2-2md\cos{\angle APB}.\]
Similarly, the Cosine Law on $\triangle APC$ tells us that \[b^2=n^2+d^2-2nd\cos{\angle APC}.\]
Since $\angle APC$ and $\angle APB$ are supplementary angles, we have
\[b^2=n^2+d^2+2nd\cos{\angle APB}.\]
Equating expressions for $\cos{\angle APB}$ yields
\[ \frac{-c^2+m^2+d^2}{2md}=\frac{b^2-n^2-d^2}{2nd}.\]
Clearing the denominator and rearranging gives
\[ nm^2+mn^2+nd^2+md^2=mb^2+nc^2.\]
Factoring yields
\[ mn(m+n)+d^{2}(m+n)=mb^2+nc^2.\]
Substituting $a=(m+n)$ gives $dad + man = bmb + cnc$ as required. }
\end{proof}

\note Overall a good proof. Perhaps some more information on why the supplementary angle step holds would be good. Justifying why division by a variable is allowed (that is, nonzero variables) would be a plus and perhaps labeling previous equations to reference in the future would help this proof slightly. This would be an acceptable answer regardless of these minor quibbles.

\ic{This concludes up to the 46-48 minute mark}

\newpage
\hdc

Find the flaw in the following arguments:
\begin{enumerate}
\item For $a,b \in \bR$,
\begin{align*}
a &= b\\
a^{2} &= ab\\
a^{2}-b^{2} &= ab-b^{2}\\
(a-b)(a+b) &= b(a-b)\\
a+b &= b && \text{ERROR: division by 0 since $a=b$}\\
b+b &= b\\
2b &= b\\
2 &= 1
\end{align*}
\ic{This is the end of lecture 2. Begin Lecture 3 with the next two examples.}
\vskip2em
\item \begin{align*}
x &= \frac{\pi+3}{2}\\
2x &= \pi + 3\\
2x(\pi-3) &= (\pi+3)(\pi-3)\\
2\pi x - 6x &= \pi^{2} - 9\\
9-6x &= \pi^{2} - 2\pi x\\
9-6x + x^{2} &= \pi^{2} - 2\pi x +x^{2}\\
(3-x)^{2} &= (\pi-x)^{2}\\
3-x &= \pi-x\\
3 &= \pi
\end{align*}
\vskip2em
\item For $x \in \bR$,
\begin{align*}
(x-1)^{2} &\geq 0\\
x^{2} - 2x + 1 &\geq 0\\
x^{2} + 1 &\geq 2x \\
x+\tfrac{1}{x} & \geq 2
\end{align*}
\end{enumerate}
\vskip3em
\newpage\textbf{Lecture 3} \vskip1em
\thispagestyle{empty}
Find the flaw in the following arguments:
\begin{enumerate}
\item (Last class)
\vskip2em
\item \begin{align*}
x &= \frac{\pi+3}{2}\\
2x &= \pi + 3\\
2x(\pi-3) &= (\pi+3)(\pi-3)\\
2\pi x - 6x &= \pi^{2} - 9\\
9-6x &= \pi^{2} - 2\pi x\\
9-6x + x^{2} &= \pi^{2} - 2\pi x +x^{2}\\
(3-x)^{2} &= (\pi-x)^{2}\\
3-x &= \pi-x && \text{ERROR: $|3-x| = |\pi-x|$}\\
3 &= \pi
\end{align*}
\vskip2em
\item For $x \in \bR$,
\begin{align*}
(x-1)^{2} &\geq 0\\
x^{2} - 2x + 1 &\geq 0\\
x^{2} + 1 &\geq 2x \\
x+\tfrac{1}{x} & \geq 2 && \text{ERROR: Division by 0. Also flip sign if $x < 0$}
\end{align*}
\end{enumerate}

\ic{This is the 5 minute mark \vskip1em}

\newpage

\ex Let $x,y \in \mathbb{R}$. Prove that 
$$
 5x^{2}y - 3y^{2} \leq x^{4} + x^{2}y + y^{2}
$$
\pf Since $0 \leq (x^{2}-2y)^{2}$, we have
\begin{align*}
0 &\leq (x^{2}-2y)^{2}\\
0 &\leq x^{4} - 4x^{2}y + 4y^{2}\\
5x^{2}y - 3y^{2} &\leq x^{4} - 4x^{2}y + 4y^{2} + 5x^{2}y - 3y^{2}\\
5x^{2}y - 3y^{2} &\leq x^{4} + x^{2}y + y^{2}\\
\end{align*}

Alternate proof:

\begin{align*}
\text{RHS} &= x^{4} + x^{2}y + y^{2}\\
&= x^{4} + x^{2}y + y^{2} + 5x^{2}y  - 5x^{2}y +3y^{2} - 3y^{2}\\
&= x^{4} - 4x^{2}y + 4y^{2} + 5x^{2}y - 3y^{2} \\
&= (x^{2}-2y)^{2} + 5x^{2}y - 3y^{2}\\
&\geq 5x^{2}y - 3y^{2}\\
&= \text{LHS}
\end{align*}

\note To discover this proof. Play around with the given inequality on a napkin (rough work). Manipulate it until you reach a true statement. Then write your proof starting with the given true statement to reach the desired inequality. Notice that starting with the given inequality is NOT valid since you do not know whether or not it is true to begin with. New truth can only be derived from old truth. (Analogy: You need a solid foundation to build a house). Here is a sample of my napkin work:

\begin{align*}
 5x^{2}y - 3y^{2} &\leq x^{4} + x^{2}y + y^{2}\\
0 &\leq x^{4} + x^{2}y + y^{2} -  5x^{2}y + 3y^{2} \\
0 &\leq x^{4} -4 x^{2}y + 4y^{2} \\
0 &\leq (x^{2}-2y)^{2}.
\end{align*}

The last statement is clearly true thus so long as I can reverse my steps, I have a valid proof. Note that you must write the proof starting with the true statement and deriving the new truth statements. 

\ic{This is the 20 minute mark}

Throughout the remainder of this lecture, let $A$, $B$, $C$ be statements. 
\vskip1em
\defn $\neg A$ is NOT $A$. 

\begin{center}
  \begin{tabular}{ c | c }
    \hline
   $A$ & $\neg A$ \\
   \hline
   T & F \\
   F & T
  \end{tabular}
\end{center}

\note: Truth tables can be used both as definitions of operators (as was done here) or in proofs (as will be done later). Make sure you understand the difference.
\vskip1em
\defn $A \wedge B$ is $A$ and $B$. Further, $A \vee B$ is $A$ or $B$.

\begin{center}
  \begin{tabular}{ c | c | c | c }
    \hline
   $A$ & $B$ & $A \wedge B$ & $A \vee B$ \\
   \hline
   T & T & T & T\\
   T & F & F & T\\
   F & T & F & T\\   
   F & F & F & F\\
  \end{tabular}
\end{center}

\ic{This is the 26 minute mark}

\newpage
\hdc

Which of the following are true?
\begin{itemize}
\item $\pi$ is irrational and $3 > 2$ 									%\hfill \nb{true}
\item 10 is even and $1=2$ 										%\hfill \nb{false}
\item 7 is larger than 6 or 15 is a multiple of 3 							%\hfill \nb{true}
\item $5 \leq 6$ 												%\hfill \nb{true}
\item 24 is a perfect square or the vertex of parabola $x^2+2x+3$ is $(1,1)$ 	%\hfill \nb{false}
\item 2.3 is not an integer 											%\hfill \nb{true}
\item 20\% of 50 is not 10 											%\hfill \nb{false}
\item $7$ is odd or $1$ is positive and $2 \neq 2$						%\hfill \nb{true} (and gets evaluated first).
\end{itemize}
\vskip3em
\newpage\textbf{Lecture 3} \vskip1em
In the following, identify the hypothesis, the conclusion and state whether the statement is true or false.

\begin{itemize}
\item If $\sqrt{2}$ is rational then $2 < 3$									%\hfill \nb{true}
\item If (1+1=2) then $5\cdot2 = 11$ 											%\hfill \nb{false}
\item	If C is a circle, then the area of C is $\pi r^{2}$							%\hfill \nb{true}
\item If $5$ is even then $5$ is odd										%\hfill \nb{true}
\item If $4-3=2$ then $1+1=3$											%\hfill \nb{true}
\end{itemize}
\vskip3em
\newpage\textbf{Lecture 4} \vskip1em
\ic{Clicker Questions to start every 4th lecture.}
Suppose $A$, $B$ and $C$ are all true statements.\\[2mm]
The compound statement $(\neg A) \vee (B \wedge \neg C)$ is %NOT $A$ OR $(B$ AND NOT $C)$ is
\begin{enumerate}[A)]
\item True 
\item False 
\end{enumerate}
\vskip3em
\newpage\textbf{Lecture 5} \vskip1em
Prove the following. Suppose that $x,y \geq 0$. Show that $x=y$ if and only if $\frac{x+y}{2} = \sqrt{xy}$. 
\vskip3em
\newpage\textbf{Lecture 6} \vskip1emDescribe the following sets using set-builder notation:

\begin{enumerate}
\item Set of even numbers between 5 and 14 (inclusive).
\vskip2.75em
\item All odd perfect squares.
\vskip2.75em
\item Sets of three integers which are the side lengths of a (non-trivial) triangle.
\vskip2.75em
\item All points on a circle of radius 8 centred at the origin.
\end{enumerate}
\vskip3em
\newpage\textbf{Lecture 7} \vskip1em\ex Prove that there is an $x \in \mathbb{R}$ such that $\frac{x^{2} + 3x - 3}{2x + 3} = 1$.
\vskip3em
\newpage\textbf{Lecture 7} \vskip1em
\ex Show that for each $x \in \mathbb{R}$, we have that $x^{2} + 4x + 7 > 0$.
\vskip3em
\newpage\textbf{Lecture 7} \vskip1emSometimes $\forall$ and $\exists$ are hidden! If you encounter a statement with quantifiers, take a moment to make sure you understand what the question is saying/asking.
\vskip0.1em
Examples:
\begin{enumerate}
\item $2n^{2} + 11n + 15$ is never prime when $n$ is a natural number.
\item If $n$ is a natural number, then $2n^{2} + 11n + 15$ is composite.
\item $\frac{m-7}{2m+4} = 5$ for some integer $m$.
\item $\frac{m-7}{2m+4} = 5$ has an integer solution.
\end{enumerate}

\vskip3em
\newpage\textbf{Lecture 8} \vskip1em
Consider the following statement.
\[ \{2k : k \in \mathbb{N}\} \supseteq \{n \in \mathbb{Z} : 8 \mid (n+4)\} \]

A well written and correct direct proof of this statement could begin with

\begin{enumerate}[A)]
\item We will show that the statement is true in both directions.
\item Assume that $8 \mid 2n$ where $n$ is an integer.
\item Let $m \in \{n \in \mathbb{Z} : 8 \mid (n+4)\} $. %Correct
\item Let $m \in \{2k: k \in \mathbb{N}\}$.
\item Assume that $8 \mid (2k+4)$.
\end{enumerate}

\vskip3em
\newpage\textbf{Lecture 8} \vskip1em
Notes:
\vskip1em
\begin{enumerate}
\item A single counter example proves that $(\forall x \in S, P(x))$ is false.
\vskip0.1em
Claim: Every positive even integer is composite.
\vskip0.1em
 This claim is false since $2$ is even but $2$ is prime.
\item A single example does not prove that $(\forall x \in S, P(x))$ is true.
\vskip0.1em
Claim: Every even integer at least 4 is composite. 
\vskip0.1em
This is true but we cannot prove it by saying "6 is an even integer and is composite." We must show this is true for an arbitrary even integer $x$. (Idea: $2 \mid x$ so there exists a $k \in \mathbb{N}$ such that $2k=x$ and $k \neq 1$.)
\item A single example does show that $(\exists x \in S, P(x))$ is true.
\vskip0.1em
Claim: Some even integer is prime. 
\vskip0.1em
This claim is true since $2$ is even and $2$ is prime.
\item What about showing that $(\exists x \in S, P(x))$ is false?
\vskip0.1em
Idea:  $(\exists x \in S, P(x))$ is false  $\equiv \forall x\in S, \neg P(x)$ is true. This idea is central for proof by contradiction which we will see later.
\end{enumerate}
\vskip3em
\newpage\textbf{Lecture 8} \vskip1em
\thispagestyle{empty}
Which of the following are true?
\begin{enumerate}
\item $\forall x\in\mathbb{R}, \forall y \in \mathbb{R}, x^{3}-y^{3}=1$
\item $\exists x\in\mathbb{R}, \exists y \in \mathbb{R}, x^{3}-y^{3}=1$
\item $\forall x\in\mathbb{R}, \exists y \in \mathbb{R}, x^{3}-y^{3}=1$
\item $\exists x\in\mathbb{R}, \forall y \in \mathbb{R}, x^{3}-y^{3}=1$
\end{enumerate}

\vskip3em
\newpage\textbf{Lecture 8} \vskip1em
List all elements of the set:
\small{
\begin{align*}
\{ n\ \in \mathbb{Z} &: n > 1 \wedge ((m \in \mathbb{Z} \wedge m > 0 \wedge m \mid n) \Rightarrow (m=1 \vee m=n))\}  \cap \{n \in \mathbb{Z} : n \mid 42\} 
\end{align*}}

\vskip3em
\newpage\textbf{Lecture 9} \vskip1em
Rewrite the following using as few English words as possible.

\begin{enumerate}
\item No multiple of 15 plus any multiple of 6 equals 100.
\vskip1em
\item Whenever three divides both the sum and difference of two integers, it also divides each of these integers.
\end{enumerate}

\vskip3em
\newpage\textbf{Lecture 9} \vskip1em
Write the following statements in (mostly) plain English.
\begin{enumerate}
\item \small{$\forall m \in \mathbb{Z},((\exists k \in \mathbb{Z}, m = 2k) \Rightarrow (\exists \ell \in \mathbb{Z}, 7m^{2} + 4 = 2\ell))$ }
\vskip1em
\item $n \in \mathbb{Z} \Rightarrow (\exists m \in \mathbb{Z}, m > n)$
\end{enumerate}

\vskip3em
\newpage\textbf{Lecture 10} \vskip1em
\ex Prove that if $x \in \mathbb{R}$ is such that $x^{3} + 7x^{2} < 9$, then $x < 1.1$.

\vskip3em
\newpage\textbf{Lecture 10} \vskip1emHow many years has it been since the Toronto Maple Leafs have won the Stanley Cup?

\begin{enumerate}[A)]
\item -3
\item 49
\item 1000000
\item 1500
\end{enumerate}

\vskip3em
\newpage\textbf{Lecture 10} \vskip1em
\ic{The following is an example of reading proofs and seeing the difference between the direct proofs and proofs by contradiction.}

\textbf{Example:} Let $n \in \mathbb{Z}$ such that $n^{2}$ is even. Show that $n$ is even.

\vskip1em

\textbf{Direct Proof:} As $n^2$ is even, there exists a $k \in \mathbb{Z}$ such that $$n\cdot n = n^{2} = 2k.$$ Since the product of two integers is even if and only if at least one of the integers is even, we conclude that $n$ is even. 

\vskip1em

\textbf{Proof By Contradiction:} Suppose that $n^{2}$ is even. Assume towards a contradiction that $n$ is odd. Then there exists a $k \in \mathbb{Z}$ such that $n = 2k+1$. Now, $$n^{2} = (2k+1)^{2} = 4k^{2} + 4k + 1 = 2(2k^{2} + 2k) + 1.$$ Hence, $n^2$ is odd, a contradiction since we assumed in the statement that $n^{2}$ is even. Thus $n$ is even.

\vskip3em
\newpage\textbf{Lecture 10} \vskip1em
\ic{It's conceivable that you might want to write out the first proof and then display the other two proofs. Feel free to ignore these proofs as well. I do however recommend the first one.}

\textbf{Example:} Prove that $\sqrt{2}$ is irrational.
\vskip1em
\textbf{Proof:} Assume towards a contradiction that $\sqrt{2} = \frac{a}{b} \in \mathbb{Q}$ with $a,b \in \mathbb{N}$ (Think: Why is it okay to use $\mathbb{N}$ instead of $\mathbb{Z}$?). 
\vskip1em

 \textbf{Proof 1:} Assume further that $a$ and $b$ share no common factor (otherwise simplify the fraction first). Then $2b^{2} = a^{2}$. Hence $a$ is even. Write $a = 2k$ for some integer $k$. Then $2b^{2} = a^{2} = (2k)^{2} = 4k^{2}$ and canceling a 2 shows that $b^{2} = 2k^{2}$. Thus $b^{2}$ is even and hence $b$ is even. This implies that $a$ and $b$ share a common factor, a contradiction.

\vskip1em
\textbf{Proof 2 (Well Ordering Principle):} Let $$S = \{ n \in \mathbb{N}: n\sqrt{2} \in \mathbb{N}\}.$$ Since $b \in S$, we have that $S$ is nonempty. By the Well Ordering Principle, there must be a least element of $S$, say $k$. Now, notice that $$k(\sqrt{2}-1) = k\sqrt{2} - k \in \mathbb{N}$$
 (positive since $\sqrt{2} > \sqrt{1} = 1$). Further, $$k(\sqrt{2}-1)\sqrt{2} = 2k - k\sqrt{2} \in \mathbb{N}$$ and so $k(\sqrt{2}-1)  \in S$. However, $k(\sqrt{2}-1) < k$ which contradicts the definition of $k$. Thus, $\sqrt{2}$ is not rational.
 
 \vskip1em
 
 \textbf{Proof 3 (Infinite Descent):}  Isolating from $\sqrt{2} = \frac{a}{b} $, we see that $2b^{2} = a^{2}$. Thus $a^{2}$ is even hence $a$ is even. Write $a = 2k$ for some integer $k$. Then $2b^{2} = a^{2} = (2k)^{2} = 4k^{2}$. Hence $b^{2} = 2k^{2}$ and so $b$ is even. Write $b = 2\ell$ for some integer $\ell$. Then repeating the same argument shows that $k$ is even. So $a = 2k = 4m$ for some integer $m$. Since we can repeat this argument indefinitely and no integer has infinitely many factors of $2$, we will (eventually) reach a contradiction. Thus, $\sqrt{2}$ is not rational.

\vskip3em 
\newpage\textbf{Lecture 11} \vskip1em\thm (Division Algorithm) Let $a \in \mathbb{Z}$ and $b \in \mathbb{N}$. Then $\exists! q,r\in\mathbb{Z}$ such that $a = bq + r$ where $0 \leq r < b$.
\vskip1em
\pf Existence: Use the Well Ordering Principle on the set
\[
S = \{ a - bq: a-bq \geq 0 \wedge q \in \mathbb{Z}\}
\]
Uniqueness:
\vskip1em
Suppose that $a = q_1 b+r_1$ with $0 \leq r_1 < b$. Also, suppose that $a = q_2 b+r_2$ with
$0\leq r_2 < b$ and $r_1\neq r_2$. Without loss of generality, we can assume $r_1 < r_2$.
\ic{Introduce the acronym WLOG. Explain that if two integers are not equal, then one must be bigger than the other and the proof is symmetric depending if $r_{1} < r_{2}$ or $r_{2} < r_{1}$}
Then $0 < r_2 - r_1 < b$ and $(q_1 - q_2)b=r_2 -r_1$.
\ic{Take the difference of the two $a$ values. Given that $0 \leq r_{1} , r_{2} < b$, the biggest value of $r_{2} - r_{1}$ is $b$.}
Hence $b \mid (r_2 -  r_1)$. By Bounds By Divisibility, $b \leq r_2 - r_1$ which contradicts the fact that $r_2 -  r_1 < b$.
\ic{This is a contradiction. Notice that we don't need $|b|$ as in (BBD) since $b \in \mathbb{N}$. }
Therefore, the assumption that $r_1\neq r_2$ is false and in fact $r_1 = r_2$. But then $(q_1- q_2)b=r_2- r_1$ implies $q_1 =q_2$.

\vskip3em
\newpage\textbf{Lecture 12} \vskip1em
Let $n \in \mathbb{Z}$. Consider the following implication.\\[2mm]

\hspace{10mm} If ($\forall x \in \mathbb{R},~x \leq 0~\vee~x+1 > n$), then $n=1$.\\[2mm]

The contrapositive of this implication is

\begin{enumerate}[A)]
\item If $n=1$, then ($\forall x \in \mathbb{R},~x \leq 0~\vee~x+1 > n$).
\item If $n=1$, then ($\exists x \in \mathbb{R},~x > 0~\wedge~x+1 \leq n$).
\item If $n\neq 1$, then ($\exists x \in \mathbb{R},~x \geq 0~\wedge~x+1 < n$).
\item If $n\neq 1$, then ($\forall x \in \mathbb{R},~x \leq 0~\vee~x+1 > n$).
\item None of the above.												
\end{enumerate}
\vskip3em
\newpage\textbf{Lecture 12} \vskip1em\ic{I suggest letting students work on these and either getting them to write solutions on the board or at least telling you which ones they want to see solved.}
Try some of the following problems:
\begin{itemize}
\item $\min\{a,b\} \leq \frac{a+b}{2}$ for all real numbers $a$ and $b$. 					
\item Let $x$ be real. Then $x^2-x > 0$ if and only if $x \not\in [0,1]$.						
%\item Let $S$ be a set. There is a unique set $T$ such that $S \cap T=S$.						
\item If $r$ is irrational, then $\frac{1}{r}$ is irrational.										
\item There do not exist integers $p$ and $q$ satisfying $p^2-q^2=10$. 						
\item The complete real solution to $x^2+y^2-2y=-1$ is $(x,y)=(0,1)$. 							
\item Let $S$ and $T$ be sets with respect to a universe $U$. Prove that $\overline{S \cap T} \subseteq \overline{S} \cup \overline{T}$. 
\item Let $a, b, c \in \mathbb{Z}$. Prove that if $a \nmid b$ and $a \mid (b + c)$, then $a \nmid c$.
%\item The sum of the first $n$ odd positive integers equals $n^2$.									\hfill \nb{induction}
\end{itemize}

\vskip3em
\newpage\textbf{Lecture 13} \vskip1emProve that
$$
\sum_{i=1}^{n}i = \frac{n(n+1)}{2}
$$
holds for all natural numbers $n$.
\vskip3em
\newpage\textbf{Lecture 14} \vskip1em
\ic{In this lecture, you might want to consider giving a midterm survey of your teaching.}

Prove $P(n): 6 \mid (2n^{3} + 3n^{2} + n)$ holds $\forall n \in \mathbb{N}$.
\vskip3em
\newpage\textbf{Lecture 14} \vskip1em\ic{This illustrates the need for something ``stronger'' than induction.}

Let $\{x_{n}\}$ be a sequence defined by $x_{1} = 4$, $x_{2} = 68$ and $$x_{m} = 2x_{m-1}+15x_{m-2} \quad\quad \text{ for all } m \geq 3$$ 
Prove that $x_{n} = 2(-3)^{n} + 10\cdot 5^{n-1}$ for $n \geq 1$.

\vskip1em
\soln We proceed by induction. 
\vskip1em
\textbf{Base Case:} For $n=1$, we have $$x_{1} = 4 = 2(-3)^{1} + 10\cdot 5^{0} =  2(-3)^{n} + 10\cdot 5^{n-1}.$$
 \vskip1em
 \textbf{Inductive Hypothesis:} Assume that $$x_{k} = 2(-3)^{k} + 10\cdot 5^{k-1}$$ is true for some $k \in \mathbb{N}$.
 \vskip1em
 \textbf{Inductive Step:} Now, for $k+1$, 
 \begin{align*}
 x_{k+1} &= 2x_{k}+15x_{k-1} &&\text{ Only true if $k \geq 2$!!!}\\
 &= 2( 2(-3)^{k} + 10\cdot 5^{k-1}) + 15x_{k-1}\\
 &= 4(-3)^{k} + 20\cdot 5^{k-1} + 15x_{k-1}\\
 &= ...?
 \end{align*}
 \vskip3em
\newpage\textbf{Lecture 14} \vskip1em
\ic{I would make them do half of this example - say the base cases and the inductive hypothesis}

Suppose $x_{1} = 3$, $x_{2} = 5$ and for all $m\geq 3$,  $$x_{m} = 3x_{m-1} + 2x_{m-2}.$$
Prove that $x_{n} < 4^{n}$ for all $n \in \mathbb{N}$.
\vskip3em
\newpage\textbf{Lecture 15} \vskip1em
\textbf{Fibonacci Sequence}
\defn Define a sequence by $f_{1} = 1$, $f_{2} = 1$ and 
\[
f_{n} = f_{n-1} + f_{n-2} \quad\quad \text{For all $n \geq 3$}
\]
so $f_{3} = 2$, $f_{4} = 3$, $f_{5} = 5$, and so on. 

\vskip1em
\begin{enumerate}
\item Prove that $\displaystyle \sum_{r=1}^{n} f_{r}^{2} = f_{n}f_{n+1}$ for all $n \in \mathbb{N}$.
\item Prove that $f_{n} < \left(\frac{7}{4}\right)^{n}$ for all $n \in \mathbb{N}$.
\end{enumerate}

\vskip3em
\newpage\textbf{Lecture 16} \vskip1em
 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
\newpage\textbf{Lecture 16} \vskip1em
Examine the following induction ``proofs''. Find the mistake
\vskip1em
\textbf{Question:} For all $n \in \mathbb{N}$, $n > n + 1$.
\vskip1em
\textbf{Proof:} Let $P(n)$ be the statement: $n > n + 1$. Assume that $P(k)$ is true for some integer $k \geq 1$. That is, $k > k + 1$ for some integer $k \geq 1$. We must show that $P(k+1)$ is true, that is, $k+1>k+2$. But this follows immediately by adding one to both sides of $k > k+1$. Since the result is true for $n = k+1$, it holds for all $n$ by the Principle of Mathematical Induction.
\vskip3em
\newpage\textbf{Lecture 17} \vskip1em\ex Prove that $\gcd(3a+b,a) = \gcd(a,b)$ using the definition directly.
\vskip3em
\newpage\textbf{Lecture 18} \vskip1emProve that $\gcd(3s+t,s) = \gcd(s,t)$ using GCDWR.
\vskip3em
\newpage\textbf{Lecture 18} \vskip1emUse the Euclidean Algorithm to compute $\text{gcd}(120,84)$ and then use back substitution to find integers $x$ and $y$ such that $\text{gcd(}120,84) = 120x + 84y$.
\ic{If a student finishes quickly, challenge them to find two such linear combinations.}
\vskip3em
\newpage\textbf{Lecture 19} \vskip1em
Prove or disprove the following:
\begin{enumerate}
\item If $n \in \mathbb{N}$ then $\text{gcd}(n,n+1) = 1$.
\item Let $a,b,c \in \mathbb{Z}$.  If $\exists ~x,y \in \mathbb{Z}$ such that $ax^{2} + by^{2} = c$ then $\text{gcd}(a,b) \mid c$.
\item Let $a,b,c \in \mathbb{Z}$.  If  $\text{gcd}(a,b) \mid c$ then $\exists ~x,y \in \mathbb{Z}$ such that $ax^{2} + by^{2} = c$.
\end{enumerate}
\vskip3em
\newpage\textbf{Lecture 20} \vskip1em\ex Let $a,b,c \in \mathbb{Z}$. Prove if $\gcd(ab,c) = 1$ then $\gcd(a,c) = \gcd(b,c) = 1$.
\vskip3em
\newpage\textbf{Lecture 21} \vskip1emUse the Extended Euclidean Algorithm to find integers $x$ and $y$ such that $408x + 170y = \gcd(408,170)$.
\vskip3em
\newpage\textbf{Lecture 21} \vskip1emUse the Extended Euclidean Algorithm to find integers $x$ and $y$ such that $399x - 2145y = \gcd(399,-2145)$.
\vskip3em
\newpage\textbf{Lecture 22} \vskip1emHow many multiples of 12 are positive divisors of 2940? What are they?
\vskip3em
\newpage\textbf{Lecture 23} \vskip1emFind $x,y \in \mathbb{Z}$ such that $143x + 253y = \gcd(143,253)$.
\vskip0.1em
Determine which of the following equations are solvable for integers $x$ and $y$:
\begin{enumerate}
\item $143x + 253y = 11$
\item $143x + 253y = 155$
\item $143x + 253y = 154$
\end{enumerate}
\ic{The answers to these questions will be part of the lecture today.}
\vskip3em
\newpage\textbf{Lecture 24} \vskip1em
Let $a,b,x,y \in \mathbb{Z}$.\\[2mm]

Which one of the following statements is true?\\[2mm]
 
\begin{enumerate}[A)]
\item If $ax+by=6$, then $\gcd(a,b) = 6$.
\item If $\gcd(a,b) = 6$, then $ax+by=6$.
\item If $a=12b+18$, then $\gcd(a,b)=6$.
\item If $ax+by=1$, then $\gcd(6a,6b)=6$.
\item If $\gcd(a,b)=3$ and $\gcd(x,y)=2$, then $\gcd(ax,by)=6$.
\end{enumerate}

\vskip3em
\newpage\textbf{Lecture 24} \vskip1emFind all non-negative integer solutions to $15x - 24y = 9$ where $x \leq 20$ and $y \leq 20$.
\vskip3em
\newpage\textbf{Lecture 25} \vskip1em\ic{Write on the board and get students to prove. These are follow your nose proofs}
\textbf{Congruence is an Equivalence Relation (CER)}
\vskip0.1em
Let $n \in \mathbb{N}$. Let $a,b,c \in \mathbb{Z}$. Then
\begin{enumerate}
\item (Reflexivity) $a \equiv a \pmod{n}$.
\item (Symmetry) $a \equiv b \pmod{n} \Rightarrow b \equiv a \pmod{n}$.
\item (Transitivity) $a \equiv b \pmod{n}$ and $b \equiv c \pmod{n} \Rightarrow a \equiv c \pmod{n}$.
\end{enumerate}

\vskip3em
\newpage\textbf{Lecture 25} \vskip1em\ic{Write on board and get students to prove on their own}
\textbf{Properties of Congruence (PC)}
Let $a,a',b,b' \in \mathbb{Z}$. If $a \equiv a' \pmod{m}$ and $b \equiv b' \pmod{m}$, then
\begin{enumerate}
\item $a+b \equiv a'+b' \pmod{m}$
\item $a-b \equiv a'-b' \pmod{m}$
\item $ab \equiv a'b' \pmod{m}$
\end{enumerate}

\vskip3em
\newpage\textbf{Lecture 27} \vskip1em
What is the last digit of $5^{32}3^{10} + 9^{22}$?
\vskip3em
\newpage\textbf{Lecture 27} \vskip1em
Solve $9x \equiv 6 \mod{15}$. 
\vskip3em
\newpage\textbf{Lecture 28} \vskip1em
Which of the following satisfies $x \equiv 40 \pmod{17}$\:?\\[2mm]

(Do not use a calculator.)\\[2mm]
 
\begin{enumerate}[A)]
\item $x=173$
\item $x=15^{5}+19^{3}-4$
\item $x=5\cdot18^{100}$
\item $x=2\cdot3\cdot5\cdot7\cdot11\cdot13$
\item $x=17^0+17^1+17^2+17^3+17^4+17^5+17^6$
\end{enumerate}

\vskip3em 
\newpage\textbf{Lecture 28} \vskip1em
Solve the following equations in $\mathbb{Z}_{14}$. Express answers as $[x]$ where $0 \leq x < 14$.
\begin{enumerate}[i)]
\item $[75]-[x]=[50]$
\item $[10][x]=[1]$		
\item $[10][x]=[2]$		
\end{enumerate}
Hint: Rewrite these using congruences.

\vskip3em
\newpage\textbf{Lecture 29} \vskip1em
Find the additive and multiplicative inverses of $[7]$ in $\mathbb{Z}_{11}$. Give your answers in the form $[x]$ where $0 \leq x \leq 10$.

\vskip3em
\newpage\textbf{Lecture 29} \vskip1em
The following are equivalent
\begin{itemize}
\item $a \equiv b \pmod {m}$
\item $m \mid (a-b)$
\item $\exists k \in \mathbb{Z}, a-b = km$
\item $\exists k \in \mathbb{Z}, a = km+b$
\item $a$ and $b$ have the same remainder when divided by $m$
\item $[a]=[b]$ in $\mathbb{Z}_m$.
\end{itemize}

\thm
[LCT 2] Let $a,c \in \mathbb{Z}$ and let $m \in \mathbb{N}$. Let $\gcd(a,m)=d$.
The equation $[a][x]=[c]$ in $\mathbb{Z}_m$ has a solution if and only if  $d \mid c$.
Moreover, if $[x] = [x_0]$ is one particular solution, then the complete solution is
\[ \left\{[x_0], [x_0+\tfrac{m}{d}], [x_0+2\tfrac{m}{d}], \ldots, [x_0+(d-1)\tfrac{m}{d}] \right\} \]
\vskip3em
\newpage\textbf{Lecture 30} \vskip1emFind the remainder when $7^{92}$ is divided by $11$. 
\vskip3em
\newpage\textbf{Lecture 30} \vskip1emProve that if $p \nmid a$ and $r \equiv s \mod{(p-1)}$, then $a^{r} \equiv a^{s} \mod{p}$.
\vskip3em
\newpage\textbf{Lecture 31} \vskip1em
\thm [Chinese Remainder Theorem (CRT)
If \newline$\gcd(m_1,m_2) = 1$, then for any choice of integers $a_1$ and $a_2$, there exists a solution to the simultaneous congruences
\begin{eqnarray*}
n & \equiv & a_1 \pmod{m_1} \\
n & \equiv & a_2 \pmod{m_2}
\end{eqnarray*}
Moreover, if $n = n_0$ is one integer solution, then the complete solution is $n \equiv n_0 \pmod{m_1m_2}$.
\vskip1em
\thm (Generalized CRT (GCRT)) If $m_1, m_2, \ldots, m_k $ are integers and $\gcd(m_i, m_j) = 1$ whenever $i \neq j$, then for any choice of integers $a_1, a_2, \ldots, a_k$, there exists a solution to the simultaneous congruences
\begin{align*}
n & \equiv a_1 \pmod {m_1} \\
n & \equiv a_2 \pmod {m_2} \\
  & \vdots \\
n & \equiv a_k \pmod {m_k}
\end{align*}
Moreover, if $n = n_0$ is one integer solution, then the complete solution is
\[ n \equiv n_0 \pmod{m_1 m_2 \ldots m_k} \]

\vskip3em
\newpage\textbf{Lecture 32} \vskip1em
Which of the following is equal to $[53]^{242}+[5]^{-1}$ in $\mathbb{Z}_7$?\\[2mm]

(Do not use a calculator.)\\[2mm]
 
\begin{enumerate}[A)]
\item $[5]$
\item $[4]$
\item $[3]$
\item $[2]$
\item $[1]$
\end{enumerate}

\vskip3em
\newpage\textbf{Lecture 32} \vskip1em
For what integers is $x^{5} + x^{3} + 2x^{2} + 1$ divisible by $6$?
\vskip3em
\newpage\textbf{Lecture 32} \vskip1em
\begin{enumerate}
\item Show that $x=2^{129}$ solves $2x \equiv1 \mod{131}$.
\item Use the square and multiply algorithm to find the remainder when $2^{129}$ is divided by $131$.
\item Solve $2x \equiv 3 \mod{131}$ for $0 \leq x \leq 130$.
\end{enumerate}
\vskip3em
\newpage\textbf{Lecture 33} \vskip1em
Let $p=2$, $q=11$ and $e=3$
\begin{enumerate}
\item Compute $n$, $\phi(n)$ and $d$.
\item Compute $C \equiv M^{e} \mod{n}$ when $M=8$ (reduce to least nonnegative $C$).
\item Compute $R\equiv C^{d} \mod{n}$ when $C=6$ (reduce to least nonnegative $R$).
\end{enumerate}
\vskip3em
\newpage\textbf{Lecture 34} \vskip1em
Express the following in standard form
\begin{enumerate}
\item $z = \frac{(1 - 2i) - (3 + 4i)}{5 - 6i}$
\item $w = i^{2015}$
\end{enumerate}

\vskip3em
\newpage\textbf{Lecture 35} \vskip1em\ic{Give the next two exercises simultaneously for students to battle through}
Solve $z^{2} = i\bar{z}$ for $z \in \mathbb{C}$
\vskip3em
\newpage\textbf{Lecture 35} \vskip1em
Find a real solution to $$6z^{3} + (1 + 3\sqrt{2}i)z^{2} - (11-2\sqrt{2}i)z - 6 = 0$$

\vskip3em
\newpage\textbf{Lecture 35} \vskip1em
Prove the following for $z \in \mathbb{C}$
\begin{enumerate}
\item $z \in \mathbb{R}$ if and only if $z = \bar{z}$.
\item $z$ is purely imaginary if and only if $z = -\bar{z}$.
\end{enumerate}

\vskip3em
\newpage\textbf{Lecture 36} \vskip1emHow many integers $x$ satisfy all of the following three conditions?

\begin{gather*}
 x \equiv 6 \pmod{13} \\
 4x \equiv 3 \pmod{7} \\
  -1000 < x < 1000 
 \end{gather*}
 
\begin{enumerate}[A)]
\item $1$
\item $7$
\item $13$
\item $22$
\item $91$
\end{enumerate}
\vskip3em
\newpage\textbf{Lecture 36} \vskip1em
To prove $|z + w| \leq |z| + |w|$, it suffices to prove that
$$|z+w|^{2} \leq (|z| + |w|)^{2} = |z|^{2}  + 2|zw| + |w|^{2}$$
since the modulus is a positive real number. Using the Properties of Modulus and the Properties of Conjugates, we have
\begin{align*}
|z+w|^{2} &= (z+w)(\overline{z+w})  && \text{PM}  \\
&= (z+w)(\bar{z} + \bar{w}) && \text{PCJ}   \\
&= z\bar{z} + z\bar{w} + w\bar{z} + w\bar{w} \\ 
&= |z|^{2} + z\bar{w} + \overline{z\bar{w}} + |w|^{2} && \text{PCJ and PM}
\end{align*}
Now, from Properties of Conjugates, we have that 
$$z\bar{w} + \overline{z\bar{w}} = 2\Re(z\bar{w}) \leq 2|z\bar{w}| = 2|zw|$$
and hence
\begin{align*}
|z+w|^{2} = |z|^{2} + z\bar{w} + \overline{z\bar{w}} + |w|^{2} \leq |z|^{2} + 2|zw| + |w|^{2}
\end{align*}
completing the proof.

\begin{center}
\includegraphics{TriangleInequality.png}
\end{center}
\vskip3em
\newpage\textbf{Lecture 37} \vskip1emExpress the following in terms of polar coordinates:
\begin{enumerate}
\item $-3$
\item $1-i$
\end{enumerate}
\vskip3em
\newpage\textbf{Lecture 37} \vskip1em\begin{enumerate}
\item Write $\text{cis}(15\pi/6)$ in standard form.
\item Write $-3\sqrt{2} + 3\sqrt{6}i$ in polar form.
\end{enumerate}
\vskip3em
\newpage\textbf{Lecture 38} \vskip1emWrite $(\sqrt{3} - i)^{10}$ in standard form.
\vskip3em
\newpage\textbf{Lecture 39} \vskip1em
Find all eighth roots of unity in standard form.

\vskip3em
\newpage\textbf{Lecture 40} \vskip1emWhat is the value of $\left|\left(\overline{-\sqrt{3}+i}\right)^5\right|$ ?
 
\begin{enumerate}[A)]
\item $16i$
\item $27$
\item $32$
\item $-45$
\item $64$
\end{enumerate}
\vskip3em
\newpage\textbf{Lecture 40} \vskip1emSimplify $(x^{5} + x^{2} + 1)(x+1) + (x^{3} + x + 1)$ over $\mathbb{Z}_{2}[x]$
\vskip3em
\newpage\textbf{Lecture 41} \vskip1emCompute the quotient and the remainder when $$x^{4} + 2x^{3} + 2x^{2} + 2x + 1$$ is divided by $g(x) = 2x^{2} + 3x + 4$ in $\mathbb{Z}_{5}[x]$.
\vskip3em
\newpage\textbf{Lecture 41} \vskip1emIn $\mathbb{Z}_{7}[x]$, what is the remainder when $4x^{3} + 2x + 5$ is divided by $x+6$?
\vskip3em
\newpage\textbf{Lecture 41} \vskip1em
Prove that there does not exist a real linear factor of $$f(x) = x^{8} + x^{3} + 1.$$
\vskip3em
\newpage\textbf{Lecture 42} \vskip1emProve that a polynomial over any field $\mathbb{F}$ of degree $n \geq 1$ has at most $n$ roots.
\vskip3em
\newpage\textbf{Lecture 42} \vskip1emFactor $iz^{3} + (3-i)z^{2} + (-3-2i)z-6$ as a product of linear factors. Hint: There is an easy to find integer root!
\vskip3em
\newpage\textbf{Lecture 43} \vskip1em
Fully factor $x^{3} - \tfrac{32}{15}x^{2} + \tfrac{1}{5}x + \tfrac{2}{15}$.
\vskip3em
\newpage\textbf{Lecture 43} \vskip1em
Prove that $\sqrt{5} + \sqrt{3}$ is irrational.
\vskip3em
\newpage\textbf{Lecture 44} \vskip1emHow many of the following statements are true?
 
 \begin{itemize}
\item Every complex cubic polynomial has a complex root.
\item When $x^3+6x-7$ is divided by a quadratic polynomial $ax^2+bx+c$ in $\mathbb{R}[x]$, \\
then the remainder has degree 1.
\item If $f(x), g(x) \in \mathbb{Q}[x]$, then $f(x)g(x) \in \mathbb{Q}[x]$.
\item Every non-constant polynomial in $\mathbb{Z}_5[x]$ has a root in $\mathbb{Z}_5$.
\end{itemize}

\begin{enumerate}[A)]
\item 0
\item 1
\item 2
\item 3
\item 4
\end{enumerate}
\vskip3em
\newpage\textbf{Lecture 44} \vskip1em
Prove that a real polynomial of odd degree has a real root.
\vskip3em
\newpage\end{document}