Greatest common divisor

The greatest common divisor (abbreviated GCD) of two integers which are not both zero is the largest integer that evenly divides both numbers. The GCD of 0 and 0 is usually defined to be 0. The GCD of a and b is often written as gcd(a,b). For example, gcd(12,18) = 6 and gcd(5,0) = 5.

Two numbers are called relatively prime or coprime if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.

Properties

Every common divisor of a and b divides the GCD of a and b.

The greatest common divisor of a and b (not both zero) may be defined alternatively and equivalently as follows: it is the smallest positive integer d which can be written in the form ap+bq where p and q are integers.

If d is the GCD of a and b, and a divides the product bc, then a/d divides c.

If m is nonzero, we have gcd(ma,mb) = m gcd(a,b) and gcd(a+mb,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 of three numbers can be computed as gcd(a,b,c) = gcd(gcd(a,b),c).

The GCD is closely related to the least common multiple: the product of the greatest common divisor and the lowest common multiple of two numbers is equal to the product of the original numbers.

Geometrically, gcd(a,b) is the number of points with integral coordinates on the straight line joining the points (0,0) and (a,b), excluding (0,0).

Calculating the GCD

While the GCD of two numbers can in principle be computed by determining the prime factorizations of the two numbers and comparing factors, this is never done in practice, because it is too slow. A much more efficient method is the Euclidean algorithm. An extended version of this algorithm can also compute integers p and q such that ap + bq = gcd(a, b).

GCD in commutative rings

The greatest common divisor can more generally be defined for elements of an arbitrary commutative ring.

If R is a commutative ring, and a and b are in R, then an element of c of R is called common divisor of a and b if it divides both a and b (that is, there are elements x and y in R such that cx = a and cy = b). If c is a common divisor of a and b, and every common divisor of a and b divides c, then c is called a greatest common divisor of a and b.

Note that the GCD of a and b need not be unique, but if R is an integral domain then any two GCDs of a and b must be associate elements. Also, a and b need not have a GCD at all unless R is a principal ideal domain. If R is a Euclidean domain then a form of the Euclidean algorithm can be used to compute the GCD.