You may also like

problem icon

Approximations, Euclid's Algorithm & Continued Fractions

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

problem icon

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.

problem icon

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: Challenge Level:2 Challenge Level:2

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