Greatest Common Divisor (GCD)

Suppose we are given two numbers 18 and 24.

Let's find their factors.

18: 1,2,3,6,9,18.

24: 1,2,3,4,6,8,12,24.

As can be seen some factors are same for both numbers (they are in bold). These numbers are called common factors (divisors) of 18 and 24.

The greatest of common factors (in bold red) is called the greatest common divisor.

For any integer numbers $$${a}$$$ and $$${b}$$$ we can find greatest common divisor.

It is denoted by $$${G}{C}{D}{\left({a},{b}\right)}$$$ (short for the Greatest Common Divisor).

Numbers $$${a}$$$ and $$${b}$$$ are called relatively prime if $$${G}{C}{D}{\left({a},{b}\right)}={1}$$$.

For example 21 and 26 are relatively prime (although each of them is composite).

Now let's see how to find greatest common divisor.

To find the Greatest Common Divisor of $$${a}$$$ and $$${b}$$$ find prime factorization of $$${a}$$$ and $$${b}$$$ and then take product of common factors taking each of them with smallest exponent.

Example 1. Find $$${G}{C}{D}{\left({21},{26}\right)}$$$.

Since $$${21}={3}\cdot{7}$$$ and $$${26}={2}\cdot{13}$$$ then there are no common factors and $$${G}{C}{D}{\left({21},{26}\right)}={1}$$$.

Next example.

Example 2. Find $$${G}{C}{D}{\left({144},{54}\right)}$$$.

Since $$${144}={{2}}^{{4}}\cdot{{3}}^{{2}}$$$ and $$${54}={{2}}^{{1}}\cdot{{3}}^{{3}}$$$ we see that common factors are $$${2}$$$ and $$${3}$$$.

	144	54	Smaller Factor
Factor 2	$$${{2}}^{{4}}$$$	$$${{2}}^{{1}}$$$	$$${{2}}^{{1}}$$$
Factor 3	$$${{3}}^{{2}}$$$	$$${{3}}^{{3}}$$$	$$${{3}}^{{2}}$$$

Therefore, $$${G}{C}{D}{\left({144},{54}\right)}={{2}}^{{1}}\cdot{{3}}^{{2}}={18}$$$.

Next example.

Example 3. Find $$${G}{C}{D}{\left({3780},{7056}\right)}$$$.

Find prime factorization: $$${3780}={{2}}^{{2}}\cdot{{3}}^{{3}}\cdot{5}\cdot{7}$$$ and $$${7056}={{2}}^{{4}}\cdot{{3}}^{{2}}\cdot{{7}}^{{2}}$$$.

You can see that $$${7056}$$$ doesn't have $$${5}$$$ as factor, while $$${3780}$$$ has.

We can write in prime factorization of $$${7056}$$$ factor $$${{5}}^{{0}}$$$ because $$${{5}}^{{0}}={1}$$$: $$${7056}={{2}}^{{4}}\cdot{{3}}^{{2}}\cdot{{5}}^{{0}}\cdot{{7}}^{{2}}$$$.

	3780	7056	Smaller Factor
Factor 2	$$${{2}}^{{2}}$$$	$$${{2}}^{{4}}$$$	$$${{2}}^{{2}}$$$
Factor 3	$$${{3}}^{{3}}$$$	$$${{3}}^{{2}}$$$	$$${{3}}^{{2}}$$$
Factor 5	$$${{5}}^{{1}}$$$	$$${{5}}^{{0}}$$$	$$${{5}}^{{0}}$$$
Factor 7	$$${{7}}^{{1}}$$$	$$${{7}}^{{2}}$$$	$$${{7}}^{{1}}$$$

So, $$${G}{C}{D}{\left({3780},{7056}\right)}={{2}}^{{2}}\cdot{{3}}^{{2}}\cdot{{5}}^{{0}}\cdot{{7}}^{{1}}={4}\cdot{9}\cdot{1}\cdot{7}={252}$$$.

Now, take pen and paper and do following exercises.

Exercise 1. Find $$${G}{C}{D}{\left({45},{375}\right)}$$$.

Answer: 15.

Next exercise.

Exercise 2. Find $$${G}{C}{D}{\left({63},{3150}\right)}$$$.

Answer: 63.

Last one.

Exercise 3. Find $$${G}{C}{D}{\left({13},{45}\right)}$$$.

Answer: 1.