Euclid's Algorithm

Euclid's Algorithm

(algorithm)(Or "Euclidean Algorithm") An algorithm forfinding 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, repeatedlyreplace the larger by subtracting the smaller from it untilthe 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 and168 is 12.

This algorithm requires only subtraction and comparisonoperations but can take a number of steps proportional to thedifference between the initial numbers (e.g. gcd(1, 1001) willtake 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.