Greatest Common Divisor and Least Common Multiple
See also: numbers, prime numbers
Greatest Common Divisor (GCD) or Highest Common Factor (HCF) of two positive integers is the largest positive integer that divides both numbers without remainder. It is useful for reducing fractions to be in its lowest terms. See below on methods to find GCD.
Least Common Multiple (LCM) of two integers is the smallest integer that is a multiple of both numbers. See below on methods to find LCM.
You can find the GCD and LCM of two or three integers using the calculator below.
Please report any error to [email protected]
How to find Greatest Common Divisor (GCD)
There are few ways to find greatest common divisor. Below are some of them.
For example, let's try to find the HCM of 24 and 60.
Prime Factorization method
Using this method, first find the prime factorization of each number. Check the prime factors page to learn how to find prime factors of an integer.
24 = 2 × 2 × 2 × 3
60 = 2 × 2 × 3 × 5
Then we find the common prime factors of these two numbers.
24 = 2 × 2 × 2 × 3
60 = 2 × 2 × 3 × 5
The common prime factors are 2, 2 and 3. The greatest common divisor of 24 and 60 is the product of these common prime factors, i.e. 2 × 2 × 3 = 12.
Division by primes
First divide all the numbers by the smallest prime that can divide all of them. The smallest prime that divides 24 or 60 is 2.
| 2 | 24 60 |
| 12 30 |
Continue the steps until we can't find any prime number that can divide all the number on the right side.
| 2 | 24 60 |
| 2 | 12 30 |
| 3 | 6 15 |
| 2 5 |
The GCD is 2 × 2 × 3 = 12.
Euclidean Algorithm
This algorithm finds GCD by performing repeated division starting from the two numbers we want to find the GCD of until we get a remainder of 0.
For our example, 24 and 60, below are the steps to find GCD using Euclid's algorithm.
- Divide the larger number by the small one. In this case we divide 60 by 24 to get a quotient of 2 and remainder of 12.
- Next we divide the smaller number (i.e. 24) by the remainder from the last division (i.e. 12). So 24 divide by 12, we get a quotient of 2 and remainder of 0.
- Since we already get a remainder of zero, the last number that we used to divide is the GCD, i.e 12.
Let's look at another example, find GCD of 40 and 64.
- 64 ÷ 40 = 1 with a remainder of 24
- 40 ÷ 24 = 1 with a remainder of 16
- 24 ÷ 16 = 1 with a remainder of 8
- 16 ÷ 8 = 2 with a remainder of 0.
We stop here since we've already got a remainder of 0. The last number we used to divide is 8 so the GCD of 40 and 64 is 8
How to find Least Common Multiple (LCM)
Some methods to find least common multiple are
For example, let's try to find the LCM of 24 and 60.
Prime Factorization method
Using this method, first find the prime factorization of each number and write it in index form. Check the prime factors page to learn how to find prime factors of an integer.
24 = 23 × 3
60 = 22 × 3 × 5
The least common multiple is the product of the each prime factors with the greatest power. So for the above example, the LCM is 23 × 3 × 5 = 120.
Division by primes
First divide all the numbers by the smallest prime that can divide any of them. The smallest prime that divides 24 or 60 is 2.
| 2 | 24 60 |
| 12 30 |
Continue the steps until we have all prime numbers on the left side and at the bottom.
| 2 | 24 60 |
| 2 | 12 30 |
| 3 | 6 15 |
| 2 5 |
The LCM is 2 × 2 × 3 × 2 × 5 = 120.
Formula
If we know the greatest common divisor (GCD) of integers a and b, we can calculate the LCM using the following formula.
Using back the same example above, we can find the LCM of 24 and 60 as follows.
Of course, you can use this formula to find GCD of two integers if you already know the LCM.
Confused and have questions? We’ve got answers. With Chegg Study, you can get step-by-step solutions to your questions from an expert in the field.
See also: numbers, prime numbers
