### Approximations, Euclid's Algorithm & Continued Fractions

This article sets some puzzles and describes how Euclid's algorithm and continued fractions are related.

### Euclid's Algorithm II

We continue the discussion given in Euclid's Algorithm I, and here we shall discover when an equation of the form ax+by=c has no solutions, and when it has infinitely many solutions.

### Solving with Euclid's Algorithm

A java applet that takes you through the steps needed to solve a Diophantine equation of the form Px+Qy=1 using Euclid's algorithm.

# BT.. Eat Your Heart Out

##### Stage: 5 Challenge Level:

Two excellent solutions follow, one from Elizabeth Whitmore of Madras College, St Andrew's, which uses Euclid's algorithm and the other, which uses a computer program, from Serguey and Ilya from the International School of The Hague. First Serguey and Ilya's solution.

Let $x$ be the three digit number at the start.

Let $y$ be the four digit number at the end of the phone number.

The original phone number is $10000x + y$. The changed phone number is $1000y + x$.

The new number is one more than the old number doubled so $$20000x + 2y + 1 = 1000y + x$$ $$19999x + 1 = 998y.$$ There are an infinite number of solutions to this equation.

We wrote the following program to test integer solutions:


Module1 - 1

Sub bbbbbbb ()

y = 2004

For x = 100 to 999

y = (19999 * x + 1) / 998

If y = Int(y) Then Debug.Print x; y

Next x

End Sub





The answer is: 435 8717
Elizabeth solved this equation $$998y-19999x = 1$$ using Euclid's algorithm, as follows:

\begin{eqnarray} \\ {\bf 19,999} &=& 998\times 20 + 39\\ \mathbf{998} &=& \mathbf{39}\times 25 + 23\\ \mathbf{39} &=& \mathbf{23}\times 1 + 16\\ \mathbf{23} &=& \mathbf{16}\times 1 + 7\\ \mathbf{16} &=& \mathbf{7}\times 2 + 2\\ \mathbf{7} &=& \mathbf{2}\times 3 + 1\\ \mathbf{2} &=& \mathbf{1}\times 2 + 0. \end{eqnarray}

Working backwards to get values for $x$ and $y$:

\begin{eqnarray} 1 &=& {\bf 7}-3\times {\bf 2}\\ &=& {\bf 7}-3\times ({\bf 16}-2\times {\bf 7})\\ &=& 7\times {\bf 7}-3\times {\bf 16}\\\ &=& 7\times ({\bf 23}-{\bf 16})-3\times {\bf 16}\\ &=& 7\times {\bf 23}-10\times {\bf 16}\\ &=& 7\times {\bf 23}-10\times ({\bf 39}-{\bf 23})\\ &=& 17\times {\bf 23}-10\times {\bf 39}\\ &=& 17\times ({\bf 998}-25\times {\bf 39})-10\times {\bf 39}\\ &=& 17\times {\bf 998}-435\times {\bf 39}\\ &=& 17\times {\bf 998}-435\times ({\bf 19999}-20\times {\bf 998})\\ &=& 8717\times {\bf 998}-435\times {\bf 19999}. \end{eqnarray}
Thus $y=8717$ and $x= 435$. The old telephone number is therefore 4358717. Checking, we have $$8717435 = 1 + 2\times 4358717.$$