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:
 |
(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
 |
(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).
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
![T(n)=(12ln2)/(pi^2)[lnn-sum_(d|n)(Lambda(d))/d]+C+1/nsum_(d|n)phi(d)O(d^(-1/6+epsilon)),](/images/equations/EuclideanAlgorithm/NumberedEquation10.svg) |
(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 
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 ![[1,N]](/images/equations/EuclideanAlgorithm/Inline63.svg)
Norton (1990) proved that
![A(N)=(12ln2)/(pi^2)[lnN-1/2+6/(pi^2)zeta^'(2)]+C-1/2+O(N^(-1/6+epsilon)),](/images/equations/EuclideanAlgorithm/NumberedEquation14.svg) |
(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.
