Greatest Common Divisor and Lowest 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.

Lowest 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 integers using the calculator below.

Enter two or three numbers

Please report any error to [email protected]. Thank you.



How to find greatest common divisor

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.

224 60
 12 30

Continue the steps until we can't find any prime number that can divide all the number on the right side.

224 60
212 30
36  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.

Let's look at another example, find GCD of 40 and 64.


How to find lowest common multiple

Some methods to find lowest 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 lowest 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.

224 60
 12 30

Continue the steps until we have all prime numbers on the left side and at the bottom.

224 60
212 30
36  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.

LCM(a,b) =a × b
GCD(a,b)


Using back the same example above, we can find the LCM of 24 and 60 as follows.

LCM(24,60) =24 × 60 = 120
12

Of course, you can use this formula to find GCD of two integers if you already know the LCM.

By Jimmy Sie

Back to top

See also: numbers, prime numbers