Euclid's Algorithm
Euclid's algorithm is a technique used to find the greatest common divisor of two numbers. The greatest common divisor of two numbers is the greatest number that is a divisor or factor, a number that divides another number, of those two numbers. Euclid's algorithm for rational numbers was given in Book VII of Elements, a book written by Euclid, the famous Greek mathematician. The corresponding algorithm for real numbers appeared in Book X of the same publication. It is the earliest example of an integer relation algorithm which are sometimes referred to as Euclidean algorithms or multidimensional continued fraction algorithms.
Euclid's algorithm is an example of a P-problem, a polynomial time problem whose number of steps is bounded by a polynomial. In this particular case the time complexity is bounded by a quadratic function of length equal to the input values. In Euclid's Book VII of Elements he uses the algorithm to find the greatest common divisor of two numbers that are not prime. For this problem, called "Proposition 2" in his book, we let a = bm + r and seek to find a number u which divides both a and b. (a = su and b = tu) The number u also will divide r since:
r = a - bm = su - mtu = (s - mt)u.
Similarly we can find a number v which divides b and r. (b = s'v and r = t'v) In this case the number v will also divide a since:
a = bm + r = s'vm + t'v = (s'm + t')v.
This means that every common divisor of a and b is a common divisor of b and r. The procedure can be iterated to find the greatest common divisor of a and b:
m1 = a/b a = bm1 + r1 m2 = b/r1 b = m2r1 + r2 m3 = r1/r2 r1 = m3r2 + r3 mn = (rn-2)/(rn-1) rn-2 = mnrn-1 + rn mn + 1 = (rn - 1)/(rn) rn - 1 = mn + 1 rn + 0.
When a and b are integers Euclid's algorithm terminates when mn + 1 divides rn - 1 exactly. At this point rn is equal to the greatest common divisor of a and b. When a and b are real numbers, Euclid's algorithm gives either an infinite sequence of approximate relations or an exact relation.
Lame's theorem deals with the number of steps in the iteration of Euclid's algorithm needed to find the greatest common divisor of two numbers. If the two numbers are less than n then the number of steps is:
steps 4.785log10n + 1.6723.
Lame's theorem shows that the worse case, the most number of iterations required, exists when Euclid's algorithm is applied to two consecutive Fibonacci numbers.
Euclid's algorithm was first published in Book VII of Euclid's Elements sometime between 330 BC and 265 BC. This book was a compilation of mathematical knowledge that was known and accepted at that time. It became the central teaching book for mathematics for 2000 years. It is thought that no results in Elements were first proven by Euclid, but he is attributed with the organization of the material and its exposition. More than 1000 editions of Elements have been published since it was first printed in 1482. Over the years various attempts were made to generalize Euclid's algorithm to find integer relations between n 3 variables. A generalized form of the algorithm for these types of systems would make obtaining solutions much easier. These attempts failed until 1999 when Ferguson and coworkers discovered the Ferguson-Forcade algorithm. Since that time several other integer relation algorithms have been found.
This is the complete article, containing 603 words
(approx. 2 pages at 300 words per page).
