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` and `b` we can find greatest common divisor.
It is denoted by `GCD(a,b)` (short for the Greatest Common Divisor).
Numbers `a` and `b` are called relatively prime if `GCD(a,b)=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 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 `GCD(21,26)`.
Since `21=3*7` and `26=2*13` then there are no common factors and `GCD(21,26)=1`.
Next example.
Example 2 . Find `GCD(144,54)`.
Since `144=2^4*3^2` and `54=2^1*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, `GCD(144,54)=2^1*3^2=18`.
Next example.
Example 3. Find `GCD(3780,7056)`.
Find prime factorization: `3780=2^2*3^3*5*7` and `7056=2^4*3^2*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*3^2*5^0*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, `GCD(3780,7056)=2^2*3^2*5^0*7^1=4*9*1*7=252`.
Now, take pen and paper and do following exercises.
Exercise 1. Find `GCD(45,375)`.
Answer: 15.
Next exercise.
Exercise 2. Find `GCD(63,3150)`.
Answer: 63.
Last one.
Exercise 3. Find `GCD(13,45)`.
Answer: 1.