\problemdata                                                             
        {GCD} % latex-friendly label for the prob.
        {Well-ordering} % The topic(s) of the problem content.  
        {fall00} % Source (if known)                                          
        {S01 Tutorial 4, 2} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
The well-ordering property can be used to show that there is a unique
greatest common divisor of two positive integers. Let $a$ and $b$
be positive integers, and let $S$ be the set of positive integers of the
form $as+bt$, where $s$ and $t$ are integers.
\begin{enumerate} \setlength{\itemsep}{0pt} \item Show that $S$ is nonempty.
\item Use the well-ordering property to show that $S$ has a smallest
  element $c$.
\item Show that if $d$ is a common divisor of $a$ and $b$, then $d$ is
  a divisor of $c$.
\item Show that $c \mid a$ and $c \mid b$. (Hint: First, assume that
  $c \nmid a$.  Then $a=qc+r$, where $0<r<c$. Show that $r \in S$,
  contradicting the choice of $c$.)
\item Conclude from (c) and (d) that the greatest common divisor of
  $a$ and $b$ exists. Finish the proof by showing that this greatest
  common divisor of two positive integers is unique.
\end{enumerate}

\renewcommand{\labelenumi}{\alph{enumi})}
\solution{
\medskip

\begin{enumerate} \setlength{\itemsep}{0pt}
\item For example, just set $s=1$, and $t=1$.  Then $as+bt = a+b$,
  which is a positive integer by our definitions of $a$ and $b$.
\item The Well Ordering Property states that every non-empty set of
  non-negative integers has a smallest member.  Since we just showed
  in part a that the set $S$ is non-empty, it must have a smallest
  member, which we may call $c$.
\item If $d$ divides $a$ and $b$, then $d$ divides $as$ and $bt$ for
  any positive integers $a$ and $b$.  Therefore, $d$ also divides the
  sum $as+bt$.  Since $c \in S$, c must be such a sum, by our
  definition of membership in $S$.  Therefore, $d$ can divide $c$.
  
  
\item We will just show $c \mid a$, as the argument is identical to
  show $c \mid b$.\\
  Proof by Contradiction.\\
  Assume for the purpose of contradiction that $c \nmid a$.\\
  If $c$ does not evenly divide into $a$, then we can write the expression $a = qc + r$, for some postive integer $r$, where $0<r<c$.\\
  We can rewrite this in terms of $r$: $r=a-qc$.\\
  Now, since $c \in S$, we know that $c$ is of the form $c=as+bt$, for some integral values of $s$ and $t$.  Rewriting our expression for $r$ again, we get:\\
  $r=a-qc = a-q(as+bt)=a-aqs-qbt=a(1-qs)+b(-qt).$ But now we are done,
  because we have expressed the positive integer $r$ as a linear
  combination with integer coefficients of $a$ and $b$.  This means
  that $r \in S$, which we know is not possible since $r<c$.  Thus, we
  have a contradiction, and our assumption that $c \nmid a$
  must be wrong, so we can conclude that $c \mid a$.
  
\item Finally, by part (d), $c$ is a divisor of both $a$ and $b$.
  Furthermore, from part (c) we know that any divisor of both $a$ and
  $b$ is also a divisor of $c$.  This means that every common divisor
  of $a$ and $b$ is no greater than $c$, and so $c$ is the greatest
  common divisor of $a$ and $b$.  To see that the greatest common
  divisor of a number is unique, one just needs to note that it makes
  no sense to have two numbers, each of which is greater than the
  other.
\end{enumerate}
}                                  

\end{problem}
                                 