\section{The Greatest Common Divisor}
\label{sec:gcd}

We've already examined the Euclidean Algorithm for computing $\gcd(a, b)$,
the greatest common divisor of $a$ and $b$.  This quantity turns out to be
a very valuable piece of information about the relationship between $a$
and $b$.  We'll be making arguments about greatest common divisors all
the time.

\hyperdef{gcd}{linear}{\subsection{Linear Combinations and the GCD}}

The theorem below relates the greatest common divisor to linear
combinations.  This theorem is \textit{very} useful; take the time to
understand it and then remember it!

\begin{theorem}
\label{th:gcd}
The greatest common divisor of $a$ and $b$ is equal to the smallest
positive linear combination of $a$ and $b$.
\end{theorem}

For example, the greatest common divisor of 52 and 44 is 4.  And, sure
enough, 4 is a linear combination of 52 and 44:
%
\[
6 \cdot 52 + (-7) \cdot 44  =  4
\]
%
Furthermore, no linear combination of 52 and 44 is equal to a smaller
positive integer.

\begin{proof}
By the well-ordering principle, there is a smallest positive linear
combination of $a$ and $b$; call it $m$.  We'll prove that $m = \gcd(a,
b)$ by showing both $\gcd(a, b) \leq m$ and $m \leq \gcd(a, b)$.

First, we show that $\gcd(a, b) \leq m$.  Now any common divisor of $a$
and $b$, that is, any $c$ such that $c \divides a$ and $c \divides b$ will
divide both $sa$ and $tb$, and therefore also divides $sa+tb$.   The
$\gcd(a, b)$ is by definition a common divisor of $a$ and $b$, so
%
\[
\gcd(a, b) \divides s a + t b
\]
every $s$ and $t$.
%
In particular, $\gcd(a, b) \divides m$, which implies that $\gcd(a, b)
\leq m$.

Now, we show that $m \leq \gcd(a, b)$.  We do this by showing that $m
\divides a$.  A symmetric argument shows that $m \divides b$, which means
that $m$ is a common divisor of $a$ and $b$.  Thus, $m$ must be less than
or equal to the \textit{greatest} common divisor of $a$ and $b$.

All that remains is to show that $m \divides a$.  By the Division
Algorithm, there exists a quotient $q$ and remainder $r$ such that:
%
\[
a = q \cdot m + r \hspace{1in} \text{(where $0 \leq r < m$)}
\]
%
Recall that $m = s a + t b$ for some integers $s$ and $t$.
Substituting in for $m$ and rearranging terms gives:
%
\begin{align*}
a & = q \cdot (s a + t b) + r \\
r & = (1 - qs) a + (-qt) b
\end{align*}
%
We've just expressed $r$ as a linear combination of $a$ and $b$.
However, $m$ is the \textit{smallest} positive linear combination and
$0 \leq r < m$.  The only possibility is that the remainder $r$ is not
positive; that is, $r = 0$.  This implies $m \divides a$.
\end{proof}

The proof notes that every linear combination of $a$ and $b$ is a
multiple of $\gcd(a, b)$.  Conversely, since $\gcd(a, b)$ is a linear
combination of $a$ and $b$, every multiple of $\gcd(a, b)$ is as well.
This establishes a corollary:

\begin{corollary}
\label{cor:lin-comb}
Every linear combination of $a$ and $b$ is a multiple of $\gcd(a, b)$
and vice versa.
\end{corollary}

Now we can restate the water jugs lemma in terms of the greatest
common divisor:

\begin{corollary}
\label{cor:waterjugs}
Suppose that we have water jugs with capacities $a$ and $b$.  Then the
amount of water in each jug is always a multiple of $\gcd(a, b)$.
\end{corollary}

For example, there is no way to form 2 gallons using 1247 and 899 gallon
jugs, because 2 is not a multiple of $\gcd(1247, 899) = 29$.


\subsection{Properties of the Greatest Common Divisor}

We'll often make use of some basic $\gcd$ facts:

\begin{lemma} The following statements about the greatest common divisor hold:
\label{lem:gcd}
%
\begin{enumerate}
\item Every common divisor of $a$ and $b$ divides $\gcd(a, b)$.
\item $\gcd(k a, k b) = k \cdot \gcd(a, b)$ for all $k > 0$.
\item\label{gcd3} If $\gcd(a, b) = 1$ and $\gcd(a, c) = 1$, then $\gcd(a, bc) =
1$.
\item If $a \divides b c$ and $\gcd(a, b) = 1$, then $a \divides c$.
\item\label{gcd5} $\gcd(a, b) = \gcd(b, \rem{a}{b})$.
\end{enumerate}
\end{lemma}

Here's the trick to proving these statements: translate the $\gcd$
world to the linear combination world using Theorem~\ref{th:gcd},
argue about linear combinations, and then translate back using
Theorem~\ref{th:gcd} again.

\begin{proof}
We prove only parts 3.\ and 4.

Proof of 3.: The assumptions together with Theorem~\ref{th:gcd} imply
that there exist integers $s$, $t$, $u$, and $v$ such that:
%
\begin{align*}
s a + t b & = 1 \\
u a + v c & = 1
\end{align*}
%
Multiplying these two equations gives:
\[
(s a + t b)(u a + v c) = 1
\]
%
The left side can be rewritten as $a \cdot (a s u + b t u + c s v) + b c
(t v)$.  This is a linear combination of $a$ and $b c$ that is equal to 1,
so $\gcd(a, bc) = 1$ by Theorem~\ref{th:gcd}.

Proof of 4.: Theorem~\ref{th:gcd} says that $\gcd(ac, bc)$ is equal to a
linear combination of $ac$ and $bc$.  Now $a \divides ac$ trivially and $a
\divides bc$ by assumption.  Therefore, $a$ divides \textit{every} linear
combination of $ac$ and $bc$.  In particular, $a$ divides $\gcd(ac, bc) =
c \cdot \gcd(a, b) = c\cdot 1 = c$.  The first equality uses part 2.\ of
this lemma, and the second uses the assumption that $\gcd(a, b) = 1$.
\end{proof}

Lemma~\ref{lem:gcd}, part 5.\ is the fact we assumed when we proved
correctness of the Euclidean Algorithm.

Now let's see if it's possible to make 3 gallons using 21 and 26-gallon
jugs.  Using
Euclid's algorithm:
%
\[
\gcd(26, 21) = \gcd(21, 5) = \gcd(5, 1) = 1.
\]
%
Now 3 is a multiple of 1, so we can't \textit{rule out} the possibility
that 3 gallons can be formed.  On the other hand, we don't know it can be
done.

\subsection{One Solution for All Water Jug Problems}

Can Bruce form 3 gallons using 21 and 26-gallon jugs?  This question
is not so easy to answer without some number theory.

Corollary~\ref{cor:lin-comb} says that 3 can be written as a linear
combination of 21 and 26, since 3 is a multiple of $\gcd(21, 26) = 1$.
In other words, there exist integers $s$ and $t$ such that:
%
\[
3 = s \cdot 21 + t \cdot 26
\]
%
We don't know what the coefficients $s$ and $t$ are, but we do know
that they exist.

Now the coefficient $s$ could be either positive or negative.
However, we can readily transform this linear combination into an
equivalent linear combination
%
\[
3 = s' \cdot 21 + t' \cdot 26
\]
%
where the coefficient $s'$ is positive.  The trick is to notice that
if we increase $s$ by 26 in the original equation and decrease $t$ by
21, then the value of the expression $s \cdot 21 + t \cdot 26$ is
unchanged overall.  Thus, by repeatedly increasing the value of $s$
(by 26 at a time) and decreasing the value of $t$ (by 21 at a time),
we get a linear combination $s' \cdot 21 + t' \cdot 26 = 3$ where the
coefficient $s'$ is positive.  Notice that $t'$ must be negative;
otherwise, this expression would be much greater than 3.

Now here's how to form 3 gallons using jugs with capacities 21 and 26:

Repeat $s'$ times:
\begin{enumerate}
\item Fill the 21-gallon jug.
\item Pour all the water in the 21-gallon jug into the 26-gallon jug.
Whenever the 26-gallon jug becomes full, empty it out.
\end{enumerate}
%
At the end of this process, there must be exactly 3 gallons in the
26-gallon jug!  Here's why: we've taken $s' \cdot 21$ gallons of water
from the fountain, we've poured out some multiple of 26 gallons, and
in the end the 26-gallon jug holds somewhere between 0 and 26 gallons.
Furthermore, we know:
%
\[
s' \cdot 21 + t' \cdot 26 = 3
\]
%
Thus, we must have emptied the 26-gallon jug exactly $-t'$ times; if
we had emptied it fewer times, then there would be more than 26
gallons left.  And we did not withdraw enough water from the fountain
to empty the 26-gallon jug more than $-t'$ times.  Thus, by the
equation above, there must be exactly 3 gallons left.

Remarkably, we don't even need to know the coefficients $s'$ and $t'$
in order to use this strategy!  Instead of repeating the outer loop
$s'$ times, we could just repeat \textit{until we obtain 3 gallons},  
since that must happen eventually.  Of course, we have to keep track
of the amounts in the two jugs so we know when we're done.  Here's the
solution that approach gives:
%
\[
\begin{array}{ccccccccc}
(0,0) & \xrightarrow{\text{fill 21}} & (21,0)& \xrightarrow{\text{pour 21 into 26}} & (0,21)\\
& \xrightarrow{\text{fill 21}} & (21,21)& \xrightarrow{\text{pour 21 into 26}} & (16,26)& \xrightarrow{\text{empty 26}} & (16,0)& \xrightarrow{\text{pour 21 into 26}} & (0,16)\\
& \xrightarrow{\text{fill 21}} & (21,16)& \xrightarrow{\text{pour 21 into 26}} & (11,26)& \xrightarrow{\text{empty 26}} & (11,0)& \xrightarrow{\text{pour 21 into 26}} & (0,11)\\
& \xrightarrow{\text{fill 21}} & (21,11)& \xrightarrow{\text{pour 21 into 26}} & (6,26)& \xrightarrow{\text{empty 26}} & (6,0)& \xrightarrow{\text{pour 21 into 26}} & (0,6)\\
& \xrightarrow{\text{fill 21}} & (21,6)& \xrightarrow{\text{pour 21 into 26}} & (1,26)& \xrightarrow{\text{empty 26}} & (1,0)& \xrightarrow{\text{pour 21 into 26}} & (0,1)\\
& \xrightarrow{\text{fill 21}} & (21,1)& \xrightarrow{\text{pour 21 into 26}} & (0,22)\\
& \xrightarrow{\text{fill 21}} & (21,22)& \xrightarrow{\text{pour 21 into 26}} & (17,26)& \xrightarrow{\text{empty 26}} & (17,0)& \xrightarrow{\text{pour 21 into 26}} & (0,17)\\
& \xrightarrow{\text{fill 21}} & (21,17)& \xrightarrow{\text{pour 21 into 26}} & (12,26)& \xrightarrow{\text{empty 26}} & (12,0)& \xrightarrow{\text{pour 21 into 26}} & (0,12)\\
& \xrightarrow{\text{fill 21}} & (21,12)& \xrightarrow{\text{pour 21 into 26}} & (7,26)& \xrightarrow{\text{empty 26}} & (7,0)& \xrightarrow{\text{pour 21 into 26}} & (0,7)\\
& \xrightarrow{\text{fill 21}} & (21,7)& \xrightarrow{\text{pour 21 into 26}} & (2,26)& \xrightarrow{\text{empty 26}} & (2,0)& \xrightarrow{\text{pour 21 into 26}} & (0,2)\\
& \xrightarrow{\text{fill 21}} & (21,2)& \xrightarrow{\text{pour 21 into 26}} & (0,23)\\
& \xrightarrow{\text{fill 21}} & (21,23)& \xrightarrow{\text{pour 21 into 26}} & (18,26)& \xrightarrow{\text{empty 26}} & (18,0)& \xrightarrow{\text{pour 21 into 26}} & (0,18)\\
& \xrightarrow{\text{fill 21}} & (21,18)& \xrightarrow{\text{pour 21 into 26}} & (13,26)& \xrightarrow{\text{empty 26}} & (13,0)& \xrightarrow{\text{pour 21 into 26}} & (0,13)\\
& \xrightarrow{\text{fill 21}} & (21,13)& \xrightarrow{\text{pour 21 into 26}} & (8,26)& \xrightarrow{\text{empty 26}} & (8,0)& \xrightarrow{\text{pour 21 into 26}} & (0,8)\\
& \xrightarrow{\text{fill 21}} & (21,8)& \xrightarrow{\text{pour 21 into 26}} & (3,26)& \xrightarrow{\text{empty 26}} & (3,0)& \xrightarrow{\text{pour 21 into 26}} & (0,3)
\end{array}
\]
%

The same approach works regardless of the jug capacities and even
regardless the amount we're trying to produce!  Simply repeat these two
steps until the desired amount of water is obtained:
\begin{enumerate}
\item Fill the smaller jug.
\item Pour all the water in the smaller jug into the larger jug.
Whenever the larger jug becomes full, empty it out.
\end{enumerate}

By the same reasoning as before, this method eventually generates every
multiple of the greatest common divisor of the jug capacities ---all the
quantities we can possibly produce.  No ingenuity is needed at all!


\subsection{The Pulverizer}
\label{sec:pulverizer}

We saw that no matter which pair of integers $a$ and $b$ we
are given, there is always a pair of integer coefficients $s$ and $t$
such that     
\[
\gcd(a, b)  =  s a + t b.
\]
The previous subsection gives a roundabout and not very efficient method
of finding such coefficients $s$ and $t$.  In the Notes on State Machines
we defined and verified the ``Extended Euclidean GCD algorithm'' which is
a much more efficient way to find these coefficients.  In this section we
give a more straightforward description of this procedure for finding $s$
and $t$ that dates to sixth-century India, where it was called {\em
kuttak}, which means ``The Pulverizer.''

Suppose we use Euclid's Algorithm to compute the GCD of 259 and 70, for
example:
\[
\begin{array}{rclcl}
\gcd(259, 70)
    & = & \gcd(70, 49) & \quad & \text{since $\rem{259}{70} = 49$}\\
    & = & \gcd(49, 21) && \text{since $\rem{70}{49} = 21$} \\
    & = & \gcd(21, 7) && \text{since $\rem{49}{21} = 7$} \\
    & = & \gcd(7, 0) && \text{since $\rem{21}{7} = 0$} \\
    & = & 7.
\end{array}
\]
The Pulverizer goes through the same steps, but requires some extra
bookkeeping along the way: as we compute $\gcd(a, b)$, we keep track
of how to write each of the remainders (49, 21, and 7, in the example)
as a linear combination of $a$ and $b$ (this is worthwhile, because
our objective is to write the last nonzero remainder, which is the
GCD, as such a linear combination).  For our example, here is this
extra bookkeeping:
\[
\begin{array}{ccccrcl}
x & \quad & y & \quad & (\rem{x}{y}) & = & x - q \cdot y \\ \hline
259 && 70 && 49 & = &   259 - 3 \cdot 70 \\
70 && 49 && 21  & = &   70 - 1 \cdot 49 \\
&&&&            & = &   70 - 1 \cdot (259 - 3 \cdot 70) \\
&&&&            & = &   -1 \cdot 259 + 4 \cdot 70 \\
49 && 21 && 7   & = &   49 - 2 \cdot 21 \\
&&&&            & = &   (259 - 3 \cdot 70) -
                                2 \cdot (-1 \cdot 259 + 4 \cdot 70) \\
&&&&            & = &   \fbox{$3 \cdot 259 - 11 \cdot 70$} \\
21 && 7 && 0
\end{array}
\]
We began by initializing two variables, $x = a$ and $y = b$.  In the
first two columns above, we carried out Euclid's algorithm.  At each
step, we computed $\rem{x}{y}$, which can be written in the form $x - q
\cdot y$.  (Remember that the Division Algorithm says $x = q \cdot y +
r$, where $r$ is the remainder.  We get $r = x - q \cdot y$ by
rearranging terms.)  Then we replaced $x$ and $y$ in this equation
with equivalent linear combinations of $a$ and $b$, which we already
had computed.  After simplifying, we were left with a linear
combination of $a$ and $b$ that was equal to the remainder as desired.
The final solution is boxed.

\endinput