Euclidean Algorithm, Euclidean Algorithm

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the smaller number is subtracted from the larger number. For example, 21 is the GCD of 252 and 105 (252 = 21  12; 105 = 21  5); since 252  105 = 147, the GCD of 147 and 105 is also 21. Since the larger of the two numbers is reduced, repeating this process gives successively smaller numbers until one of them is zero. When that occurs, the GCD is the remaining nonzero number.

It is used to solve Diophantine equations, such as finding numbers that satisfy multiple congruences (Chinese remainder theorem) or multiplicative inverses of a finite field. The Euclidean algorithm can also be used in constructing continued fractions, in the Sturm chain method for finding real roots of a polynomial, and in several modern integer factorization algorithms. Finally, it is a basic tool for proving theorems in modern number theory, such as Lagrange's four-square theorem and the fundamental theorem of arithmetic (unique factorization).

A key advantage of the Euclidean algorithm is that it can find the GCD efficiently without having to compute the prime factors. Schroeder, p. 19.

For example, the Fibonacci numbers are defined recursively; each term is the sum of the two preceding terms: F n  =  F n 1  +  F n 2 . Several equations associated with the Euclidean algorithm are recursive. Finally, in infinite descent, Rosen, p. 492.

Therefore, either the original solution was impossible, or the construction of smaller solutions must end. The latter argument is used to show that the Euclidean algorithm for natural numbers must end in a finite number of steps.

Source: Wikipedia > Euclidean Algorithm