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 room. Instead, the Vizier suggested that they start with the largest possible 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 lose his head? \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}