# Greatest common divisor

995pages on
this wiki
row 1, cell 1 row 1, cell 2 row 1, cell 3
row 2, cell 1 row 2, cell 2 row 2, cell 3

|-valign="middle" |width="1px" style="padding-right: 1em"| |This page should be merged with L.C.M. and H.C.F.|} The greatest common divisor (abbreviated GCD, also known as greatest common factor or GCF, or the highest common factor, HCF) is the largest number which may be divided into two given numbers (or a set of numbers) without remainder, also known as a divisor. The opposite of the greatest common divisor is the least common multiple.

## Calculating the greatest common divisor

There are three fundamental ways of finding the greatest common divisor: listing divisors of each of the numbers, prime factorization and the Euclidian Algorithm.

### Divisor listing

The most elementary, and rigorous way to find the greatest common divisor of a set of numbers is to list the divisors of each number and find the largest number that appears in every list. For example, when finding the greatest common divisor of 18 and 30, one would list 1, 2, 3, 6, 9, 18 as the divisors of 18, and 1, 2, 3, 5, 6, 10, 15, 30 as the divisors of 30. The largest number that appears in both lists is 6. Therefore, the greatest common divisor of 18 and 30 is 6.

### Prime factorization

Another way of finding the greatest common divisor of two or more numbers is through prime factorization. In this method, each number is factored so that it is the product of prime numbers. For example, the prime factorization of 1,176 gives us $1,176 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 7 \cdot 7 = 2^3 \cdot 3 \cdot 7^2$. The prime factorization of 2,100 is $2^2 \cdot 3 \cdot 5^2 \cdot 7$. To find the greatest common Divisor of 1,176 and 2,100, the smallest powers of each prime divisor for each of the numbers (with $p^0$ being assumed if one number doesn't contain a particular prime factor $p$) are multiplied together, as in $2^2 \cdot 3^1 \cdot 5^0 \cdot 7^1 = 84$. Therefore, 84 is the greatest common factor of 1,176 and 2,100.

### Euclidean Algorithm

For large numbers with many divisors, especially large prime divisors, these methods are somewhat inefficient. A systematic way of finding the greatest common divisor is the Euclidean Algorithm. This algorithm has the advantage of being easily written for a computer program. In the Euclidean Algorithm, the division algorithm is applied to two numbers until a remainder of zero is found. How this works is that the greatest common divisor of any two non-zero numbers is also the greatest common divisor between any one of those numbers and the remainder. Thus, the numbers may be recursively divided by the remainder until the remainder is zero, at which point the greatest common divisor has been found. For example:

• $1,975,231 = 1 \cdot 1,936,877 + 38,354$ (numbers are written $\mbox{dividend} = \mbox{quotient} \cdot \mbox{divisor} + \mbox{remainder}$)
• $1,936,877 = 50 \cdot 38,354 + 19,177$
• $38,354 = 2 \cdot 19,177 + 0$

Therefore, the greatest common divisor of 1,975,231 and 1,936,877 is 19,177.

A recursive function for the Euclidian Algorithm would appear something like this:

gcd := func(a,b);
if a mod b = 0 then return b;
else return gcd(b, a mod b);
end;
end;

In Python, a gcd function may look like:

def gcd(a, b):
while b != 0:
a, b = b, a%b
return abs(a)

## Relationship to least common multiple

The product of the greatest common divisor and least common multiple of two numbers is equal to the product of the two numbers. Thus, one of the easiest (and most systematic) ways to find the least common multiple is to compute the greatest common divisor and then divide the product of the numbers by that value. This relationship is evident when using the prime factorization method of calculating the greatest common factor and least common multiple (using prime factorization, the divisors with the greatest powers are multiplied together), as all prime divisors are either used in the GCF or the LCM.