Euclid's algorithm is a technique used to find the greatest common divisor of two numbers. The greatest common divisor of two numbers is the greatest number that is a divisor or factor, a number that divides another number, of those two numbers. Euclid's algorithm for rational numbers was given in Book VII of Elements, a book written by Euclid, the famous Greek mathematician. The corresponding algorithm for real numbers appeared in Book X of the same publication. It is the earliest example of an integer relation algorithm which are sometimes referred to as Euclidean algorithms or multidimensional continued fraction algorithms.

Euclid's algorithm is an example of a P-problem, a polynomial time problem whose number of steps is bounded by a polynomial. In this particular case the time complexity is bounded by a quadratic function of length equal to the input values. In Euclid's Book VII of...