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