Euclidean algorithm

In mathematics, the Euclidean algorithm, or Euclid's algorithm, named after the ancient Greek geometer and number-theorist Euclid, is an algorithm for finding the greatest common divisor (gcd) of two integers. The algorithm runs efficiently even when methods using prime factorizations do not.

Simple but slow version

The algorithm is based on this simple fact: If d is a divisor of both m and n, then d is a divisor of m − n. Thus, for example, any divisor shared in common by both 1989 and 867 must also be a divisor of 1989 − 867 = 1122. This reduces the problem of finding gcd(1989, 867) to the problem of finding gcd(1122, 867). This reduction to smaller integers is iterated as many times as possible. Since one cannot go one getting smaller and smaller positive integers forever, one must reach a point where one of the two is 0. But one can get 0 when subtracting two integers only if the two integers are equal. Therefore, one must reach a point where the two are equal. At that point, the problem of the gcd becomes trivial.

Thus:

gcd(1989, 867) = gcd(1989 − 867, 867) = gcd(1122, 867)

= gcd(1122 − 867, 867) = gcd(255, 867)

= gcd(255, 867 − 255) = gcd(255, 612)

= gcd(255, 612 − 255) = gcd(255, 357)

= gcd(255, 357 − 255) = gcd(255, 102)

= gcd(255 − 102, 102) = gcd(51, 102)

= gcd(51, 102 − 51) = gcd(51, 51) = 51.

Thus the largest integer that is a divisor of both 1989 and 867 is 51. One use of this fact is in reducing the fraction 1989/867 to lowest terms:

${\frac {1989}{867}}={\frac {51\times 39}{51\times 17}}={\frac {39}{17}}.$

Full-fledged and faster version

In the example above, succesive subtraction of 867 from the larger of the two numbers whose gcd was sought led to the remainder on division of the larger number, 1989, by the smaller, 867. Thus the algorithm may be stated:

• Replace the larger of the two numbers by the remainder on division of the larger one by the smaller one.

• Repeat until one of the two numbers is 0. The gcd is the other number.

Example

It is desired to reduce the fraction

${\frac {357765}{110959}}$

to lowest terms. We have

gcd(357765, 110959) = gcd(24888, 110959)

because 24888 is the remainder when 357765 is divided by 110959. Then

gcd(24888, 110959) = gcd(24888, 11407)

because 11407 is the remainder when 110959 is divided by 24888. Then

gcd(24888, 11407) = gcd(2074, 11407)

because 2074 is the remainder when 24888 is divided by 11407. Then

gcd(2074, 11407) = gcd(2074, 1037)

because 1037 is the remainder when 11407 is divided by 2074. Then

gcd(2074, 1037) = gcd(0, 1037)

because 0 is the remainder when 2074 is divided by 1037.

No further reduction is possible, and the gcd is 1037. Thus we have

${\frac {357765}{110959}}={\frac {1037\times 345}{1037\times 107}}={\frac {345}{107}}.$