Euclidean AlgorithmDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/