A new version of the Euclidean algorithm for finding the greatest common divisor of n integers a,- and multipliers x,- such that gcd = Щ a-\ -j- • • • + x„ an 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.
KEY WORDS AND PHRASES: greatest common divisor, Euclidean algorithm, number theory, diophantine equations CR CATEGORIES: 3.15, 5.10
1. Introduction
The greatest common divisor, gcd, of two positive integers can be determined by the Euclidean algorithm. < Euclid noted that the algorithm could be used to find the i gcd of n positive integers; this follows since gcd(ai, a2, «з) = gcd (gcd (at, a2), a3). If the steps of the algorithm are * traced back, it is possible to determine integers x,- such i that i
с gcd(cti, • ■ ■ , a„) = xxai + • • • + xnan . (1)
The Xi will be called "multipliers." Many applications require the multipliers, for instance, the Chinese problem of remainders [1], calculations on polynomial rings [1], solving linear diophantine equations [2], and computing , the Hermite or Smith normal form of an integer matrix [2].
Blankinship [1] has proposed a new version of the s Euclidean algorithm that eliminates the necessity of г backtracking to determine the multipliers. An (n) X (n) 1 matrix is carried along to keep track of the calculations.
* Administrative Sciences Department. This research was supported in part by funds from the Yale Computer Center. This paper gives the theoretical background of Algorithm 386, Greatest Common Divisor of n Integers and Multipliers, by the ' same author, appearing on pages 447-448 of this issue . i
