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

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.

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

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 simplived. Moreover, the gcd can be used to calculate the least common multiple: lcd(a,b) = ab/gcd(a,b).

Tutorial

For example, the divisors of 60 are

1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60,

and the divisors of 72 are

1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72.

The common divisors of 60 and 72 are the numbers that appear in both lists:

1, 2, 3, 4, 6, 12.

The greatest common divisor of 60 and 72 is therefore 12. One writes "gcd(60, 72) = 12", or simply "(60, 72) = 12".

The greatest common divisor is used in reducing fractions to lowest terms, thus:

${\frac {60}{72}}={\frac {12\times 5}{12\times 6}}={\frac {5}{6}}.$

An algorithm involving prime factorizations

One method of finding the greatest common divisor of two integers involves factoring both into prime numbers:

$60=2\times 2\times 3\times 5,\,$

$72=2\times 2\times 2\times 3\times 3.\,$

Observe that the prime number 2 occurs twice in the factorization of 60, and three times in the factorization of 72. One says that the multiplicity of that prime factor is 2 in the first case and 3 in the second. ("Multiplicity" means the number of times the prime factor appears in the factorization.) For each prime factor, one sees which multiplicity is smaller: the one in the factorization of 60 or the one in the factorization of 72:

In the factorization of 60, the multiplicity of the prime factor 2 is 2.

In the factorization of 72, the multiplicity of the prime factor 2 is 3.

The smaller of those multiplicities is 2.

Next:

In the factorization of 60, the multiplicity of the prime factor 3 is 1.

In the factorization of 72, the multiplicity of the prime factor 3 is 2.

The smaller of those multiplicities is 1.

Next:

In the factorization of 60, the multiplicity of the prime factor 5 is 1.

In the factorization of 72, the multiplicity of the prime factor 5 is 0.

The smaller of those multiplicities is 0.

For completeness, note that

all other prime numbers have multiplicity 0 in the factorization of both 60 and 72.

The smaller of those two multiplicities (both 0) is 0.

Therefore

the multiplicity of 2 in the factorization of the gcd is 2;

the multiplicity of 3 in the factorization of the gcd is 1;

the multiplicity of any other prime number in the factorization of the gcd is 0.

The gcd is therefore 2 × 2 × 3 = 12.

Here is another example: the problem is to find gcd(14280, 1638). We have

14280 = 2 × 2 × 2 × 3 × 5 × 7 × 17.

1638 = 2 × 3 × 3 × 7 × 13.

For the prime number 2, the multiplicities are 3 and 1; the smaller of those is 1.

For the prime number 3, the multiplicities are 1 and 2; the smaller of those is 1.

For the prime number 5, the multiplicities are 1 and 0; the smaller of those is 0.

For the prime number 7, the multiplicities are 1 and 1; the smaller of those is 1.

For the prime number 11, the multiplicities are 0 and 0; the smaller of those is 0.

For the prime number 13, the multiplicities are 0 and 1; the smaller of those is 0.

And so on—for all larger prime numbers the multiplicity is 0.

Therefore gcd(14280, 1638) = 2 × 3 × 7 = 42.

An algorithm not involving prime numbers

When the prime factors of a number are large, the algorithm above may be inefficient. Euclid's algorithm does not involve prime factorizations and runs fast in such cases. It may be described as follows:

(1) Replace the larger of the two numbers with the remainder on division of the larger by the smaller.

(2) Repeat step (1) until one of the two numbers is 0.

(3) The one that is not 0 is the gcd.

For an example, let's find the greatest common divisor of the last pair of numbers we used above, (14280, 1638).

14280 / 1638 = 8 remainder 1176. because 1638 times 8 is 13104.

Now we take the new pair of numbers (1638, 1176).

1638 / 1176 = 1 remainder 462

Now we have (1176,462).

1176 / 462 = 2 remainder 252

Now we have (462, 252).

462 / 252 = 1 remainder 210.

Now we have (252,210).

252 / 210 = 1 remainder 42.

Now we have (210,42).

210 / 42 = 5 remainder 0.

Now we have (42,0).

Therefore gcd(14280,1638) = 42.