This site is supported by donations to The OEIS Foundation.

# Euclidean algorithm

The Euclidean algorithm (also called Euclid's algorithm) is an efficient method for computing the greatest common divisor (GCD), also known as the greatest common factor (GCF) or highest common factor (HCF). It is named after the Greek mathematician Euclid, who described it in Books VII and X of his Elements.[1]

## Algorithmic efficiency

### Number of steps

Number of steps in the Euclidean algorithm for
 gcd (x, y)
. Red points indicate relatively few steps (quick), whereas yellow, green and blue points indicate successively more steps (slow). The largest blue area follows the line
 y = ϕ x
, where
 ϕ
represents the Golden ratio.
The number of steps to calculate the GCD of two natural numbers,
 a
and
 b
, may be denoted by
 T (a, b)
.[2] If
 g
is the GCD of
 a
and
 b
, then
 a = m g
and
 b = n g
for two coprime numbers
 m
and
 n
. Then
${\displaystyle {\begin{array}{l}\displaystyle {T(a,b)=T(m,n),\quad a=mg,b=ng,(a,b)=g,(m,n)=1,}\end{array}}}$
as may be seen by dividing all the steps in the Euclidean algorithm by
 g
.[3] By the same argument, the number of steps remains the same if
 a
and
 b
are multiplied by a common factor
 w
${\displaystyle {\begin{array}{l}\displaystyle {T(a,b)=T(wa,wb).}\end{array}}}$
Therefore, the number of steps
 T
may vary dramatically between neighboring pairs of numbers, such as
 T (a, b)
and
 T (a, b + 1)
, depending on the size of the two GCDs.

The recursive nature of the Euclidean algorithm gives another equation

${\displaystyle {\begin{array}{l}\displaystyle {T(a,b)=1+T(b,r_{0})=2+T(r_{0},r_{1})=\ldots =N+T(r_{N-2},r_{N-1})=N+1,}\end{array}}}$
where
 T (x, 0) = 0
by assumption.[2]

### Worst case number of steps

If the Euclidean algorithm requires
 N
steps for a pair of natural numbers
 a   >   b   >   0
, the smallest values of
 a
and
 b
for which this is true are the Fibonacci numbers
 FN  + 2
and
 FN  + 1
, respectively.[4] This can be shown by induction.[5] If
 N = 1
,
 b
divides
 a
with no remainder; the smallest natural numbers for which this is true is
 b = 1
and
 a = 2
, which are
 F2
and
 F3
, respectively. Now assume that the result holds for all values of
 N
up to
 M  −  1
. The first step of the
 M
-step algorithm is
${\displaystyle {\begin{array}{l}\displaystyle {a=q_{0}b+r_{0},}\end{array}}}$

and the second step is

${\displaystyle {\begin{array}{l}\displaystyle {b=q_{1}r_{0}+r_{1}.}\end{array}}}$
Since the algorithm is recursive, it required
 M  −  1
steps to find
 gcd (b, r0)
and their smallest values are
 FM  + 1
and
 FM
. The smallest value of
 a
is therefore when
 q0 = 1
, which gives
 a = b + r0 = FM  + 1 + FM = FM  + 2
. This proof, published by Gabriel Lamé in 1844, represents the beginning of computational complexity theory,[6] and also the first practical application of the Fibonacci numbers.[4] This result suffices to show that the number of steps in Euclid's algorithm can never be more than five times the number of its digits (base 10).[7] For if the algorithm requires
 N
steps, then
 b
is greater than or equal to
 FN + 1
which in turn is greater than or equal to
 ϕ N  − 1
, where
 ϕ
is the golden ratio. Since
 b   ≥   ϕ N  − 1
, then
 N  −  1   ≤   logϕ b
. Since
log10 ϕ   >
 1 5
,
 N  −  1 5
<   log10 ϕ logϕ b = log10 b.
Thus,
 N   ≤   5 log10 b
. Thus, the Euclidean algorithm always needs less than
 O (h)
divisions, where
 h
is the number of digits in the smaller number
 b
.

## Applications

### Factorization algorithms

Calculating a greatest common divisor is an essential step in several integer factorization algorithms,[8] such as Pollard's rho algorithm,[9] Shor's algorithm,[10] Dixon's factorization method[11] and the Lenstra elliptic curve factorization.[12] The Euclidean algorithm may be used to find this GCD efficiently. Continued fraction factorization uses continued fractions, which are determined using Euclid's algorithm.[13]

## Domains

The Euclidean algorithm can be adapted to some other domains. Those domains in which the Euclidean algorithm can be adapted and implemented are then called Euclidean domains.

## Notes

1. Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications.
2. Knuth, p. 344.
3. Ore, p. 45.
4. Knuth, p. 343.
5. Mollin, p. 21.
6. LeVeque, p. 35.
7. Mollin, pp. 21–22.
8. Crandall R., Pomerance C. (2001). Prime Numbers: A Computational Perspective (1st ed.). New York: Springer-Verlag. pp. 225–349. ISBN 0-387-94777-9.
9. Knuth, pp. 369–371.
10. Shor P.W. (1997). “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM J. Sci. Statist. Comput. 26: pp. 1484.
11. Dixon J.D. (1981). “Asymptotically fast factorization of integers”. Math. Comput. 36 (153): pp. 255–260. doi:10.2307/2007743.
12. Lenstra Jr. H.W. (1987). “Factoring integers with elliptic curves”. Annals of Mathematics 126 (3): pp. 649–673. doi:10.2307/1971363.
13. Knuth, pp. 380–384.