Euclidean algorithm

The Euclidean algorithm (also called Euclid's algorithm) is an extremely fast algorithm to determine the greatest common divisor (GCD) of two integers.

It was already contained in Euclid's Elements.

The algorithm does not require factoring.

Given two non-negative integers a and b, first check if b is zero. If yes, then the GCD is a. If no, calculate c, the remainder after the division of a by b. Replace a with b, b with c, and start the process again.

For example, the GCD of 1029 and 42 is computed by this algorithm to be 21 with the following steps:

a	b
1029	42
42	21
21	0

For a more involved example, 46406 and 36957 can be seen to be relatively prime by the following computation:

a	b
46406	36957
36957	9449
9449	8610
8610	839
839	220
220	179
179	41
41	15
15	11
11	4
4	3
3	1
1	0

By keeping track of the quotients occurring during the algorithm, one can also determine integers p and q with ap+bq = gcd(a,b). This is known as the extended Euclid's algorithm. Here is a Javascript implementation which should work in most browsers:

// This program works only for non-negative inputs.

// Get data from user and convert strings to integers.

var a = parseInt(prompt("Enter non-negative value for a",0))

var b = parseInt(prompt("Enter non-negative value for b",0))



// Save original values.

a0 = a;

b0 = b;



// Initializations. We maintain the invariant p*a0 + q*b0 = a and r*a0 + s*b0 = b.

p = 1; q = 0;

r = 0; s = 1;



// The algorithm:

while (b != 0) { 

  c = a % b;

  quot = Math.floor(a/b);  //Javascript doesn't have an integer division operator

  a = b;

  b = c;

  new_r = p - quot * r; new_s = q - quot * s;

  p = r; q = s;

  r = new_r; s = new_s;

}



// Show result.

alert("gcd(" + a0 + "," + b0 + ")=" + a + "\n" + p + "*" + a0 + "+(" + q + ")*" + b0 + "=" + a)

When analyzing the runtime of this version of Euclid's algorithm, it turns out that the inputs requiring the most steps are two successive Fibonacci numbers, and the worst case requires O(n) divisions, where n is the number of digits in the input (see Big O).

Euclid originally formulated the problem geometrically, as the problem of finding a common "measure" for two line lengths, and his algorithm proceeded by repeated subtraction of the shorter from the longer segment. This is illustrated with the following implementation in Python:

def gcd(a,b):

    while 1:

        if a == b:

            return a

        elif a > b:

            a = a - b

        else:

            b = b - a