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


\begin{problem}
Let $m,n$ be integers, and assume at least one of $m$ and $n$ is nonzero.
Define a set of integers, $L_{m,n}$, recursively as follows:
\begin{itemize}
\item \textbf{base cases}: $m,n,-m,-n \in L_{m,n}$.
\item \textbf{recursive step}: If $k,l \in L_{m,n}$, then $k+l \in L_{m,n}$.
\end{itemize}


\begin{problemparts}

\problempart \label{Lmx+ny}  Show that
\[
L_{m,n} = \set{mx+ny \suchthat x,y \in \integers}.
\]

\solution{
We need to prove two statements:  firstly, that every number of the
form $mx+ny$ is in $L_{m,n}$; secondly, that every member of $L_{m,n}$
has this form.

\begin{itemize}
\item
To show that $\forall x, y\in \integers, mx+ny\in L_{m,n}$: we do this with two induction
proof steps.  Note that we can only run induction on the \emph{nonnegative}
integers, so we extend our proof slightly.
\begin{itemize}
\item
\textbf{Induction Hypothesis}:  
\begin{equation}\label{indhyp1}
P(x)\eqdef\set{mx, -mx}\subset L_{m,n}
\end{equation}
\textbf{Base case}: $m\cdot 0=m+(-m)\in L_{m,n}$

\textbf{Inductive step}: If $mx$ and $-mx$ are in $L_{m,n}$ then so
are $m(x+1)=mx+m$ and $-m(x+1)=-mx+(-m)$.

So equation~\ref{indhyp1} holds for all nonnegative integers $x$.
\item
\textbf{Induction Hypothesis}:  
\begin{equation}\label{indhyp2}
Q(y)\eqdef\forall x\in\integers,\set{mx+ny, mx-ny}\subset L_{m,n}
\end{equation}
\textbf{Base case}: $mx+n\cdot 0=mx\in L_{m,n}$, from
eqn.~\ref{indhyp1}, this holds for all integers $x$.

\textbf{Inductive step}: If $mx+ny$ and $mx-ny$ are in $L_{m,n}$ then so
are $mx+n(y+1)=mx+ny+n$ and $mx-n(y+1)=mx-ny+(-n)$.

So equation~\ref{indhyp2} holds for all nonnegative integers $y$.
This completes the proof.
\end{itemize}
\item
To show that every member of $L_{m,n}$ has the form $mx+ny$: note that
it's true for the base cases $m, -m, n, -n$ because $m=m\cdot 1+n\cdot
0$, etc.  Now let's look at our recursive step:  suppose true for $k,
l$.  Numerically
\begin{eqnarray*}
k&=&mx_k+ny_k\\
l&=&mx_l+ny_l\\
\Rightarrow k+l&=&mx_k+ny_k+mx_l+ny_l=m(x_k+x_l)+n(y_k+y_l)
\end{eqnarray*}
In other words, the newly added element also has the requisite form.
It follows inductively that all elements of $L_{m,n}$
have the form $mx+ny$ for some integers $x$ and $y$.
\end{itemize}
}

\problempart \label{common}

Prove that any common divisor of $m$ and $n$ also divides every member of
$L_{m,n}$.

\solution{ If $k \in L_{m,n}$, then by part~(\ref{Lmx+ny}), $k = mx+ny$.
Now if $d$ is a common divisor of $m$ and $n$, then it divides $mx$ and
$ny$, and hence divides their sum $mx+ny$.  So $d$ also divides $k$.

\iffalse

\begin{proof} (by Induction)
The induction hypothesis is
\[
P(k) \eqdef\quad k \in L_{m,n} \implies \forall l\ (l \divides m \land l \divides
n) \implies l \divides k.
\]

\textbf{Base case}: $P(m)$ is immediate, since any common divisor of $m$ and
$n$ certainly divides $m$.  Likewise for $P(n)$.

\textbf{Recursive case}: Suppose $k,l \in L_{m,n}$.  Assume $P(k)$ and
$P(l)$, in order to prove $P(k+l)$.

So suppose $j$ is a common divisor of $m$ and $n$.  Then $j \divides k$ by
hypothesis $P(k)$ and $j \divides l$ by hypothesis $P(l)$.  That is, $k = pj$
and $l= qj$ for some $p,q \in \integers$.  Hence $k+l = pj+qj = j(p+q)$.
So we have $j \divides k+l$, and we conclude that $P(k+l)$ holds.
\end{proof}
\fi

}


\problempart

Show that if $k,l \in L_{m,n}$ then the remainder of $k$ divided by $l$ is
in $L_{m,n}$.

\solution{Say $r$ is the remainder of $k$ divided by $l$.  That is, $0
\leq r < l$ and $k = ql+r$ for some $q \in \integers$.

Since $k,l \in L_{m,n}$ we have as in part~(\ref{Lmx+ny}) that $k+ (-q)l
\in L_{m,n}$.  That is, $r \in L_{m,n}$.}

\problempart \label{g}

Show that there is a positive integer $g \in L_{m,n}$ which divides every
member of $L_{m,n}$.  \hint The least positive integer in $L_{m,n}$.

\solution{At least one of the integers $m, -m, n, -n \in L_{m,n}$ must be
positive.  Hence by the Least Number Principle, there is a least positive
integer $g \in L_{m,n}$.

Suppose $k \in L_{m,n}$.  We must show that $g \divides k$.

We prove this by contradiction: if $g$ does not divide $k$, then the
remainder of $k$ divided by $g$ is a positive number smaller than $g$,
which by the previous part is in $L_{m,n}$, contradicting the fact that
$g$ is the smallest such integer.
}

\problempart Conclude that $\gcd(m,n) = mx+ny$ for some $x,y \in \integers$.

\solution{From part~(\ref{g}), we have a positive integer $g \in L_{m,n}$
that divides every element of $L_{m,n}$.  By part~(\ref{Lmx+ny}), $g
=mx+ny$ for some $x,y \in \integers$.  Also, $g$ is a common divisor of
$m,n$, since $m,n \in L_{m,n}$.  But by part~(\ref{common}), any common
divisor of $m$ and $n$ divides $g$.  Hence, $g = \gcd(m,n)$.}


\end{problemparts}

\end{problem}
