Euclid's Algorithm

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

a = nb + b₁

b = n₁b₁ + b₂

b₁ = n₂b₂ + b₃

(where all the n₁ are positive integers and 0 ≤ b_i ≤ b_i − ₁) 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_kb_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.