1. Home
  2. Math Notes
  3. Pre-Algebra
  4. Factors and Multiples

Greatest Common Divisor (GCD)

Related calculator: Greatest Common Divisor/Factor (GCD) Calculator

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{a} and b{b} we can find greatest common divisor.

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

Numbers a{a} and b{b} are called relatively prime if GCD(a,b)=1{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{a} and b{b} find prime factorization of a{a} and b{b} and then take product of common factors taking each of them with smallest exponent.

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

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

Next example.

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

Since 144=24⋅32{144}={{2}}^{{4}}\cdot{{3}}^{{2}} and 54=21⋅33{54}={{2}}^{{1}}\cdot{{3}}^{{3}} we see that common factors are 2{2} and 3{3}.

144 54 Smaller Factor
Factor 2 24{{2}}^{{4}} 21{{2}}^{{1}} 21{{2}}^{{1}}
Factor 3 32{{3}}^{{2}} 33{{3}}^{{3}} 32{{3}}^{{2}}

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

Next example.

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

Find prime factorization: 3780=22⋅33⋅5⋅7{3780}={{2}}^{{2}}\cdot{{3}}^{{3}}\cdot{5}\cdot{7} and 7056=24⋅32⋅72{7056}={{2}}^{{4}}\cdot{{3}}^{{2}}\cdot{{7}}^{{2}}.

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

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

3780 7056 Smaller Factor
Factor 2 22{{2}}^{{2}} 24{{2}}^{{4}} 22{{2}}^{{2}}
Factor 3 33{{3}}^{{3}} 32{{3}}^{{2}} 32{{3}}^{{2}}
Factor 5 51{{5}}^{{1}} 50{{5}}^{{0}} 50{{5}}^{{0}}
Factor 7 71{{7}}^{{1}} 72{{7}}^{{2}} 71{{7}}^{{1}}

So, GCD(3780,7056)=22⋅32⋅50⋅71=4⋅9⋅1⋅7=252{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 GCD(45,375){G}{C}{D}{\left({45},{375}\right)}.

Answer: 15.

Next exercise.

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

Answer: 63.

Last one.

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

Answer: 1.