The Euclidean algorithm, also called Euclid's algorithm, is analgorithm for finding thegreatest common divisor of two numbers and. The algorithm can also be defined for more generalrings than just the integers. There are evenprincipal rings which are notEuclidean but where the equivalent of the Euclidean algorithm can be defined. The algorithm for rational numbers was given in Book VII of Euclid'sElements. The algorithm for reals appeared in Book X, making it the earliest example of aninteger relation algorithm (Fergusonet al.1999).

The Euclidean algorithm is an example of aP-problem whose time complexity is bounded by a quadratic function of the length of the input values (Bach and Shallit 1996).

Let, then find a number whichdivides both and (so that and), then alsodivides since

(1)

Similarly, find a number whichdivides and (so that and), thendivides since

(2)

Therefore, every commondivisor of and is a commondivisor of and, so the procedure can be iterated as follows:

(3)

For integers, the algorithm terminates when divides exactly, at which point corresponds to thegreatest common divisor of and,. For real numbers, the algorithm yields either an exact relation or an infinite sequence of approximate relations (Fergusonet al.1999).

An important consequence of the Euclidean algorithm is finding integers and such that

(4)

This can be done by starting with the equation for, substituting for from the previous equation, and working upward through the equations.

Note that the are justremainders, so the algorithm can be easily applied by hand by repeatedly computing remainders of consecutive terms starting with the two numbers of interest (with the larger of the two written first). As an example, consider applying the algorithm to. This gives 42, 30, 12, 6, 0, so. Similarly, applying the algorithm to (144, 55) gives 144, 55, 34, 21, 13, 8, 5, 3, 2, 1, 0, so and 144 and 55 arerelatively prime.

A conciseWolfram Language implementationcan be given as follows.

  Remainder[a_, b_] := Mod[a, b]  Remainder[a_, 0] := 0  EuclideanAlgorithmGCD[a_, b_] := FixedPointList[    {Last[#], Remainder @@ #}&, {a, b}][[-3, 1]]

Lamé showed that the number of steps needed to arrive at thegreatest common divisor for two numbers less than is

(5)

where is thegolden ratio. Numerically, Lamé's expression evaluates to

(6)

which, for, is always times the number of digits in the smaller number (Wells 1986, p. 59). As shown byLamé's theorem, the worst case occurs when thealgorithm is applied to two consecutiveFibonacci numbers. Heilbronn showed that the average number of steps is for all pairs with. Kronecker showed that the shortest application of thealgorithm uses least absolute remainders. Thequotients obtained are distributed as shown in the following table (Wagon 1991).

quotient
1	41.5
2	17.0
3	9.3

Let be the number of divisions required to compute using the Euclidean algorithm, and define if. Then the function is given by therecurrence relation

(7)

Tabulating this function for gives

(8)

(OEISA051010). The maximum numbers of steps for a given, 2, 3, ... are 1, 2, 2, 3, 2, 3, 4, 3, 3, 4, 4, 5, ... (OEISA034883).

Consider the function

(9)

giving the average number of steps when is fixed and chosen at random (Knuth 1998, pp. 344 and 353-357). The first few values of are 0, 1/2, 1, 1, 8/5, 7/6, 13/7, 7/4, ... (OEISA051011 andA051012). Norton (1990) showed that

(10)

where is theMangoldt function and isPorter's constant (Knuth 1998, pp. 355-356).

The related function

(11)

where is thetotient function, gives the average number of divisions when is fixed and is a random number coprime to. Porter (1975) showed that

(12)

(Knuth 1998, pp. 354-355).

Finally, define

(13)

as the average number of divisions when and are both chosen at random in Norton (1990) proved that

(14)

where is the derivative of theRiemann zeta function.

There exist 21quadratic fields in which thereis a Euclidean algorithm (Inkeri 1947, Barnes and Swinnerton-Dyer 1952).

For additional details, see Uspensky and Heaslet (1939) and Knuth (1998).

Although various attempts were made to generalize the algorithm to findinteger relations between variables, none were successful until the discovery of theFerguson-Forcade algorithm (Fergusonet al.1999). Several otherinteger relation algorithms have now been discovered.

See also

Explore with Wolfram|Alpha

More things to try:

• euclidean algorithm
• 5-ary Lyndon words of length 12
• circle, diameter=10

References

Referenced on Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Euclidean Algorithm."FromMathWorld--A Wolfram Resource.https://mathworld.wolfram.com/EuclideanAlgorithm.html

Subject classifications