# Euclid's Algorithm

## Euclid's Algorithm

(algorithm)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 *a* ≥ *b*, this method consists in the following: Division of *a* by *b* with a remainder always gives *a* = *nb* + *b*_{1}, where *n* is a positive integer and *b*_{1} is either 0 or a positive number less than *b* (0 ≤ *b*_{1} < *b*). Let us perform successive division:

*a* = *nb* + *b*_{1}

*b* = *n*_{1}*b*_{1} + *b*_{2}

*b*_{1} = *n*_{2}*b*_{2} + *b*_{3}

(where all the *n*_{1} are positive integers and 0 ≤ *b*_{i} ≤ *b*_{i} − _{1}) until a remainder equal to zero is obtained. This final remainder *b*_{k + 1} does not have to be written, so that the series of equations given above ends thus:

*b _{k − 2}* =

*n*

_{k − 1}

*b*

_{k − 1}+

*b*

_{k}*b*_{k − 1} = *n*_{k}*b*_{k}

The last positive remainder *b _{k}* 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.