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

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