Greatest common divisor

The greatest common divisor (often abbreviated to gcd, or g.c.d., sometimes also called highest common factor) of two or more natural numbers is the largest number which divides evenly both (or all) the numbers. Since 1 divides all numbers, and since a divisor of a number cannot be larger than that number, the greatest common divisor of some numbers is a number between 1 and the smallest of the numbers inclusive, and therefore can be determined (at least in principle) by testing finitely many numbers.

Numbers for which the greatest common divisor is 1 are called relatively prime. If (for three or more numbers) any two of them are relatively prime, they are called pairwise relatively prime.

The greatest common divisor of two numbers a and b usually is written as gcd(a,b), or, if no confusion is to be expected, simply as (a,b).

Finding the greatest common divisor

A theoretically important method to determine the greatest common divisor uses prime factorization: Every prime factor of a common divisor must be a prime factor of all the numbers. The greatest common divisor therefore is the product of all common prime factors taken with the highest power common to all the numbers. However, since prime factorization is not efficient, this is at most practical for small numbers (or for numbers whose factorization is already known). This product expression shows that the greatest common divisor can be characterized by the following property: The gcd is a common divisor, and every common divisor divides it evenly.

Fortunately, the Euclidean algorithm provides an efficient means to calculate the greatest common divisor. It also shows that the greatest common divisor can be expressed as an integer linear combination of the numbers (a,b) = ra + sb (with integers r and s). Since every such linear combination is divisible by all divisors common to a and b, this, in turn, shows that it is the smallest positive linear combination, and therefore (in the language of ring theory) the ideal generated by a and b is a principal ideal generated by (a,b).

Examples

For instance,

• (4,9) = 1, (4,6) = 2, and (4,12) = 4, because

the divisors of 4 for are 1,2,4; the divisors of 9 are 1,3,9; and the only common divisor and the gcd 1;

the divisors of 4 for are 1,2,4; the divisors of 6 are 1,2,3,6; the common divisors are 1 and 2, and the gcd is 2;

the divisors of 4 for are 1,2,4; the divisors of 12 are 1,2,3,4,6,12; the common divisors are 1,2,4, and the gcd is 4.

• (72,108) = 36 because

the prime factorizations 72 = 2 • 2 • 2 • 3 • 3 and 108 = 2 • 2 • 3 • 3 • 3 have the common factors 2 • 2 • 3 • 3 = 36.

• 6, 10, and 15 are relatively prime, but not pairwise relatively prime, because

gcd(6,10,15) = 1, but (6,10) = 2, (6,15) = 3, (10,15) = 5, as can be seen either

from the prime factorizations 6 = 2 • 3, 10 = 2 • 5, 15 = 3 • 5 in which no prime occurs in all three products, or

from the lists of divisors: 1,2,3,6 for 6, and 1,2,5,10 for 10, and 1,3,5,15 for 15.

• 7, 9, and 10 are relatively prime, but not pairwise relatively prime, because

gcd(4,9,10) = 1, but (4,10) = 2 even though two pairs are (4,9) = (9,10) = 1 are relatively prime.

• 7, 9, 10 are pairwise relatively prime, and therefore also relatively prime

because (7,9) = (7,10) = (9,10) = (7,9,10) = 1.

See also the Tutorial.

Applications

In elementary arithmetic, the greatest common divisor is used to simplify expressions by reducing the size of numbers involved, e.g., given some fraction p/q, then p/(p,q) / q/(p,q) is its reduced representation. For instance:

The reduced form of 9/12 is 3/4 because (9,12) = 3.

Similarly, equations can be simplified:

The quadratic equation 9x² + 12x = 0 is equivalent to 3x² + 4x = 0.

Moreover, the gcd can be used to calculate the least common multiple: lcm(a,b) = ab/gcd(a,b):

lcm(9,12) = 9•12 / gcd(9,12) = 108/3 = 36

Generalizations

The notion of divisibility can be generalized to the context of rings, the idea of a greatest common divisor, however, is not always applicable.
But in Euclidean rings, i.e., in rings for which there is an analogue to the Euclidean algorithm, a greatest common divisor does exist. An important example is the ring of polynomials: The greatest common divisor of two polynomials is a common factor of greatest degree. In this case the gcd is only unique up to a constant factor.
More generally, a greatest common divisor can be defined for rings with unique prime factorization.

Formulas

Bounds

$1\leq \mathop {\rm {gcd}} (a,b)\leq \min(a,b)$

gcd and lcm

$\mathop {\rm {gcd}} (a,b)\mathop {\rm {lcm}} (a,b)=ab$

prime factor representation

$a=\prod _{p\ {\rm {prime}}}p^{a(p)}\ {\textrm {\ and\ }}\ b=\prod _{p\ {\rm {prime}}}p^{b(p)}\ \Rightarrow \ \mathop {\rm {gcd}} (a,b)=\prod _{p\ {\rm {prime}}}p^{\min(a(p),b(p))}$