Greatest common divisor

Written by Patrick Stevens, Eric B last updated

Summaries

There are two ways to define the greatest common divisor (also known as greatest common factor, or highest common factor), both equivalent.

The first definition is as the name suggests: the GCD of and is the largest number which divides both and .

The second definition is the more "mathematical", because it generalises to arbitrary rings rather than just ordered rings. The GCD of and is the number such that , , and whenever and , we have . (That is, it is the maximal element of the partially ordered set that consists of the divisors of and , ordered by division.)

Examples

Equivalence of the definitions

Relation to prime factorisations

Calculating the GCD efficiently