You may also like

If the last four digits of my phone number are placed in front of the remaining three you get one more than twice my number! What is it?

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.

Euclid's Algorithm and Musical Intervals

Stage: 5 Challenge Level:

Euclid's algorithm can be used not only for integers but for any two numbers.

You could use the same method for this problem as given in the article Approximations, Euclid's Algorithm and Continued Fractions for finding rational approximations to $\pi$. In this method you write the process down in terms of continued fractions.

Alternatively, see the article by Benjamin Wardhaugh in the Plus magazine entitled Euclid's Algorithm and Music which shows a method for solving this problem. The examples given there use different numbers. If you use this method it might be easier if you write down your working using the factorizations of the numbers involved, rather than writing them out in full.