Commentary on Euclid's Algorithm and Diophantine Equations
Last updated 24jun13

\begin{document}
\maketitle

\section{Introduction}
In the interest of efficiency and clarity we depart from out usual approach
of commenting on the textbook. The D'Angelo-West text, Chapter 6 and 7, are
at best a resource for you to study if needed, and a source of assigned
problems. But study the homework assigment. You are to use the prime
decomposition whenever possible, and, even more important, you are to use
everything that is covered in class, and summarized here.

\section{Euclid's Algorithm}
We began with Euclid's Principle of \textit{ anthyphairesis}, which is
pronounced something like "anti fareysis". Roughly translated
it means \textbf{take the lesser from the greater}, i.e. recursively subtract
the smaller from the larger of two quantities. This leaves two quantities,
the larger of which is what was the smaller before. Unless, of course, they
are equal. In that case, the algorihtm cannot continue, because there is no
longer a larger and a smaller!

Here is a very good paper on this subject by Prof.
Paul Hewitt  of Toledo University. But you
may prefer to read the rest of this lesson first.

\subsection{The Story of King Midas's Golden Tiled Floor}
Once upon a time there was a fabulously wealthy king whose palaces
along the southern shore of the Black Sea were the envy of his neighbors.
That the reason for his wealth was the ability to turn into gold anything
King Midas touched is irrelevant here. But he did want to tile the floor
of a huge, perfectly rectangular room with golden, square tiles. He wanted
them to be as uniformly large as possible so that he could save money
by having to lay the fewest tiles. And, here's the rub, no tiles may be cut,
he decreed, or altered in any way.

He called upon his Grand Vizier, a slave geometer who had studied with
Euclid, and gave him the order to figure out how to solve this problem
or the vizier would lose his head! Since the workers were ignorant and
couldn't do numbers anyway, there was no point in trying to measure the
square that fit, namely one the size of the shorter side of the room.
Lay out the room with those, and if there was nothing left over at the far
end of the room, the problem was solved. Otherwise, there would be smaller
rectangle left over. Repeat the process, with the largest square that fit
into the smaller rectangle. Again, if this tile filled out the second
rectangle, the problem was solved, becaue that size tile would automatically
tile the original squares perfectly. If again there is a rectangle left
over, repeat.  Eventually, a solution would be found.

Unhappily, the Vizier did not live to see his grandchildren. Why did he

\subsubsection{Euclid's Algorithm}
See the figure at the top that shows why Euclid's algorithm
always ends for two natural numbers. You don't have to read French
to understand it.  The golden rectangle shows why the
algorithm does not always stop. And in the next and final part of the course,
when we study the real numbers, we will see how Euclid's algorithm gives
a practical definition of what an irrational numbers is. This may not
be the way you learned it high school, but it is equivalent to it,
as we shall see.

\subsubsection{An example}
\textbf{Theorem: } Euclid's algorithm applied to whole numbers ends with the
final remainder equal to their \textit{greatest common divisor} (gcd).

Consider Euclid's Algorithm applied to $(17,5)$:
\begin{eqnarray*}
17 &=& 5q_1 + 2 \\
5 &=& 2q_2 + 1 \\
---&--&---------\\
2 &=& 1q_3 + 0 \\
1 &\ne& 0q_4 + ? \\
\end{eqnarray*}
Note why we must have a stopping rule, else the algorithm ends in nonsense.
On the other hand, the stopping rule is always the same: \textbf{The gcd is
the last non-zero remainder of this succesion of long divisions.}

So $1 = gcd(17,5)$. Note that we can solve $17x + 5y = 1$ as follows:
\begin{eqnarray*}
1 &=& 5 - 2q_2 \\
1 &=& 5 - (17-5q_1)q_2 \\
1 &=& 17(-q_2) + 5(1+q_1q_2) \\
1 &=& 17(-2) + 5(7) \\
\end{eqnarray*}
The 3rd line shows \textbf{ that } there is a solution, and evaluating
the quotients, shows you an explicit solution in the last line.
Scaling the above argument by $2$ applies the algorithm to find a
solution to the \textit{Diophantine Equation} $34x + 10y = 2$, namely the
same values $(x,y) = (-4,14)$. But observe that we can shift the factor
\begin{eqnarray*}
2 & = & 34(-2) + 10(7)\\
2 & = & 17(-4) + 5(14)\\
\end{eqnarray*}
and thereby find a solution to the $2 = 17x + 5y$ as well.

Question 1 : What is a solution to $42 = 17x + 5y$ ?

\textbf{Theorem: } The Diophantine equation $ax +by = c$ has a solution
if and only if $d = gcd(a,b)$ divides $c$, i.e. $c = de$ for some $e$.

\textbf{ Proof:} If $au + bv = d$ from Euclid's algorithm or wherever,
then $c = de = a(ue) + b(ve)$. The converse follows from  a different
factorization $c = ax+by=(da')x + (db')y = d(a'x + b'y) = de$. QED

\textbf{Theorem: } Every solution of $ax+by=c$ has the form
$(x,y) = (x_0 + mb', y_0 + ma')$ where $(a',b')= (\frac{a}{d},\frac{b}{d})$.

\textbf{ Proof } Subtract
\begin{eqnarray*}
ax_0 + by_0&=&c \\
ax_1 + by_1&=&c \\
a(x_1-x_0) + b(y_1 -y_0)&=&0 \mbox{ divide out by } d \\
a'(x_1-x_0) + b'(y_1 -y_0)&=&0 \\
a'(x_1-x_0) &=&  b'(y_0 -y_1) \mbox{ match the prime decompositions }\\
\mbox( Big Step ) a'(b'm) &=&  b'(a'm) \\
(x_1-x_0) &=& b'm \\
(y_0-y_1) &=& a'm \\
(x_1,y_1) &=& (x_0 + mb', y_0 - ma')= (x_0,y_0)+m(b',-a') \\
\end{eqnarray*}
The only mystery is the Big Step. If we look at the prime decompositions
of the LHS and the RHS, all the primes in $a'$ have to be in the $(y_0-y_1)$
factor because $b'$ is relatively prime to $a'$. Similarly for the primes
belonging to $b'$. So matching those up, leaves the same product $m$ of
of primes left over. QED

Question 2: So, what are ALL solutions to $34x+10y = 6$ ?

\end{document}