# Greatest Common Divisor and LCM

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).

```
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
}
```
This is a recursive algorithm that continually calls itself until b is reduced to 0, and then the answer is a.

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.

See: Greatest Common Divisor -- From MathWorld
And: Euclidean Algorithm -- From MathWorld
And: Wolfram Function Definition -- GCD

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).

See: Least Common Multiple -- From MathWorld
And: Wolfram Function Definition -- LCM

This page accessed times since March 25, 2005.
Page created by: hjsmithh@sbcglobal.net
Changes last made on Monday, 06-Aug-07 20:47:20 PDT