10/21/24, 10:10 PM Euclidean Algorithm -- from Wolfram MathWorld
TOPICS
Number Theory › Number Theoretic Functions › Greatest Common Divisor ›
Number Theory › Integer Relations ›
History and Terminology › Mathematica Code ›
More...
Euclidean Algorithm
Download
Wolfram Notebook
The Euclidean algorithm, also called Euclid's algorithm, is an algorithm for finding the greatest
common divisor of two numbers and . The algorithm can also be defined for more general
rings than just the integers . There are even principal rings which are not Euclidean but
where the equivalent of the Euclidean algorithm can be defined. The algorithm for rational
numbers was given in Book VII of Euclid's Elements. The algorithm for reals appeared in Book
X, making it the earliest example of an integer relation algorithm (Ferguson et al. 1999).
The Euclidean algorithm is an example of a P-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 which divides both and (so that and ),
then also divides since
(1)
Similarly, find a number which divides and (so that and ), then divides
since
(2)
Therefore, every common divisor of and is a common divisor of and , so the procedure
can be iterated as follows:
Find out if you already have access to Wolfram tech through your organization » ×
https://mathworld.wolfram.com/EuclideanAlgorithm.html 1/7
10/21/24, 10:10 PM Euclidean Algorithm -- from Wolfram MathWorld
TOPICS
(3)
For integers, the algorithm terminates when divides exactly, at which point
corresponds to the greatest common divisor of and , . For real numbers,
the algorithm yields either an exact relation or an infinite sequence of approximate relations
(Ferguson et 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 just remainders, 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 are relatively prime.
A concise Wolfram Language implementation can 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 the greatest common divisor for
two numbers less than is
(5)
where is the golden ratio. Numerically, Lamé's expression evaluates to
Find out if you already have access to Wolfram tech through your organization » ×
https://mathworld.wolfram.com/EuclideanAlgorithm.html 2/7
10/21/24, 10:10 PM Euclidean Algorithm -- from Wolfram MathWorld
TOPICS
(6)
which, for , is always times the number of digits in the smaller number (Wells 1986,
p. 59). As shown by Lamé's theorem, the worst case occurs when the algorithm is applied to
two consecutive Fibonacci numbers. Heilbronn showed that the average number of steps is
for all pairs with . Kronecker showed that the
shortest application of the algorithm uses least absolute remainders. The quotients 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 the
recurrence relation
(7)
Tabulating this function for gives
(8)
(OEIS A051010). The maximum numbers of steps for a given , 2, 3, ... are 1, 2, 2, 3, 2, 3, 4,
3, 3, 4, 4, 5, ... (OEIS A034883).
Find out if you already have access to Wolfram tech through your organization » ×
https://mathworld.wolfram.com/EuclideanAlgorithm.html 3/7
10/21/24, 10:10 PM Euclidean Algorithm -- from Wolfram MathWorld
TOPICS
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, ... (OEIS
A051011 and A051012). Norton (1990) showed that
(10)
where is the Mangoldt function and is Porter's constant (Knuth 1998, pp. 355-356).
The related function
(11)
where is the totient function, gives the average number of divisions when is fixed and
Find out if you already have access to Wolfram tech through your organization » ×
is a random number coprime to . Porter (1975) showed that
https://mathworld.wolfram.com/EuclideanAlgorithm.html 4/7
10/21/24, 10:10 PM Euclidean Algorithm -- from Wolfram MathWorld
TOPICS (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 the Riemann zeta function.
There exist 21 quadratic fields in which there is 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 find integer relations
between variables, none were successful until the discovery of the Ferguson-Forcade
algorithm (Ferguson et al. 1999). Several other integer relation algorithms have now been
discovered.
SEE ALSO
Blankinship Algorithm, Euclidean Ring, Ferguson-Forcade Algorithm, Half-GCD, Integer Relation, Quadratic
Field
Explore this topic in the MathWorld classroom
EXPLORE WITH WOLFRAM|ALPHA
euclidean algorithm
More things to try: = euclidean algorithm = 2x^2 - 3xy + 4y^2 + 6x - 3y - 4 = 0 = code 506119 k=4
REFERENCES
Bach, E. and Shallit, J. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. Cambridge, MA: MIT Press,
1996.
Find out if you already have access to Wolfram tech through your organization » ×
https://mathworld.wolfram.com/EuclideanAlgorithm.html 5/7
