In number theory, the Euclidean algorithm (also called Euclid's algorithm) is an algorithm to determine the greatest common divisor (GCD) of two elements of any Euclidean domain (for example, the integers). Its major significance is that it does not require factoring the two integers, and it is also significant in that it is one of the oldest algorithms known, dating back to the ancient Greeks. Number theory is the branch of pure mathematics concerned with the properties of numbers in general, and integers in particular, as well as the wider classes of problems that arise from their study. ... In mathematics, computing, linguistics and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ... In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers. ... In abstract algebra, a Euclidean domain (also called a Euclidean ring) is a type of ring in which the Euclidean algorithm can be used. ... In mathematics, factorization or factoring is the decomposition of an object (for example, a number, a polynomial, or a matrix) into a product of other objects, or factors, which when multiplied together give the original. ...

History of the Euclidean algorithm

The Euclidean algorithm is one of the oldest algorithms known, since it appeared in Euclid's Elements around 300 BC. Euclid originally formulated the problem geometrically, as the problem of finding a common "measure" for two line lengths, and his algorithm proceeded by repeated subtraction of the shorter from the longer segment. However, the algorithm was probably not discovered by Euclid and it may have been known up to 200 years earlier. It was almost certainly known by Eudoxus of Cnidus (about 375 BC), and Aristotle (about 330 BC) hinted at it in his Topics, 158b, 29-35. The frontispiece of Sir Henry Billingsleys first English version of Euclids Elements, 1570 Euclids Elements (Greek: ) is a mathematical and geometric treatise, consisting of 13 books, written by the Hellenistic mathematician Euclid in Alexandria circa 300 BC. It comprises a collection of definitions, postulates (axioms), propositions (theorems... Centuries: 4th century BC - 3rd century BC - 2nd century BC Decades: 350s BC 340s BC 330s BC 320s BC 310s BC - 300s BC - 290s BC 280s BC 270s BC 260s BC 250s BC Years: 305 BC 304 BC 303 BC 302 BC 301 BC - 300 BC - 299 BC 298 BC... Euclid, is also referred to as Euclid of Alexandria, (Greek: , about 330 BC– about 275 BC), a Hellenistic mathematician, who lived in the city of Alexandria, Egypt, almost certainly during the reign of Ptolemy I (323 BC–283 BC), is often considered to be the father of geometry. His most... Eudoxus of Cnidus (Greek Εύδοξος) (410 or 408 BC - 355 or 347 BC) was a Greek astronomer, mathematician, physician, scholar and friend of Plato. ... Aristotle (Greek: AristotélÄ“s) (384 BC – March 7, 322 BC) was an ancient Greek philosopher, a student of Plato and teacher of Alexander the Great. ...

Description of the algorithm

Given two natural numbers a and b: check if b is zero; if yes, a is the gcd. If not, repeat the process using (respectively) b, and the remainder after dividing a by b (written a mod b below). The algorithm can be naturally expressed using recursion: In mathematics, a natural number is either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). The former definition is generally used in number theory, while the latter is preferred in set theory and computer science. ... In computing, the modulo operation finds the remainder of division of one number by another. ... A Sierpinski triangle —a confined recursion of triangles to form a geometric lattice. ...

 function gcd(a, b) if b = 0 return a else return gcd(b, a mod b) 

or using iteration (more efficient with compilers that don't optimize tail recursion): The word iteration is sometimes used in everyday English with a meaning virtually identical to repetition. ... In computer science, tail recursion is a special case of recursion that can be easily transformed into an iteration. ...

 function gcd(a, b) while b ≠ 0 t := b b := a mod b a := t return a 

These algorithms can be used in any context where division with remainder is possible. This includes rings of polynomials over a field as well as the ring of Gaussian integers, and in general all Euclidean domains. Applying the algorithm to the more general case other than natural number will be discussed in more detail later in the article. In abstract algebra, a polynomial ring is the set of polynomials in one or more variables with coefficients in a ring. ... In abstract algebra, a field is an algebraic structure in which the operations of addition, subtraction, multiplication and division (except division by zero) may be performed, and the same rules hold which are familiar from the arithmetic of ordinary numbers. ... A Gaussian integer is a complex number whose real and imaginary part are both integers. ... In abstract algebra, a Euclidean domain (also called a Euclidean ring) is a type of ring in which the Euclidean algorithm can be used. ...

By keeping track of the quotients occurring during the algorithm, one can also determine integers p and q with ap + bq = gcd(a, b). This is known as the extended Euclidean algorithm. The extended Euclidean algorithm is an extension to the Euclidean algorithm for finding the greatest common divisor (GCD) of a and b: it also finds the integers x and y in Bezouts identity The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is...

The original algorithm as described by Euclid treated the problem geometrically, using repeated subtraction rather than mod (remainder). This is significantly less efficient:

 function gcd(a, b) while a ≠ b if a > b a := a - b else b := b - a return a 

An example

As an example, consider computing the gcd of 1071 and 1029, which is 21. Recall that “mod” means “the remainder after dividing.”

With the recursive algorithm:

With the iterative algorithm:

Observe that a ≥ b in each call. If initially, b > a, there is no problem; the first iteration effectively swaps the two values.

Proof

Suppose a and b are the natural numbers whose gcd has to be determined. And suppose the remainder of the division of a by b is r. Therefore a = qb + r where q is the quotient of the division.

Any common divisor of a and b is also a divisor of r. To see why this is true, consider that r can be written as r = a − qb. Now, if there is a common divisor d of a and b such that a = sd and b = td, then r = (s−qt)d. Since all these numbers, including s−qt, are whole numbers, it can be seen that r is divisible by d.

The above analysis is true for any divisor d; thus, the greatest common divisor of a and b is also the greatest common divisor of b and r. Therefore it is enough if we continue searching for the greatest common divisor with the numbers b and r. Since r is smaller in absolute value than b, we will reach r = 0 after finitely many steps. In mathematics, the absolute value (or modulus1) of a real number is its numerical value without regard to its sign. ...

Running time

Plot of the running time for gcd(x,y). Red indicates a fast computation, while successively bluer points indicate slower computations

When analyzing the running time of Euclid's algorithm, it turns out that the inputs requiring the most divisions are two successive Fibonacci numbers (because their ratios are the convergents in the slowest continued fraction expansion to converge, that of the golden ratio), and the worst case requires O(n) divisions, where n is the number of digits in the input. However, the divisions themselves are not constant time operations; the actual time complexity of the algorithm is O(n²). The reason is that division of two n-bit numbers takes time O(n(m + 1)), where m is the length of the quotient. Consider the computation of gcd(a,b) where a and b have at most n bits, let be the sequence of numbers produced by the algorithm, and let be their lengths. Then k = O(n), and the running time is bounded by Download high resolution version (880x880, 140 KB)Plot of the number of iterations used by the Euclidean algorithm to compute gcd(x, y) for x and y from 0 to 800. ... Download high resolution version (880x880, 140 KB)Plot of the number of iterations used by the Euclidean algorithm to compute gcd(x, y) for x and y from 0 to 800. ... In mathematics, the Fibonacci numbers form a sequence defined recursively by: That is, after two starting values, each number is the sum of the two preceding numbers. ... A convergent is one of a sequence of rational values obtained by evaluating successive truncations of a continued fraction. ... In mathematics, a continued fraction is an expression such as where a0 is some integer and all the other numbers an are positive integers. ... The golden section is a line segment sectioned into two according to the golden ratio. ... It has been suggested that this article or section be merged into Asymptotic notation. ...

This is considerably better than Euclid's original algorithm, in which the modulus operation is effectively performed using repeated subtraction in O(2ⁿ) steps. Consequently, that version of the algorithm requires O(2ⁿn) time for n-digit numbers, or O(mlogm) time for the number m.

Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity. An alternative algorithm, the binary GCD algorithm, exploits the binary representation used by computers to avoid divisions and thereby increase efficiency, although it too is O(n²); it merely shrinks the constant hidden by the big-O notation on many real machines. The binary GCD algorithm is an algorithm which computes the greatest common divisor of two positive integers. ... The binary numeral system (base 2 numerals) represents numeric values using two symbols, typically 0 and 1. ... The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...

Relation with continued fractions

The quotients that appear when the Euclidean algorithm is applied to the inputs a and b are precisely the numbers occurring in the continued fraction representation of a/b. Take for instance the example of a = 1071 and b = 1029 used above. Here is the calculation with highlighted quotients: In mathematics, a continued fraction is an expression such as where a0 is some integer and all the other numbers an are positive integers. ...

1071 = 1029 × 1 + 42

1029 = 42 × 24 + 21

42 = 21 × 2 + 0

From this, one can read off that

.

This method can even be used for real inputs a and b; if a/b is irrational, then the Euclidean algorithm will not terminate, but the computed sequence of quotients still represents the (now infinite) continued fraction representation of a/b. In mathematics, the real numbers may be described informally in several different ways. ... In mathematics, an irrational number is any real number that is not a rational number, i. ...

Generalization to Euclidean domains

The Euclidean algorithm can be applied to some rings, not just the integers. The most general context in which the algorithm terminates with the greatest common divisor is in a Euclidean domain. For instance, the Gaussian integers and polynomial rings over a field are both Euclidean domains. In mathematics, a ring is an algebraic structure in which addition and multiplication are defined and have properties listed below. ... The integers consist of the positive natural numbers (1, 2, 3, …) the negative natural numbers (−1, −2, −3, ...) and the number zero. ... In abstract algebra, a Euclidean domain (also called a Euclidean ring) is a type of ring in which the Euclidean algorithm can be used. ... A Gaussian integer is a complex number whose real and imaginary part are both integers. ... In abstract algebra, a polynomial ring is the set of polynomials in one or more variables with coefficients in a ring. ... In abstract algebra, a field is an algebraic structure in which the operations of addition, subtraction, multiplication and division (except division by zero) may be performed, and the same rules hold which are familiar from the arithmetic of ordinary numbers. ...

As an example, consider the ring of polynomials with rational coefficients. In this ring, division with remainder is carried out using long division, also known as synthetic division. The resulting polynomials are then made monic by factoring out the leading coefficient. In mathematics, a rational number (commonly called a fraction) is a ratio or quotient of two integers, usually written as the vulgar fraction a/b, where b is not zero. ... In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of lower degree, a generalized version of the familiar arithmetic technique called long division. ... In mathematics, Ruffinis rule allows the rapid division of any polynomial by a binomial of the form x − r. ... In mathematics, polynomial functions, or polynomials, are an important class of simple and smooth functions. ...

We calculate the greatest common divisor of

x⁴ − 4x³ + 4x² − 3x + 14 = (x² − 5x + 7)(x² + x + 2)

and

x⁴ + 8x³ + 12x² + 17x + 6 = (x² + 7x + 3)(x² + x + 2).

Following the algorithm gives these values:

a	b
x4 − 4x3 + 4x2 − 3x + 14	x4 + 8x3 + 12x2 + 17x + 6
	x4 − 4x3 + 4x2 − 3x + 14
x2 + x + 2
0	x2 + x + 2

This agrees with the explicit factorization. For general Euclidean domains, the proof of correctness is by induction on some size function. For the integers, this size function is just the identity. For rings of polynomials over a field, it is the degree of the polynomial (note that each step in the above table reduces the degree by one).

See also

• Least common multiple
• Extended Euclidean algorithm
• Binary GCD algorithm

In arithmetic and number theory the least common multiple or lowest common multiple (lcm) or smallest common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b. ... The extended Euclidean algorithm is an extension to the Euclidean algorithm for finding the greatest common divisor (GCD) of a and b: it also finds the integers x and y in Bezouts identity The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is... The binary GCD algorithm is an algorithm which computes the greatest common divisor of two positive integers. ...

References

• Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Sections 4.5.2–4.5.3, pp.333–379.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.2: Greatest common divisor, pp.856–862.

Donald Knuth at a reception for the Open Content Alliance. ... Cover of books The Art of Computer Programming is a comprehensive monograph written by Donald Knuth which covers many kinds of programming algorithms and their analysis. ... Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...

External links

• Euclid's Algorithm at cut-the-knot
• Binary Euclid's Algorithm (Java) at cut-the-knot
• Euclid's Game (Java) at cut-the-knot
• Weisstein, Eric W., Euclidean Algorithm at MathWorld.
• Euclid's algorithm at PlanetMath.