The **greatest common divisor** (**gcd**) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 6 and 9 is 3.

The greatest common divisor is also known as the **greatest common factor** (**gcf**), **highest common factor** (**hcf**), **greatest common measure** (**gcm**), or **highest common divisor**.

### Using prime factorizations

Greatest common divisors can in principle be computed by determining the prime factorization of the two numbers and comparing factors, as in the following example: to compute gcd(81, 60), we find the prime factorizations 81 = 3^{4} and 60 = 2^{2} · 3 · 5 and notice that the “overlap” of the two expressions is 3; so gcd(81, 60) = 3. In practice, this method is only feasible for small numbers; computing prime factorizations in general takes far too long.

Here is another concrete example, illustrated by a Venn diagram. Suppose it is desired to find the greatest common divisor of 81 and 60. First, find the prime factorizations of the two numbers:

- 81 = 3 x 3 x 3 x 3
- 60 = 2 x 2 x 3 x 5.

What they share in common is a “3”:

- Least common multiple = 2 x 2 x 5 x ( 3 ) x 3 x 3 x 3 = 4860
- Greatest common divisor = 3.

Example 1: Find the greatest common divisor of 1000 and 810

**Solution:**

1000 = 5 x 5 x 5 x 2 x 2 x 2 = 5^{3 }x 2^{3}

810 = 5 x 2 x 3 x 3 x 3 x 3 = 5 x 2 x 3^{4}

the “overlap” of the two expressions is 5 x 2 = 10

So, greatest common divisor = 10.

## One thought on “Greatest Common Divisor”

Comments are closed.