Euclidean algorithm


Euclidean algorithm
a method based on the division algorithm for finding the greatest common divisor of two given integers.
[1950-55]

* * *

      procedure for finding the greatest common divisor (GCD) of two numbers, described by the Greek mathematician Euclid in his Elements (c. 300 BC). The method is computationally efficient and, with minor modifications, is still used by computers.

      The algorithm involves successively dividing and calculating remainders; it is best illustrated by example. For instance, to find the GCD of 56 and 12, first divide 56 by 12 and note that the quotient is 4 and the remainder is 8. This can be expressed as 56 = 4 × 12 + 8. Now take the divisor (12), divide it by the remainder (8), and write the result as 12 = 1 × 8 + 4. Continuing in this manner, take the previous divisor (8), divide it by the previous remainder (4), and write the result as 8 = 2 × 4 + 0. Since the remainder is now 0, the process has finished and the last nonzero remainder, in this case 4, is the GCD.

      The Euclidean algorithm is useful for reducing a common fraction to lowest terms. For example, the algorithm will show that the GCD of 765 and 714 is 51, and therefore 765/714 = 15/14. It also has a number of uses in more advanced mathematics. For example, it is the basic tool used to find integer solutions to linear equations ax + by = c, where a, b, and c are integers. The algorithm also provides, as the successive quotients obtained from the division process, the integers ab, …, f needed for the expansion of a fraction p/q as a continued fraction:

a + 1/(b + 1/(c + 1/(d … + 1/f).
 

* * *


Universalium. 2010.

Look at other dictionaries:

  • 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… …   Wikipedia

  • 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”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.