To find g, the greatest common divisor GCD of the two integers a and b using Euclid's algorithm:
g = (a, b) is read g is the greatest common divisor GCD of a and b and it means that a is a multiple of g, b is a multiple of g, and there is no larger number than g that evenly divides both a and b.
Euclid's algorithm is the oldest algorithm in the book (see Euclid's Elements, Book 7, Propositions 1 and 2). It is used to compute g = GCD(a, b).
This is a recursive algorithm that continually calls itself until b is reduced to 0, and then the answer is a.First set a = |a| and b = |b|, then g = GCD(a, b) // using Euclid's algorithm { if (b == 0) g = a; else g = GCD(b, a % b); // % is the remainder function, 0 <= a % b < b }
For example, let a = 54321 and b = 12345.
The first call is GCD(54321, 12345),
the next call is GCD(12345, 54321 % 12345) = GCD(12345, 4941),
the next call is GCD(4941, 12345 % 4941) = GCD(4941, 2463),
the next call is GCD(2463, 4941 % 2463) = GCD(2463, 15),
the next call is GCD(15, 2463 % 15) = GCD(15, 3),
the next call is GCD(3, 15 % 3) = GCD(3, 0).
Now since b is zero, the answer is 3.
GCD(54321, 12345) = 3.
A related function is LCM(a, b) = Least common multiple of a and b.
if a == 0 and b == 0, LCM(0, 0) = 0,
Else LCM(a, b) = |a| * |b| / GCD(a, b).
Return to Number Theory, Algorithms, and Real Functions
Return to Harry's Home Page
times since March 25, 2005.