\newlec

\ic{Do these proofs if you missed them. Otherwise review the theorems with examples.}

\thm (B\'{e}zout's Lemma (Extended Euclidean Algorithm - EEA)) Let $a,b \in \mathbb{Z}$. Then there exist integers $x,y$ such that $ax + by = d$
\vskip1em
\pf We've seen the outline of the proof via an example. Just make the argument abstract. The proof is left as a reading exercise.\qed
\vskip1em
\thm GCD Characterization Theorem (GCDCT) If $d > 0$, $d \mid a$, $d \mid b$ and there exist integers $x$ and $y$ such that $ax + by = d$, then $d = \gcd(a,b)$. 
\vskip1em
\pf Let $e = \gcd(a,b)$. Since $d \mid a$ and $d \mid b$, by maximality we have that $d \leq e$. Now $e \mid a$ and $e \mid b$ so by Divisibility of Integer Combinations, $e \mid (ax + by) = d$. Thus, by Bounds by Divisibility, $|e| \leq |d|$ and since $d,e > 0$, we have that $e \leq d$. Hence $d=e$. \qed

\vskip1em
\ex $6 > 0$, $6 \mid 30$, $6 \mid 42$ and $30(3) + 42(-2)=6$ and hence by the GCD Characterization Theorem, we have that $\gcd(30,42) = 6$.
\vskip1em
\ex Prove if $a,b,x,y\in\mathbb{Z}$, are such that $\gcd(a,b) \neq 0$ and $ax + by = \gcd(a,b)$, then $\gcd(x,y) = 1$.
\vskip1em
\pf Since $\gcd(a,b) \mid a$ and $\gcd(a,b) \mid b$, we divide by $\gcd(a,b) \neq 0$ to see that
\[
\frac{a}{\gcd(a,b)}x + \frac{b}{\gcd(a,b)} y = 1
\]
Since $1 \mid x$ and $1 \mid y$ and $1 > 0$, GCD Characterization Theorem implies that $\gcd(x,y) = 1$. \qed
\ic{This is the 10 minute mark.}
Now, we've reached the point where we can prove Euclid's Lemma.
\vskip1em
\thm (Euclid's Lemma - [Primes and Divisibility PAD]). If $p$ is a prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.
\vskip1em
\pf Suppose $p$ is prime, $p \mid ab$ and $p \nmid a$ (possible by elimination). Since $p \nmid a$, $\gcd(p,a)=1$. By B\'{e}zout's Lemma, there exist $x,y \in \mathbb{Z}$ such that
\begin{align*}
px + ay &= 1\\
pbx + aby &= b
\end{align*}
Now, since $p \mid p$ and $p \mid ab$, by Divisibility of Integer Combinations, $p \mid p(bx) + ab(y)$ and hence $p \mid b$.

\ic{This is the 20 minute mark}

\newpage
\hdc

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
\soln
\begin{enumerate}
\item $n+1 = n(1) + 1$ and so by the GCD Characterization Theorem, $\gcd(n+1,n) = \gcd(n,1)=1$. Hence this is true.
\item $\gcd(a,b) \mid a$ and $\gcd(a,b) \mid b$. Thus, by Divisibility of Integer Combinations, $\gcd(a,b) \mid (ax^{2}+by^{2})$ which implies that $\gcd(a,b) \mid c$. Hence this is true.
\item This is false. Suppose that $a=3$, $b=0$ and $c=6$. Then $\gcd(a,b) = 3 \mid 6 = c$ however, $3x^{2} + 0y^{2} = 6$ implies that $x^{2} = 2$, a contradiction.
\end{enumerate}


\ic{This is the 30-35 minute mark. At the end of this lecture, I think it would be wise to talk about the midterm a bit. It is coming up so I've left a bit of extra time to review for the midterm.}









