What is the greatest common divisor?

Before discussing greatest common divisors, let us discuss divisors and common divisors.

A divisor is an integer that is divisible by an integer.

For example, the divisor of 4 is 1,2,4, and the divisor of 10 is 1,2,5,10.

A common divisor is an integer that is common to two or more integers.

As an example, let us consider the common divisor of 12 and 18.

The divisors of 12 are 1,2,3,4,6,12.

The divisor of 18 is 1,2,3,6,9,18.

The common divisors 1,2,3,6 are the common divisors.

The greatest common divisor is the largest number among the common divisors.

Since the common divisors of 12 and 18 are 1,2,3,6, 6 is the greatest common divisor.

How to find the greatest common divisor

The greatest common divisor can be found using prime factorization.

As an example here, we will find the greatest common divisor of 18 and 30.

We first prime factorize these numbers.

\begin{align} 18&=2\times3^{2}\notag\\ 30&=2\times3\times5\notag \end{align}

Next, each prime factor of each number is compared and the smaller number is taken out.

For ease of comparison, we express the equation as follows

\begin{align} 18&=2^{1}\times3^{2}\times5^{0}\notag\\ 30&=2^{1}\times3^{1}\times5^{1}\notag \end{align}

18 contains one 2 and one 30, so we take out \( 2^{1} \).

18 contains two 3's and one 30, so we take out \( 3^{1} \).

18 does not contain 5 and 30 contains one, so \( 5^{0} \) is taken out.

Finally, we multiply the extracted numbers together to obtain the greatest common divisor.

\[ 2^{1}\times3^{1}\times5^{0}=6 \]

Example

Example 1

Find the greatest common divisor of 75 and 90.

Solution

The prime factorization of 75 and 90 is as follows

\begin{align} 75&=3\times5^{2}\notag\\ 90&=2\times3^{2}\times5\notag \end{align}

If we take the smaller of each prime factor and take the product, we get the following.

\[ 3\times5=15 \]

Therefore, the greatest common divisor is 15.

Example 2

Find the greatest common divisor of 42 and 231.

Solution

The prime factorization of 42 and 231 is as follows

\begin{align} 42&=2\times3\times7\notag\\ 231&=3\times7\times11\notag \end{align}

If we take the smaller of each prime factor and take the product, we get the following

\[ 3\times7=21 \]

Therefore, the greatest common divisor is 21.