The Euclidean algorithm (also called Euclid's algorithm) is an algorithm to determine the greatest common divisor (gcd) of two integers. It is one of the oldest algorithms known, since it appeared in Euclid's Elements around 300 BCE. However, the algorithm probably was 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 BCE); and Aristotle (about 330 BCE) hinted at it in his Topics, 158b, 29-35. The algorithm does not require factoring the two integers. Flowcharts are often used to represent algorithms. ... In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf) of two integers which are not both zero is the largest integer that divides both numbers. ... The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ... Euclids Elements (Greek Στοιχεία) is a mathematical and geometric treatise, consisting of 13 books, written by the Greek mathematician Euclid around 300 BC. It comprises a collection of definitions, postulates (axioms), propositions (theorems) and proofs thereof. ... 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... Eudoxus of Cnidus (Greek Εύδοξος) (410 or 408 BC - 355 or 347 BC) was a Greek astronomer, mathematician, physician, scholar and friend of Plato. ... Aristotle (sculpture) Aristotle (Greek: Αριστοτέλης AristotelÄ“s) (384 BC – March 7, 322 BC) was an ancient Greek philosopher. ... This article is about the mathematical concept. ...

Algorithm and implementation

Given two natural numbers a and b, check if b is zero. If yes, a is the gcd. If not, repeat the process using b and the remainder after integer division of a and b (written a modulus b below). The algorithm can be naturally expressed using tail recursion: In computer science, tail recursion is a special case of recursion that can be transformed into an iteration. ...

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

This can be rewritten iteratively as:

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

For example, the gcd of 1071 and 1029 is computed by this algorithm to be 21 with the following steps:

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 algorithm used to calculate the greatest common divisor (gcd, or also highest common factor, HCF) of two integers a and b, as well as integers x and y such that (This equation is known as Bezouts identity. ...

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. 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. ...

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. This is equivalent to the following implementation, which is considerably less efficient than the method explained above:

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

Proof of correctness

Suppose a and b are the numbers whose gcd has to be determined. And suppose the remainder of the division of a by b is t. Therefore a = qb + t where q is the quotient of the division. Now any common divisor of a and b also divides t (since t can be written as t = a − qb); similarly, any common divisor of b and t will also divide a. Thus the greatest common divisor of a and b is the same as the greatest common divisor of b and t. Therefore it is enough if we continue the process with the numbers b and t. Since t is smaller in absolute value than b, we will reach t = 0 after finitely many steps. The graph of the absolute value function In mathematics, the absolute value (or modulus) of a real number is its numerical value without regard to its sign. ...

Running time

Plot of the running time for gcd(x,y)

When analyzing the running time of Euclid's algorithm, it turns out that the inputs requiring the most divisions are two successive Fibonacci numbers, and the worst case requires O(n) divisions, where n is the number of digits in the input (see Big O notation). However, it must be noted that the divisions themselves are not atomic operations (if the numbers are larger than the natural size of the computer's arithmetic operations), since the size of the operands could be as large as n digits. The actual running time is therefore O(n²). 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: In words: you start with 0 and 1, and then produce the next Fibonacci number by adding the two previous Fibonacci numbers. ... The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...

This is, nevertheless, considerably better than Euclid's original algorithm, in which the modulus operation is effectively performed using repeated subtraction in O(2ⁿ) steps. Consequently, this version of the algorithm requires O(n2ⁿ) time for n-digit numbers, or O(mlog m) 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 published by J. Stein in 1967 which computes the greatest common divisor of two positive integers. ... The binary or base-two numeral system is a system for representing numbers in which a radix of two is used; that is, each digit in a binary numeral may have either of two different values. ...

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 are intuitively defined as numbers that are in one-to-one correspondence with the points on an infinite line—the number line. ... In mathematics, an irrational number is any real number that is not a rational number, i. ...

Reference

Knuth, Donald, The Art of Computer Programming, volume 1 and volume 2. Addison-Wesley.

See also

• Least common multiple
• Extended Euclidean 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 algorithm used to calculate the greatest common divisor (gcd, or also highest common factor, HCF) of two integers a and b, as well as integers x and y such that (This equation is known as Bezouts identity. ...

External links

• Euclid's Algorithm: Algorithm, generalization, game and related topics
• Binary Euclid's Algorithm (Java)
• Euclid's Game (Java)