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.$$

Euclid's algorithm. Number bases. Diophantine equations. Place value. Geometric sequence. Continued fractions. Representing numbers. Interactivities. Making and proving conjectures. Inequality/inequalities.

You may also like

Approximations, Euclid's Algorithm & Continued Fractions

Euclid's Algorithm II

Solving with Euclid's Algorithm

BT.. Eat Your Heart Out

Stage: 5 Challenge Level: