\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage{cancel}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage{multicol}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}


\usepackage{tikz}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\input{preamble.tex}

\begin{document}

\homework{10: The Euclidean Algorithm!}{Due Friday, Week 5}

Do \textbf{one} of the \textbf{two} problems below! 

These problems are both centered around the \textbf{Euclidean algorithm}, which is a method for taking two positive integers $a >b$ and calculating their GCD:
\begin{algorithm}
To initialize our algorithm, set $r_1 = a, r_2 = b$. Our algorithm will create a sequence of values $r_1, r_2, r_3\ldots r_k,$, where this last value $r_k$ will be the GCD of $a,b$.
\begin{enumerate}
\item Suppose that we have defined our sequence up to $r_i, r_{i+1}$, that $r_i > r_{i+1}$, and that $r_{i+1} > 0$.
\item If the remainder of $r_i$ when divided by $r_{i+1}$ is 0, quit our algorithm: $r_{i+1}$ is the GCD we were looking for.
\item Otherwise, to define $r_{i+2}$, simply set it equal to the remainder of $r_i$ when divided by $r_{i+1}$.  This always gives us a number smaller than $r_{i+1}$ that is positive, by definition.
\item Go to 1.
\end{enumerate}
\end{algorithm}
We give an example run of this algorithm for the two values $63, 99$:
\begin{enumerate}
\item Set $r_1 = 99, r_2 = 63$.
\item The remainder of 99 divided by 63 is 36; so set $r_3 = 36$.
\item The remainder of 63 divided by 36 is 27; so set $r_4 = 27$.
\item The remainder of 36 divided by 27 is 9; so set $r_5 = 9$.
\item The remainder of 27 divided by 9 is 0; so our algorithm quits, and says that the GCD of 63 and 99 is 9.
\end{enumerate}
The algorithm works here, as we can check: because $63 = 9\cdot7$ and $99 = 9 \cdot 11$, the GCD of 63 and 99 is 9, as claimed!

\begin{enumerate}
\item Prove that this algorithm does work!  In other words, show that the GCD of any two numbers $a,b$ can be calculated by the above process.
\item Using the algorithm above, prove the following result:
\begin{thm}
If $a,b$ are two positive integers, then we can find two more integers $n,m$ such that 
\begin{align*}
na + mb = GCD(a,b).
\end{align*}
\end{thm}
\end{enumerate}

\end{document}