Algorithm and Bound for the Greatest Common Divisor of n Integers A new version of the Euclidean algorithm for finding the greatest common divisor of n integers a(i) and multipliers x(i) such that gcd = x(1)a(1) + ... + x(n)a(n) is presented. The number of arithmetic operations and the number of storage locations are linear in n. A theorem of Lame that gives a bound for the number of iterations of the Euclidean algorithm for two integers is extended to the case of n integers. An algorithm to construct a minimal set of multipliers is presented. A Fortran program for the algorithm appears as Comm. ACM Algorithm 386. CACM July, 1970 Bradley, G. H. greatest common divisor, Euclidean algorithm, number theory, diophantine equations 3.15 5.10 CA700706 JB February 13, 1978 8:45 AM 2031 4 2031 2031 4 2031 1022 5 2031 2028 5 2031 2031 5 2031 2031 5 2031 2031 5 2031 2521 5 2031 450 5 2031 3099 5 2031 1313 6 2031 2028 6 2031 2031 6 2031 2031 6 2031 2031 6 2031 3135 6 2031