\magnification=\magstep1
\centerline{Mathematics 243, section 1 -- Algebraic Structures}
\centerline{Discussion 3 -- Greatest Common Divisors}
\centerline{October 10, 2003}
\bigskip
\noindent
{\it Background}
\bigskip
\noindent
From before the exam, recall that we discussed the following ideas:
\bigskip
\item{$\bullet$} if $a$ and $b$ are two integers, then an integer $c$ is 
a {\it common divisor\/} of $a$ and $b$ if $c|a$ and $c|b$.  
\item{$\bullet$}  We say $d$ is a
{\it greatest common divisor}, or gcd, of $a$ and $b$ if all three
of the following statements are true:
\itemitem{1)}  $d \in {\bf Z}^+$,
\itemitem{2)}  $d|a$ and $d|b$, and
\itemitem{3)}  if $c|a$ and $c|b$, then $c|d$.  
\bigskip
\item{$\bullet$} For example, a greatest common divisor of 
$a = 240$ and $b = 504$ is 
$d = 24$, which we can see by factoring:
$$240 = 2^4\cdot 3\cdot 5\quad {\rm and}\quad  504 = 2^3\cdot 3^2 \cdot 7$$
\noindent
However, factoring large numbers can be hard (especially
if there are no small factors).  Hence we want to consider today 
a better method for computing gcd's for large $a,b$, based on one of the other facts
we proved before the exam:
\bigskip
\item{$\bullet$}  Given $a,b\in {\bf Z}$, we
considered the set
$$S_{a,b} = \{ ma + nb : m, n \in {\bf Z}\}\leqno(1)$$
We showed that if $d$ is the smallest element in 
$S_{a,b}^+ = S_{a,b} \cap {\bf Z}^+$,
then $d$ is a gcd of $a,b$.
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\item{A)}  Show that if $a,b$ are integers and $b > 0$, then 
the remainder on division of $a$ by $b$ is one of the elements of
the set $S_{a,b}$.
\item{B)}  This observation suggests one method for finding the gcd, 
namely:  Construct elements in the set $S_{a,b}$ from (1) by taking remainders,
and try to identify the smallest positive element in that set by finding
a remainder as small as possible.  Try this 
for $a = 5673$ and $b = 305$.  What is the smallest strictly 
positive number you find? Can you show there aren't any smaller elements 
of $S$? 
\item{C)}  A systematic procedure for doing the kind of search for 
small elements of $S$ you did in B is known as {\it Euclid's Algorithm}.  
It can be phrased like this:  Start with $a > b > 0$, and compute the 
quotient and remainder: $a = q_1b + r_1$. Then divide $r_1$ into 
$b$ to yield $b = q_2r_1 + r_2$.  Then divide $r_2$ into 
$r_1$ to yield $r_1 = q_3r_2 + r_3$, and so on.  If you ``stack'' the 
resulting equations you will see a pattern that should help you to 
remember the process:
$$\eqalign{a &= q_1b + r_1\cr
           b &= q_2r_1 + r_2\cr
         r_1 &= q_3r_2 + r_3\cr
             &\vdots\cr}$$
\itemitem{1)}  Explain why eventually you will get a remainder $r_n = 0$.
(Hint: What is true about $r_1$ versus $b$, $r_2$ versus $r_1$, etc.)
\itemitem{2)}  Explain why  $r_i \in S$ for all $i \ge 1$.  
\bigskip
\item{D)} In fact, 
$$r_n = 0\ {\rm but}\ r_{n-1}\ne 0 \Rightarrow r_{n-1} = gcd(a,b).$$ 
Use the Euclidean Algorithm to find the gcd of 
\itemitem{1)}  $a = 1400$, $b = 980$.
\itemitem{2)}  $693$, $b = 414$.
\bigskip
\noindent
{\bf Assignment}
\bigskip
Group write-ups due Friday, October 17.
\bye