The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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 

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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.