Home > Greatest common divisor

In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (GCF) or highest common factor (hcf) of two integers which are not both zero is the largest integer that divides both numbers.

The greatest common divisor of a and b is written as gcd(a, b), or sometimes simply as (a, b). For example, gcd(12, 18) = 6, gcd(−4, 14) = 2 and gcd(5, 0) = 5. Two numbers are called coprime or relatively prime if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.

The greatest common divisor is useful for reducing fractions to be in lowest terms. Consider for instance

where we cancelled 14, the greatest common divisor of 42 and 56.

1 Calculating the gcd

Greatest common divisors can in principle be computed by determining the prime factorizations of the two numbers and comparing factors, as in the following example: to compute gcd(18,84), we find the prime factorizations 18 = 2·3² and 84 = 2²·3·7 and notice that the "overlap" of the two expressions is 2·3; so gcd(18,84) = 6. In practice, this method is only feasible for very small numbers; computing prime factorizations in general takes far too long.

A much more efficient method is the Euclidean algorithm: divide 84 by 18 to get a quotient of 4 and a remainder of 12. Then divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a remainder of 0, which means that 6 is the gcd.

2 Properties

Every common divisor of a and b is a divisor of gcd(a, b).

gcd(a, b), where a and b are not both zero, may be defined alternatively and equivalently as the smallest positive integer d which can be written in the form d = a·p + b·q where p and q are integers. Numbers p and q like this can be computed with the extended Euclidean algorithm.

If a divides the product b·c, and gcd(a, b) = d, then a/d divides c.

If m is any integer, then gcd(m·a, m·b) = m·gcd(a, b) and gcd(a + m·b, b) = gcd(a, b). If m is a nonzero common divisor of a and b, then gcd(a/m, b/m) = gcd(a, b)/m.

The gcd is a multiplicative function in the following sense: if a₁ and a₂ are relatively prime, then gcd(a₁·a₂, b) = gcd(a₁, b)·gcd(a₂, b).

The gcd of three numbers can be computed as gcd(a, b, c) = gcd(gcd(a, b), c) = gcd(a, gcd(b, c)). Thus the gcd is an associative operation.

gcd(a, b) is closely related to the least common multiple lcm(a, b): we have

gcd(a, b)·lcm(a, b) = a·b.

This formula is often used to compute least common multiples: one first computes the gcd with Euclid's algorithm and then divides the product of the given numbers by their gcd. The following versions of distributivity hold true:

gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))

lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c)).

It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a complete distributiveIn mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and in latticeSee lattice for other mathematical as well as non-mathematical meanings of the term. In mathematics, a lattice is a partially ordered set in which all nonempty finite subsets have both a supremum join and an infimum meet . On the other hand, lattices can with gcd as meet and lcm as join operation. This extension of the definition is also compatible with the generalization for commutative rings given below.

In a Cartesian coordinate systemCartesian means relating to the French mathematician and philosopher Descartes, who, among other things, worked to merge algebra and Euclidean geometry. This work was influential to the development of analytic geometry, calculus, and cartography. The idea, gcd(a, b) can be interpreted as the number of points with integral coordinates on the straight line joining the points (0, 0) and (a, b), excluding (0, 0).