## 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.

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.

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 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 = **2 ^{3}** ×

**3**

60 = 2

^{2}× 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 2^{3} × 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.

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.

*See also: numbers, prime numbers*