\newlec
\ic{If you ran out of time last lecture, you should give students the following tips.}

When solving GCD problems, the following gives a rough order of how and when you should try a technique
\begin{enumerate}
\item B\'{e}zout's Theorem (EEA) [Good when gcd is in hypothesis]
\item GCDWR [Good when terms in gcd depend on each other; good for computations]
\item GCDCT [Good when gcd is in conclusion]
\item Definition [Good when nothing else seems to work]
\item GCDPF [Good when you're desperate]
\end{enumerate}

\newpage
\hdc
Find $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{Linear Diophantine Equations (LDE)}
\vskip1em
We want to solve $ax + by = c$ where $a,b,c \in \mathbb{Z}$ under the condition that $x,y \in \mathbb{Z}$
\ic{Relate this to solving for the equation of a line over the real case and invite students to think critically about the difference in the integer case.}
\ex Solve the LDE $143x + 253y = 11$.
\vskip1em
\soln We can solve this using the Extended Euclidean Algorithm!
\begin{table}[ht!]
%\caption{default}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
x & y & r &q \\
\hline
0 & 1 & 253 &\\
1 & 0 & 143 &\\
-1 & 1 & 110 &1\\
2 & -1 & 33 &1\\
-7 & 4 & 11 &3\\
23 & -13 & 0 &3\\
\hline
\end{tabular}
\end{center}
%\label{default}
\end{table}%
\vskip0.01em
Therefore, $143(-7) + 254(4) = 11$. Are there other solutions? 
\ic{This is the 10-15 minute mark depending on the introduction. Students should do the EEA on their own and you should do it simultaneously.}

Questions to ask about LDE's
\begin{enumerate}
\item Is there a solution?
\item What is it?
\item Are there more than one?
\end{enumerate}
\ex Solve the LDE
\[
143x + 253y = 155
\]
\soln Assume towards a contradiction that there exist $x_{0}$ and $y_{0}$ integers such that
\[
143x_{0} + 253y_{0} = 155
\]
By before, $11 \mid 143$ and $11 \mid 253$. Hence by Divisibility of Integer Combinations, $143x_{0} + 253y_{0}$ is divisible by $11$. HOWEVER, 
\[
11 \nmid 155 = 143x_{0} + 253y_{0}
\]
which is a contradiction. Hence the original LDE has no integer solutions. \qed
\ic{This is the 25 minute mark.}
What about
\[
143x + 253y = 154
\]
as an LDE?
Now, notice that $154 = 11 \cdot 14$. Hence, since
\[
143(-7) + 253(4) = 11
\]
multiplying by $14$ gives
\begin{align*}
143(-7\cdot 14) + 253(4 \cdot 14) &= 11\cdot 14\\
143(-98) + 253(56) &= 154
\end{align*}
\ic{This is the 35 minute mark.}
These insights lead to the following theorem
\vskip1em
\thm (LDET1) Let $d = \gcd(a,b)$. The LDE
\[
ax + by = c
\]
has a solution if and only if $d \mid c$. 
\vskip1em
\pf $(\Rightarrow)$ Assume that $ax  + by = c$ has an integer solution, say $x_{0}, y_{0} \in \mathbb{Z}$.  Since $d \mid a$ and $d \mid b$, by Divisibility of Integer Combinations, we have that $d \mid (ax_{0} + by_{0})=c$. 
\vskip1em
$(\Leftarrow)$ Assume that $d \mid c$. Then, there exists an integer $k$ such that $dk = c$. By B\'{e}zout's Lemma, there exist integers $u$ and $v$ such that $au + bv = \gcd(a,b) = d$. Multiplying by $k$ gives
\[
a(uk) + b(vk) = dk = c
\]
Therefore, a solution is given by $x = uk$ and $y = vk$.\qed
\ic{This is the 45 minute mark.}
\ex Solve $20x + 35y = 5$ as an LDE.
\vskip1em
\soln Notice here that we can simplify the LDE by dividing by $5$ first to give
\[
4x + 7y = 1
\]
An easy solution is given by $x=2$ and $y=-1$.
\vskip1em
Now, look at $x_{2} = 2 + 7$ and $y_{2} = -1 - 4$. Notice that
\begin{align*}
4x_{2} + 7y_{2} &= 4(2 + 7) + 7(-1 -4)\\
&= 4(2) + 4(7) + 7(-1) + 7(-4)\\
&= 4(2) + 7(-1)\\
&= 4x + 7y\\
&= 1
\end{align*}
In fact, if I take $x_{2} = 2 + 7(11)$ and $y_{2} = -1 - 4(11)$. Notice that
\begin{align*}
4x_{2} + 7y_{2} &= 4(2 + 7(11)) + 7(-1 -4(11))\\
&= 4(2) + 4(7)(11) + 7(-1) + 7(-4)(11)\\
&= 4(2) + 7(-1)\\
&= 4x + 7y\\
&= 1
\end{align*}
and $11$ above is very arbitrary. In fact, this gives us an insight into the complete characterization of solutions for an LDE.