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]}

## Contents

## Algorithmic efficiency

### Number of steps

The number of steps to calculate the GCD of two natural numbers,a |

b |

T (a, b) |

^{[2]}If

g |

a |

b |

a = m g |

b = n g |

m |

n |

g |

^{[3]}By the same argument, the number of steps remains the same if

a |

b |

w |

T |

T (a, b) |

T (a, b + 1) |

The recursive nature of the Euclidean algorithm gives another equation

T (x, 0) = 0 |

^{[2]}

### Worst case number of steps

If the Euclidean algorithm requiresN |

a > b > 0 |

a |

b |

FN + 2 |

FN + 1 |

^{[4]}This can be shown by induction.

^{[5]}If

N = 1 |

b |

a |

b = 1 |

a = 2 |

F2 |

F3 |

N |

M − 1 |

M |

and the second step is

M − 1 |

gcd (b, r0) |

FM + 1 |

FM |

a |

q0 = 1 |

a = b + r0 = FM + 1 + FM = FM + 2 |

^{[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 |

b |

FN + 1 |

ϕ N − 1 |

ϕ |

b ≥ ϕ N − 1 |

N − 1 ≤ logϕ b |

log10 ϕ >
ϕ logϕ b = log10 b. |

N ≤ 5 log10 b |

O (h) |

h |

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

- ↑ Thomas L. Heath,
*The Thirteen Books of Euclid's Elements*, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications. - ↑
^{2.0}^{2.1}Knuth, p. 344. - ↑ Ore, p. 45.
- ↑
^{4.0}^{4.1}Knuth, p. 343. - ↑ Mollin, p. 21.
- ↑ LeVeque, p. 35.
- ↑ Mollin, pp. 21–22.
- ↑ Crandall R., Pomerance C. (2001).
*Prime Numbers: A Computational Perspective*(1st ed.). New York: Springer-Verlag. pp. 225–349. ISBN 0-387-94777-9. - ↑ Knuth, pp. 369–371.
- ↑ 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. - ↑ Dixon J.D. (1981). “Asymptotically fast factorization of integers”.
*Math. Comput.***36**(153): pp. 255–260. doi:10.2307/2007743 . - ↑ Lenstra Jr. H.W. (1987). “Factoring integers with elliptic curves”.
*Annals of Mathematics***126**(3): pp. 649–673. doi:10.2307/1971363 . - ↑ Knuth, pp. 380–384.