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, and therefore can be determined (at least in principle) by testing finitely many numbers.

The greatest common divisor can also be characterized by the following property:

It is a common divisor, and every common divisor divides it evenly.

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 relative 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 gcd

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

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) = ka + lb (with integers k and l). 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 thus (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. Similarly, equations can be simplified. Moreover, the gcd can be used to calculate the least common multiple: lcd(a,b) = ab/gcd(a,b).

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.

Formulas

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

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

If

$a=\prod _{p\ {\rm {prim}}}p^{a(p)}\ {\textrm {and}}\ b=\prod _{p\ {\rm {prim}}}p^{b(p)}$

then

$\mathop {\rm {gcd}} (a,b)=\prod _{p\ {\rm {prim}}}p^{\min(a(p),b(p))}$