Euclidean Algorithm

Date: 01/25/2003 at 09:25:55
From: Kayla
Subject: Euclidean algorithm

Suppose we have two nonzero positive integers a and b, such that each 
is at most 100 digits long.  I wish to find an "example" of (a,b) 
such that they produce the longest "chain" using the Euclidean 
algorithm process (the greatest number of steps to reach the gcd).

How would I go about finding the solution to this problem?  Is there 
a formula that would help me, or is it simply a trial-and-error 
process?

Date: 01/25/2003 at 11:16:46
From: Doctor Jacques
Subject: Re: Euclidean algorithm

Hi Kayla,

The Euclidean algorithm is a sequence of divisions:

  a_1 = a_2 * q_1 + a_3

  a_2 = a_3 * q_2 + a_4, 

and so on...

If you want the chain to be as long as possible, the numbers (a_i) 
should decrease as slowly as possible.

As a_(i+1) is less than a_i/q_i, we should keep the q_i as small as 
possible, i.e. equal to 1.

Now, assuming all q_i = 1, try to work backward from the end of the 
algorithm (assume the GCD is 1 to keep the numbers as small as 
possible), and see what you get - it is a well-known sequence...

Do not hesitate to write back if you have other questions

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/