Namespaces
Variants
Actions

Euclidean algorithm

From Encyclopedia of Mathematics
Revision as of 17:15, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

A method for finding the greatest common divisor of two integers, two polynomials (and, in general, two elements of a Euclidean ring) or the common measure of two intervals. It was described in geometrical form in Euclid's Elements (3rd century B.C.).

For two positive integers , the method is as follows. Division with remainder of by always leads to the result , where the quotient is a positive integer and the remainder is either 0 or a positive integer less than , . Successive divisions are performed:

(*)

where the are positive integers and , until a remainder 0 is obtained. The series of equations (*) finishes thus:

The least positive remainder in this process is the greatest common divisor of and .

The Euclidean algorithms for polynomials or for intervals are similar to the one for integers. In the case of incommensurable intervals the Euclidean algorithm leads to an infinite process.


Comments

The Euclidean algorithm to determine the greatest common divisor of two integers is quite fast. It can be shown that the number of steps required is at most

A slight extension of the algorithm also yields a solution of in .

References

[a1] W.J. Leveque, "Topics in number theory" , 1 , Addison-Wesley (1956) pp. Chapt. 2
How to Cite This Entry:
Euclidean algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Euclidean_algorithm&oldid=33779
This article was adapted from an original article by BSE-3 (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article