Algorithm and bound for the greatest common divisor of n integers

ABSTRACT

A new version of the Euclidean algorithm for finding the greatest common divisor of n integers ai and multipliers xi such that gcd = x1 a1 + ··· + xn an is presented. The number of arithmetic operations and the number of storage locations are linear in n. A theorem of Lamé 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.

REFERENCES

• 1: BLANKINSHIP, W. A. A new version of the Euclidean algorithm. Amer. Math. Mon. 70 (1963), 742-745.
• 2: BRADLEY, G. H. Algorithms for Hermite and Smith normal matrices and linear diophantine equations. Administrative Sciences Dep., Yale U., New Haven, Conn. (in preparation).
• 3: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 4: LAME, G. Note sur la limite du nombre des divisions dans la recherche du plus grand comrnun diviseur entre deux hombres entiers. C. R. Acad. Sci. Paris, 19 (1844), 867-870.
• 5: LEVIT, R. J. A minimum solution of a diophantine equation. Amer. Math. Mon. 63 (1956), 647-651.
• 6: J. E. L. Peck, Algorithm 139: Solutions of the diophantine equation, Communications of the ACM, v.5 n.11, p.556, Nov. 1962 [doi>10.1145/368996.369014]
• 7: J. E. L. Peck, Algorithm 237: Greatest common divisor, Communications of the ACM, v.7 n.8, p.481, Aug. 1964 [doi>10.1145/355586.364802]
• 8: USFENSKY, J. V., AND HEASLET, M. A. Elementary Number Theory. McGraw-Hill, New York, 1939.

INDEX TERMS

Keywords:
Euclidean algorithm, diophantine equations, greatest common divisor, number theory