        \problemdata       % Takes 5 *mandatory* arguments
        {gcd}             % latex-friendly label for the prob.
        {induction}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {S02 ps2-5, F99 PS2-7} % Usage (list ones you are aware of).
        {Ashish, S02}        % Last revision info (author, date).


\begin{problem}\label{mx+ny}
Let $m$ be a natural number and $n$ be a positive integer.  Prove \emph{by
induction} that there are integers $x,y$ such that $mx+ny= \gcd(m,n)$.
You may use the fact that
\begin{equation}\label{241}
\gcd(m,n) = \gcd(m,r)
\end{equation}
where $r$ is the remainder of $n$ divided by $m$ (\cf Rosen, Lemma 2.4.1).

\begin{quote}
\textbf{IMPORTANT NOTE:} While correct above, the definition of $r$ was a typo in the original problem set. Rosen, Lemma 2.4.1 states $\gcd(m, n) = \gcd(m, n\!\mod m)$ which is different from $\gcd(m,n) = \gcd(n, m\!\mod n)$.  The first statement is true, while the second is \textbf{NOT}.  This only requires a small change in the overall proof form to correct, which is the assumption that $m$ can be less than $n$ without  loss of generality. 
\end{quote}

\solution{
\begin{proof}
Define
\[
P(n) \eqdef\quad n > 0 \implies \forall m \in \naturals\, \exists x,y\in \integers\
[mx+ny= \gcd(m,n)].
\]
We want to prove that $P(n)$ holds for all $n \in \naturals$.  We do this
by strong induction.

Namely, we assume that whenever $k$ is a positive integer \emph{less than}
$n$ we can express $\gcd(k,m)$ as an linear integer combination of $k$ and
$m$, for any natural number, $m$.  Using this, we show how to express $n$
in the same way.

Before we do the official proof, it's worth describing the problem from a
Computer Science view.  We would like to define a pair of recursive
procedures \texttt{findx} and \texttt{findy}, each with two parameters,
such that \texttt{findx} applied to integers $m$ and $n$ will return an
integer, $x$, and likewise \texttt{findy} applied to integers $m$ and $n$
will return an integer, $y$, such that
\begin{equation}\label{eqmn}
mx+ny= \gcd(m,n),
\end{equation}
providing that $m \geq 0$ and $n > 0$.  Evaluation of \texttt{findx} and
\texttt{findy} applied to integers $m$ and $n$ may make direct recursive
calls of both \texttt{findx} and \texttt{findy} applied to integers $m$
and $r$ for $0 < r <n$.  As you read the following proof, see if you can
extract the definitions of these \texttt{findx} and \texttt{findy}
procedures.

Now for the official proof, we consider any $n \in \naturals$ and assume
the strong induction hypothesis
\begin{equation}\label{SIH2}
\forall k\ 0 < k < n \implies \forall m\, \exists
x_k,y_k\in \integers\ [mx_k+ky_k= \gcd(m,k)].
\end{equation}
in order to prove that $P(n)$ holds.

\textbf{Case 0:} ($n=0$).  $P(0)$ holds trivially.

Now we can prove $P(n)$ for $n>0$ by showing how, given any $m \in
\naturals$, to find integers $x,y$ such that equation~(\ref{eqmn}) holds.
This proof divides into cases:

\textbf{Case 1:} ($m = 0$).  Then $\gcd(m,n) = n$ so we can choose $x = 0$
and $y = 1$ to satisfy~(\ref{eqmn}).

\textbf{Case 2:} ($m \divides n$).  Then $\gcd(m,n) = n$ so we can choose $x = 1$
and $y = 0$ to satisfy~(\ref{eqmn}).

\textbf{Case 3:} $m \neq 0$ and $r>0$ where $r$ is the remainder of $n$
divided by $m$.  Assume without loss of generality that $m \leq n$ (we can do this because we have already taken care of the case where $m=0$ and otherwise we can always relabel $m$ to be the smaller of the two).
Now $1 \leq r <m \leq n$, so by the induction
hypothesis~(\ref{SIH2}) applied with $k=r$, we conclude that there are
natural numbers $x_r,y_r$ such that
\begin{equation}\label{xr}
mx_r+ry_r= \gcd(m,r).
\end{equation}

Now $r=m-qn$ where $q$ is the quotient of $m$ divided by $n$, so
substituting into~(\ref{xr}), yields
\[
mx_r+(m-qn)y_r= \gcd(m,r).
\]
Simplifying the lefthand side and using~(\ref{241}), we conclude
\[
m(x_r+y_r)+n(-qy_r)= \gcd(m,n).
\]
So we can choose $x = (x_r+y_r)$ and $y = -qy_r$ to satisfy~(\ref{eqmn}).

Since Cases 1--3 exhaust the possibilities for $m$, we conclude
that~(\ref{eqmn}) holds for all $m$, completing the proof of $P(n)$.
\end{proof}
}

\end{problem}
