\newlec

\ic{This should be the lecture you give on the day of the midterm. It is a very light computational lecture.}

\defn For $x \in \mathbb{R}$, define the floor function $\lfloor x \rfloor$ to be the greatest integers less than or equal to $x$.
\vskip1em
\ex 
\begin{enumerate}
\item $\floor{2.5} = 2 = \floor{2}$
\item $\floor{\pi} = 3$
\item $\floor{0} = 0$
\item $\floor{-2.5} = -3$
\end{enumerate}
\ex Find $\gcd(56,35)$
\begin{align*}
56(1) + 35(0) &= 56 && \text{ Eqn [1]}\\
56(0) + 35(1) &= 35 && \text{ Eqn [2]}\\
56(1) + 35(-1) &= 21 && \text{ $q_{1} = \floor{\tfrac{56}{35}} = 1$ Eqn [3] $= [1]-q_{1}[2]$}\\
56(-1) + 35(2) &= 14 && \text{ $q_{2} = \floor{\tfrac{35}{21}} = 1$ Eqn [4] $= [2]-q_{2}[3]$}\\
56(2) + 35(-3) &= 7 && \text{ $q_{3} = \floor{\tfrac{21}{14}} = 1$ Eqn [5] $= [3]-q_{3}[4]$}\\
56(-5) + 35(8) &= 0 && \text{ $q_{4} = \floor{\tfrac{14}{7}} = 2$ Eqn [6] $= [4]-q_{4}[5]$}\\
\end{align*}
Therefore $\gcd(56,35) = 7 = 56(2) + 35(-3)$. This process gives rise to the Extended Euclidean Algorithm.
\vskip1em
\ex Find $x,y \in \mathbb{Z}$ such that $506x + 391y = \gcd(506,391)$.

\begin{table}[ht!]
%\caption{default}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
$x$ & $y$ & $r$ & $q$ \\
\hline
1 & 0 & 506 & 0 \\
0 & 1 & 391 & 0\\
1 & -1 & 115 & $\floor{\tfrac{506}{391}}=1$\\
-3 & 4 & 46 & $\floor{\tfrac{391}{115}} = 3$\\
7 & -9 & 23 & $\floor{\tfrac{115}{46}}=2$\\
-17 & 22 & 0 & $\floor{\tfrac{46}{23}} = 2$\\
\hline
\end{tabular}
\end{center}
%\label{default}
\end{table}%
\vskip1em
Therefore, $506(7) + 391(-9) = 23 = \gcd(506,391)$. \qed
\vskip1em
\note This process is known as the Extended Euclidean Algorithm.
\newpage
\hdc
Use the Extended Euclidean Algorithm to find integers $x$ and $y$ such that $408x + 170y = \gcd(408,170)$.
\vskip3em
\soln
\begin{table}[ht!]
%\caption{default}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
$x$ & $y$ & $r$ & $q$ \\
\hline
1 & 0 & 408 & 0 \\
0 & 1 & 170 & 0\\
1 & -2 & 68 & $\floor{\tfrac{408}{170}}=2$\\
-2 & 5 & 34 & $\floor{\tfrac{170}{68}} = 2$\\
5& -12 & 0 & $\floor{\tfrac{68}{34}}=2$\\
\hline
\end{tabular}
\end{center}
%\label{default}
\end{table}%
\vskip1em
Therefore, $408(-2) + 170(5) = 34 = \gcd(408,170)$. \qed

\newpage

\note \begin{enumerate}
\item B\'{e}zout's Lemma is the Extended Euclidean Algorithm in the textbook.
\item With $\gcd(a,b)$, what if
\begin{enumerate}
\item $b > a$? Then swap $a$ and $b$. This works since $\gcd(a,b) = \gcd(b,a)$.
\item $a < 0$ or $b < 0$? Solution is to make all the terms positive. This works since
\[
\gcd(a,b) = \gcd(-a,b) = \gcd(a,-b) = \gcd(-a,-b).
\]
\end{enumerate}
\item In practice, one can accomplish these goals by changing the headings then accounting for this in the final steps.
\end{enumerate}

\newpage

\hdc
Use the Extended Euclidean Algorithm to find integers $x$ and $y$ such that $399x - 2145y = \gcd(399,-2145)$.
\vskip3em
\soln
\begin{table}[ht!]
%\caption{default}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
$x$ & $-y$ & $r$ & $q$ \\
\hline
0 & 1 & 2145 & 0 \\
1 & 0 & 399 & 0\\
-5 & 1 & 150 & $\floor{\tfrac{2145}{399}}=5$\\
11 & -2 & 99 & $\floor{\tfrac{399}{150}} = 2$\\
-16& 3 & 51 & $\floor{\tfrac{150}{99}}=1$\\
27& -5 & 48 & $\floor{\tfrac{99}{51}}=1$\\
-43& 8 & 3 & $\floor{\tfrac{51}{48}}=1$\\
27-(16)(-43)& -5-16(8) & 0 & $\floor{\tfrac{48}{3}}=1$\\
\hline
\end{tabular}
\end{center}
%\label{default}
\end{table}%
\vskip1em
Therefore, $x=-43$, $-y = 8$ and so $y=-8$, $\gcd(399,-2145) = 3$. Hence
\[
399(-43) -2145(-8) = 3 = \gcd(399,-2145)
\]


