Euclidean algorithm

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.

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 (7th book, Proposition 2). Euclid originally formulated the problem geometrically, as the problem of finding the greatest common "measure" for two line lengths (a line that could be used to measure both lines without a remainder), 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.

Description of the algorithm

Given two natural numbers "a" and "b", not both equal to zero: 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". The remainder after dividing "a" by "b" is usually written as "a" mod "b".

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 numbers will be discussed in more detail later in the article.

Using recursion

Using recursion, the algorithm can be expressed: function gcd(a, b) if b = 0 return a else return gcd(b, a mod b)

or in C/C++ as

int gcd(int a, int b) { return ( b != 0 ? gcd(b, a % b) : a ); }

Using iteration

An efficient, iterative method, for compilers that don't optimize tail recursion:

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

The extended Euclidean algorithm

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.

Original algorithm

The original algorithm as described by Euclid treated the problem geometrically, using repeated subtraction rather than mod (remainder).

function gcd(a, b) if a = 0 return b while b ≠ 0 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:

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 at least one).

ee also

*Least common multiple
*Extended Euclidean algorithm
*Binary GCD algorithm
*Lehmer's GCD algorithm

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.
*Clark Kimberling. "A Visual Euclidean Algorithm," "Mathematics Teacher" 76 (1983) 108-109.

External links

* [http://www.cut-the-knot.org/blue/Euclid.shtml Euclid's Algorithm] at cut-the-knot
* [http://www.cut-the-knot.org/blue/binary.shtml Binary Euclid's Algorithm (Java)] at cut-the-knot
* [http://www.cut-the-knot.org/blue/EuclidAlg.shtml Euclid's Game (Java)] at cut-the-knot
*MathWorld | urlname=EuclideanAlgorithm | title=Euclidean Algorithm
*MathWorld | urlname=LamesTheorem | title=Lamé's Theorem
*PlanetMath | urlname=EuclidsAlgorithm | title=Euclid's algorithm
* [http://plus.maths.org/issue40/features/wardhaugh/index.html Music and Euclid's algorithm]
* [http://www.mathpages.com/home/kmath384.htm The Euclidean Algorithm] at MathPages
* [http://www.math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html Implementation] in Javascript
* [http://www.sharpdeveloper.net/content/articles/dot-net-data-structures-and-algorithms.aspx .NET Implementation of Euclidean algorithm]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Euclidean algorithm — Algebra. a method based on the division algorithm for finding the greatest common divisor of two given integers. [1950 55] * * * ▪ mathematics       procedure for finding the greatest common divisor (GCD) of two numbers, described by the Greek… …   Universalium

  • Euclidean algorithm — noun Date: circa 1955 a method of finding the greatest common divisor of two numbers by dividing the larger by the smaller, the smaller by the remainder, the first remainder by the second remainder, and so on until exact division is obtained… …   New Collegiate Dictionary

  • Euclidean algorithm — noun A method based on the division algorithm for finding the greatest common divisor (gcd) of two given integers …   Wiktionary

  • Euclidean algorithm — Algebra. a method based on the division algorithm for finding the greatest common divisor of two given integers. [1950 55] …   Useful english dictionary

  • Extended Euclidean algorithm — The extended Euclidean algorithm is an extension to the Euclidean algorithm for finding the greatest common divisor (GCD) of integers a and b : it also finds the integers x and y in Bézout s identity: ax + by = gcd(a, b). ,(Typically either x or… …   Wikipedia

  • algorithm — [al′gə rith΄əm] n. [altered (after ARITHMETIC) < ALGORISM] 1. Math. a) any systematic method of solving a certain kind of problem b) the repetitive calculations used in finding the greatest common divisor of two numbers: called in full… …   English World dictionary

  • Euclidean domain — In abstract algebra, a Euclidean domain (also called a Euclidean ring) is a type of ring in which the Euclidean algorithm applies. A Euclidean domain is a specific type of integral domain, and can be characterized by the following (not… …   Wikipedia

  • Euclidean — List of topics named after Euclid (Euclidean or, less commonly, Euclidian) *Euclidean space *Euclidean geometry *Euclid s Elements *Euclidean domain *Euclidean distance *Euclidean ball *Euclidean algorithm *Euclidean distance map *Extended… …   Wikipedia

  • Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

  • Algorithm characterizations — The word algorithm does not have a generally accepted definition. Researchers are actively working in formalizing this term. This article will present some of the characterizations of the notion of algorithm in more detail. This article is a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”