        \problemdata       % Takes 5 *mandatory* arguments
        {vell-dab}             % latex-friendly label for the prob.
        {induction, least number principle}  % The topic(s) of the problem content.
        {Velleman, Exercise 6.4.6}               % Source (if known)
        {F01 PS2-7} % Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
Velleman, Exercise 6.4.6

\solution{
a) Prove that $d \divides a$.  This is a proof using the least number
principle.  We have chosen $d$ so that it is the smallest element of
$S$. Using the division algorithm, we can express $a$ in terms of $d$:
$a = dq+r$ where $0 \leq r < d$. Note that if $a=dq+r$ then
$d=(a-r)/q$.  Using the definition of $S$ we know
that there exists integers $s$ and $t$ such that $d=as+bt$.
Substituting in for $d$ we get $(a-r)/q=as+bt$, which, with a little
bit of algebra, gives us $r=a(1-sq)+b(-tq)$.  Since $(1-sq)$ and
$(-tq)$ are integers, $r$ must be in $S$ if it is not 0.  This
contradicts the choice of $d$ as the smallest element of $S$.  This
proves that $r=0$, so $a=dq$ and therefor $d \divides a$.

Prove that $d \divides b$.  This also is a proof using the least number
principle.  Again, we have chosen $d$ so that it is the smallest
element of 
$S$.  Using the division algorithm, we can express $b$ in terms of
$d$: $b = dq+r$ where $0 \leq r < d$.  Note that if $b=dq+r$ then
$d=(b-r)/q$.  Using the definition of $S$ we know
that there exists integers $s$ and $t$ such that $d=as+bt$.
Substituting in for $d$ we get $(b-r)/q=as+bt$, which, with a little
bit of algebra, gives us $r=a(-sq)+b(1-tq)$.  Since $(-sq)$ and
$(1-tq)$ are integers, $r$ must be in $S$ if it is not 0.  This
contradicts the choice of $d$ as the smallest element of $S$.  This
proves that $r=0$, so $b=dq$ and therefor $d \divides b$.

b) If $c$ divides $a$ then there exists some integer $p$ such that
$a=cp$.  Similarly, if $c$ divides $b$ then there exists some integer
$q$ such that $b=cq$.  Since $d \in S$ we know that $d=as+bt$, which,
given $c$ divides both $a$ and $b$, is $d=acs+bct=c(as+bt)$, showing
that $c \divides d$.
}

\end{problem}