Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search