\newlec

\prop Transitivity of Divisibility (TD)
$$
a \mid b \wedge b \mid c \Rightarrow a \mid c
$$

\pf There exists a $k \in \mathbb{Z}$ such that $ak = b$. There exists an $\ell \in \mathbb{Z}$ such that $b\ell = c$. This implies that $(ak)\ell = c$ and hence $a(k\ell) = c$. Since $k\ell \in \mathbb{Z}$, we have that $a \mid c$. \qed
\vskip1em

\prop Divisibility of Integer Combinations (DIC). Let $a,b,c \in \mathbb{Z}$. If $a \mid b$ and $a \mid c$. Then for all $x,y \in \mathbb{Z}$, we have $a \mid (bx + cy)$.
\vskip1em
\pf Since $a \mid b$, $\exists k \in \mathbb{Z}$ such that $ak = b$. Since $a \mid c$, $\exists \ell \in \mathbb{Z}$ such that $a\ell = c$. Then for all integers $x$ and $y$,
\[
bx + cy = akx + a\ell y = a(kx + \ell y)
\]
Since $kx + \ell y \in \mathbb{Z}$, by definition we see that $a \mid (bx + cy)$. \qed
\vskip1em
\qn Prove that if $m \in \mathbb{Z}$ and $14 \mid m$ then $7 \mid (135m + 693)$.
\vskip1em
\pf Suppose $m \in \mathbb{Z}$ and $14 \mid m$. Since $7 \mid 14$ (since $7\cdot 2 = 14$), by transitivity we have that $7 \mid m$. As $7 \mid 693$ (since $7 \cdot 99 = 693$), we have by Divisibility of Integer Combinations (DIC) that
\[
7 \mid m(135) + 693(1)
\]
and thus $7 \mid (135m + 693)$. \qed
\vskip1em
\note In DIC we set $b = m$, $x = 135$, $c = 693$ and $y=1$.

\ic{This should be the 10-13 minute mark}

\defn Let $A,B$ be statements. The \textit{converse} of $A \Rightarrow B$ is $B \Rightarrow A$.
\vskip1em
\ex If $S$ is the statement: 
\begin{center}
If $p$, $p+1$ are prime, then $p=2$. 
\end{center}
Then the converse of $S$ is
\begin{center}
If $p=2$, then $p$, $p+1$ are prime.
\end{center}
Note in this case that the statement and it's converse are both true.
\vskip1em
\recall Bounds by Divisibility (BBD)
\[
a \mid b \wedge b \neq 0 \Rightarrow |a| \leq |b|
\]
\vskip1em
\ex The converse of Bounds by Divisibility (BBD) is
\[
|a| \leq |b| \Rightarrow a \mid b \wedge b \neq 0 
\]
Note here, the converse is a false statement (for example $6 \leq 7$).

\ic{This should be the 20 minute mark}

\defn \textit{If and only if} $A \Leftrightarrow B$, $A$ iff $B$, $A$ if and only if $B$.
\begin{center}
  \begin{tabular}{ c | c | c  }
    \hline
   $A$ & $B$ & $A \Leftrightarrow B$ \\
   \hline
   T & T & T \\
   T & F & F \\
   F & T & F \\   
   F & F & T \\
  \end{tabular}
\end{center}
\note Definitions in mathematics should (almost) always be if and only if definitions. Mathematicians generally are sloppy and don't do this.  We will try to be careful in this course but you have been warned for other courses.
\vskip1em
\exr Show that $A \Leftrightarrow B \equiv (A \Rightarrow B) \wedge (B \Rightarrow A)$
\vskip1em
\ex In $\Delta ABC$, show that $b = c\cos A$ if and only if $\angle C = \tfrac{\pi}{2}$.
\vskip1em
\pf Suppose that $b = c\cos A$. By the Cosine Law,
\begin{align*}
a^{2} &= b^{2} + c^{2} - 2bc\cos A\\
a^{2} &= b^{2} + c^{2} - 2bb\\
a^{2} &= c^{2} - b^{2}\\
a^{2} + b^{2} &= c^{2}
\end{align*}
Is the converse of the Pythagorean Theorem true? Let's find out! Using the cosine law again,
\begin{align*}
c^{2} &= a^{2} + b^{2} - 2ab\cos C\\
c^{2} &= c^{2} - 2ab\cos C\\
0 &= - 2ab\cos C
\end{align*}
Therefore, $\cos C = 0$ since $0 < \angle C < \pi$, we see that $\angle C = \pi/2$. 
\vskip1em
Now we prove the converse. Suppose that $\angle C = \pi/2$. Then $\Delta ABC$ is a right angled triangle! Hence, $\cos A = \tfrac{b}{c}$ and thus $c \cos A = b$ as required. \qed


\ic{This should be the 35 minute mark. Emphasize proving the converse in iff proofs.}

\newpage

\hdc

Prove the following. Suppose that $x,y \geq 0$. Show that $x=y$ if and only if $\frac{x+y}{2} = \sqrt{xy}$. 
\vskip3em
\ic{Give 5 minutes to try it and 5 minutes to take it up.}
\pf Suppose first that $\frac{x+y}{2} = \sqrt{xy}$. Then 
\begin{align*}
\frac{x+y}{2} &= \sqrt{xy}\\
x + y &= 2\sqrt{xy}\\
(x+y)^{2} &= (2\sqrt{xy})^{2}\\
x^{2} + 2xy + y^{2} &= 4xy \\
x^{2} - 2xy + y^{2} &= 0\\
(x-y)^{2} &= 0.
\end{align*}
Therefore, $x-y=0$ and thus $x=y$. Now, suppose first that $x=y$. Then 
\begin{align*}
\text{LHS} &= \frac{x+y}{2} = \frac{y+y}{2} = \frac{2y}{2} = y
\end{align*}
and 
\begin{align*}
\text{RHS} &= \sqrt{xy} = \sqrt{y^{2}} = y
\end{align*}
with the last equality holding since $y \geq 0$. Therefore, $\frac{x+y}{2} = \sqrt{xy}$.

\ic{This is the 45 minute mark.}

\newpage

\defn A \textit{set} is a collection of elements.
\vskip1em
\ex
\begin{enumerate}
\item $\mathbb{Z} = \{...-2,-1,0,1,2,...\}$
\item $\mathbb{N} = \{1,2,...\}$
\item $\mathbb{R}$
\item $\mathbb{Q} = \{a/b \in \mathbb{R} : a \in \mathbb{Z} \wedge b \in \mathbb{Z} \wedge b \neq 0\}$ (We call $\mathbb{R}$ the \textit{universe of discourse}.
\item $\{5,A\}$
\item $S = \{\blacksquare, 2 , \{1,2\}\}$
\end{enumerate}

\note For Math 135, the natural numbers begin with the element $1$. (Some textbooks or courses start with $0$).
\vskip1em
\note $x \in S$ means $x$ in $S$ (or $x$ belongs to $S$) and $x \notin S$ means $x$ not in $S$.
\ic{If you have time here do these, otherwise start the next lecture with these two points.}
\note $\{ \}$ and $\emptyset$ are the empty set, a set with no elements.
\vskip1em
\note $\{\emptyset\}$ is NOT the empty set. It is a set with one element, the element that is the empty set.


