greatest common divisor

(algorithm)

Definition: (1) The greatest integer which is a divisor of given positive integers. For instance, GCD(30, 42) = 6. (2) An algorithm to find the same.

Also known as GCD.

See also binary GCD algorithm, Euclid's algorithm, least common multiple, extended Euclid's algorithm.

Note: After [CLR90, page 804].

Author: PEB

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black  (paul.black@nist.gov).

Entry modified Thu Jan 10 13:37:20 2002.
HTML page formatted Thu Jan 31 13:51:08 2002.

This page's original URL is http://www.nist.gov/dads/HTML/greatcomdiv.html