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 greater than or equal to 1 and less than or equal to the smallest of the numbers, 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).

Examples

For instance,

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

for 72 = 2 • 2 • 2 • 3 • 3, 108 = 2 • 2 • 3 • 3 • 3 there is (72,108) = 2 • 2 • 3 • 3 = 36,

for 6 = 2 • 3, 10 = 2 • 5, 15 = 3 • 5 there is gcd(6,10,15) = 1, (6,10) = 2, (6,15) = 3, (10,15) = 5
and thus 6, 10, and 15 are relatively prime, but not pairwise relatively prime.

The same holds for 4,9,10 — (4,9) = (9,10) = (4,9,10) = 1, but (4,10) = 2 —,

while 1 = (7,9) = (7,10) = (9,10) = (7,9,10) are pairwise relatively prime, and therefore also relatively prime.

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).

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))}$