Euclid's GCD (and LCM) algorithm

The greatest common divisor (GCD) of two integers, not both zero, is the largest integer that divides both of them. It is convenient to set GCD(0,0)=0. Basic identities concerning the GCD:


Hence we can assume that A and B are nonnegative integers.

Euclid's algorithm is described in the Elements of Euclid (circa 300 B. C. E.). It is based on the following recursion theorem:


Unit: recursive internal function, external function without procedure statement
Parameters: nonnegative integer A, nonnegative integer B
Returns: GCD(A, B)

GCD: procedure
parse arg A, B
if B = 0 then return A
  else return GCD(B, A // B)


That program use "tail recursion". It can always be transformed to iteration by replacing function calls by assignment and do while loop statements. See Technique: Recursion Elimination.


GCD: procedure
parse arg A, B
do while B > 0
  parse value(B A//B) with A B
return A


The worst case of Euclid's algorithm occurs when A and B are consecutive Fibonacci numbers. The number of // operations will never exceed



There is a related idea - the least common multiple LCM of two integer A and B. It is defined to be the smallest positive integer which is a multiple of both A and B.

Equation A*B=GCD(A,B)*LCM(A,B) reduces the calculation of LCM to the calculation of GCD.


LCM: procedure
parse arg A, B
return A * B / GCD(A, B)



Knuth D. E., Seminumerical Algorithms, vol. 2 of The Art of Computer Programming
Addison-Wesley, 1973
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms
The MIT Press, Cambridge, 1990

cover contents index main page

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic.