## Euclidean Algorithm

An Algorithm for finding the Greatest Common Divisor of two numbers and , also called Euclid's algorithm. It is an example of a P-Problem whose time complexity is bounded by a quadratic function of the length of the input values (Banach and Shallit). Let , then find a number which Divides both and (so that and ), then also Divides since

 (1)

Similarly, find a number which Divides and (so that and ), then Divides since
 (2)

Therefore, every common Divisor of and is a common Divisor of and , so the procedure can be iterated as follows
 (3) (4) (5) (6) (7)

where is . Lamé showed that the number of steps needed to arrive at the Greatest Common Divisor for two numbers less than is
 (8)

where is the Golden Mean, or times the number of digits in the smaller number. Numerically, Lamé's expression evaluates to
 (9)

As shown by Lamé's Theorem, the worst case occurs when the Algorithm is applied to two consecutive Fibonacci Numbers. Heilbronn showed that the average number of steps is for all pairs with . Kronecker showed that the shortest application of the Algorithm uses least absolute remainders. The Quotients obtained are distributed as shown in the following table (Wagon 1991).

 Quotient 1 41.5 2 17.0 3 9.3

For details, see Uspensky and Heaslet (1939) or Knuth (1973). Let be the number of divisions required to compute using the Euclidean algorithm, and define if . Then

 (10)

Define the functions
 (11) (12) (13)

where is the Totient Function, is the average number of divisions when is fixed and chosen at random, is the average number of divisions when is fixed and is a random number coprime to , and is the average number of divisions when and are both chosen at random in . Norton (1990) showed that

 (14)

where is the von Mangoldt Function and is Porter's Constant. Porter (1975) showed that
 (15)

and Norton (1990) proved that

 (16)

There exist 22 Quadratic Fields in which there is a Euclidean algorithm (Inkeri 1947).

References

Bach, E. and Shallit, J. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. Cambridge, MA: MIT Press, 1996.

Courant, R. and Robbins, H. The Euclidean Algorithm.'' §2.4 in Supplement to Ch. 1 in What is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 42-51, 1996.

Dunham, W. Journey Through Genius: The Great Theorems of Mathematics. New York: Wiley, pp. 69-70, 1990.

Finch, S. Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/porter/porter.html

Inkeri, K. Über den Euklidischen Algorithmus in quadratischen Zahlkörpern.'' Ann. Acad. Sci. Fennicae. Ser. A. I. Math.-Phys. 1947, 1-35, 1947.

Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 2nd ed. Reading, MA: Addison-Wesley, 1973.

Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd ed. Reading, MA: Addison-Wesley, 1981.

Norton, G. H. On the Asymptotic Analysis of the Euclidean Algorithm.'' J. Symb. Comput. 10, 53-58, 1990.

Porter, J. W. On a Theorem of Heilbronn.'' Mathematika 22, 20-28, 1975.

Uspensky, J. V. and Heaslet, M. A. Elementary Number Theory. New York: McGraw-Hill, 1939.

Wagon, S. The Ancient and Modern Euclidean Algorithm'' and The Extended Euclidean Algorithm.'' §8.1 and 8.2 in Mathematica in Action. New York: W. H. Freeman, pp. 247-252 and 252-256, 1991.