Euclid's Algorithm

Euclid's Algorithm

(Or "Euclidean Algorithm") An algorithm for finding the greatest common divisor (GCD) of two numbers. It relies on the identity

gcd(a, b) = gcd(a-b, b)

To find the GCD of two numbers by this algorithm, repeatedly replace the larger by subtracting the smaller from it until the two numbers are equal. E.g. 132, 168 -> 132, 36 -> 96, 36 -> 60, 36 -> 24, 36 -> 24, 12 -> 12, 12 so the GCD of 132 and 168 is 12.

This algorithm requires only subtraction and comparison operations but can take a number of steps proportional to the difference between the initial numbers (e.g. gcd(1, 1001) will take 1000 steps).

Euclid’s Algorithm


a method of finding the largest common denominator of two integers and two polynomials or the greatest common measure of two line segments. This theorem is geometrically described in Euclid’s Elements. For the case of the positive numbers a and b, where ab, this method consists in the following: Division of a by b with a remainder always gives a = nb + b1, where n is a positive integer and b1 is either 0 or a positive number less than b (0 ≤ b1 < b). Let us perform successive division:

a = nb + b1

b = n1b1 + b2

b1 = n2b2 + b3

(where all the n1 are positive integers and 0 ≤ bibi1) until a remainder equal to zero is obtained. This final remainder bk + 1 does not have to be written, so that the series of equations given above ends thus:

bk − 2 = nk − 1bk − 1 + bk

bk − 1 = nkbk

The last positive remainder bk in this process is the greatest common denominator of a and b. Euclid’s algorithm serves not only as a means to find the greatest common denominator but also as a proof of its existence. In the case of polynomials or line segments similar methods are used. In the case of incommensurable line segments, Euclid’s algorithm is infinite.

References in periodicals archive ?
Keywords: Lattice Reduction, Gauss' algorithm, LLL algorithm, Euclid's algorithm, probabilistic analysis of algorithms, Dynamical Systems, Dynamical analysis of Algorithms.