 Top

# GCD and LCM

A common divisor of two or more numbers is a number which can be the divisor of each number. Any set of numbers always have 1 as common divisor.
GCD is abbreviated as 'Greatest Common Factor".
The other names for GCD are Greatest Common Divisor(GCD), Highest common factor and Greatest Common denominator.
GCD is defined as the greatest of the positive integers that divide the given number exactly without remainder.The GCD of any set of numbers is the greatest number which divides all the numbers exactly.
A systematic method of finding GCD of any two numbers is better known as Euclidean algorithm, and could be followed by dividing smaller number into the larger until the remainder is zero.

GCD is also known as Greatest Common Factor(GCF) and Highest Common Factor (HCF).

If a remainder does not end at zero then the remainder is divided into the previously used divisor.

Example: Find the GCD of 72 and 84
Solution :
Step 1 : 84 divided by 72 gives a remainder of 12. ( 84 ÷ 72 = remainder 12 )
Step 2 : 72 is divided by the remainder 12 gives a zero remainder with quotient of 6. ( 72 ÷ 12 = 6 with zero remainder )
Step 3 : GCD of 72 and 84 is 12 as the remainder ended with zero.

 Related Calculators Calculate GCD Calculate LCM LCM Calculator for 4 Numbers

## Least Common Multiple

LCM is abbreviated as "least common multiple". The other names of LCM are smallest common multiple and lowest common multiple.
LCM is defined as the smallest of the positive integers that divide the given number exactly without remainder. LCM could be also explained as a common multiple of two or more number is a number that is a multiple of each of the given numbers.
LCM of a set of numbers is the least number into which each of the numbers divides exactly.
LCM of two numbers is equal to their product divided by their GCD.

## How to Calculate LCM?

Listed below are the steps to be followed to calculate LCM.

Step 1: Note the given terms, say a and b.

Step 2: Find the multiples of the term a.

Step 3: Find the multiplies of term b.

Step 4: Now, note the common multiplies of both a and b.

Step 5: Least common multiple is obtained by choosing small values of common values.

Use the below widget to calculate least common multiple(LCM).

## How to Calculate GCD?

Listed below are the steps to be followed to calculate GCD.

Step 1: Note the given terms, say m and n

Step 2: Find the factors of term m.

Step 3: Find the factors of term n.

Step 4: Note the common factors.

Step 5: Highest Common Factor is gcd of given numbers.

Use the below widget to calculate greatest common divisor(GCD).

## Relation Between LCM and GCD

LCM:

LCM refers to Least Common Multiple, i.e. it gives out the least common multiples of any two or more numbers. LCM of any two numbers (say x, y) is denoted as LCM(x, y).

Example:

LCM of 4 and 9 is?

Multiples of 4 are

4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44…

Multiples of 9 are

9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99…

Here, the least common multiple of 4 and 9 is 36.

So LCM of 4 and 9 is 36.

GCD:

GCD refers to Greatest Common Divisor, i.e. it is the largest number which divides the numbers without leaving any remainder. GCD is also known as Greatest Common Factor(GCF) and Highest Common Factor (HCF).

Example:

GCD of 12, 36, and 48 is?

GCD (12, 36, 48)

12, 36, 48 = 12 x 1, 12 x 3, 12 x 4

= 12 (1, 2, 4)

So 12 is the Greatest Common Divisor for numbers 12, 36, 48

Relationship between LCM and GCD is given as:

LCM(a, b) $\times$ GCD(a, b) = a $\times$ b

i.e. Product of LCM and GCD of two numbers is equal to the product of given numbers.

## LCM and GCD Solved Examples

Listed below are some of the examples to find GCD and LCM.

### Solved Examples

Question 1: Calculate the LCM and GCD of 5 and 10.
Solution:

LCM :

The multiplies of 5 are 5, 10, 15, 20, 25, 30, 35, 40,…

The multiplies of 10 are 10, 20, 30, 40, 50, 60, 70,…

Common multiplies are 10, 20

LCM =10

GCD :

Factors of 5 is 5

Factors of 10 are 2, 5

Common factors are 5

GCD = 5

Question 2: Calculate the LCM and GCD of 12 and 10.
Solution:

LCM :

The multiplies of 12 are 12, 24, 36, 48, 60,…

The multiplies of 10 are 10, 20, 30, 40, 50, 60, 70, 80, 90…

Common multiple is 60

LCM = 60

GCD :

Factors of 12 is 2, 4, 3, 6

Factors of 10 are 2, 5

Common factors are 2

GCD = 2

Question 3: Calculate the LCM and GCD of 6 and 18.
Solution:

LCM :

The multiplies of 6 are 6, 12, 18, 24, 30, 36, 42,….

The multiplies of 18 are 18, 36, 54 ..

Common multiplies are 18, 36

LCM = 18

GCD :

Factors of 6 is 1, 2, 3, 6

Factors of 18 are 1,  2, 3, 6, 9, 18

Common factors are 2, 3

GCD = 3

## Finding GCD when LCM is Given

When LCM of any two numbers is given then we can find the GCD as follow:

We know from the relation of LCD and GCD: Product of LCM and GCD of two numbers = Product of two numbers.

Let m and n be two integers, then
GCD (m, n) = $\frac{m \times n}{LCM(m,n)}$

### Solved Example

Question: LCM of numbers 12, 36 is 36, find GCD.
Solution:

Given that, LCM of (12, 36) is 36

GCD (m, n) = $\frac{m \times n}{LCM(m,n)}$

GCD (12, 36) = $\frac{12 \times 36}{36}$ = 12

Therefore, greatest common divisor (GCD) is 12.

## Finding LCM when GCD is Given

When GCD of any two numbers is given we can find the LCM from the below relationship:

For any two numbers x and y

LCM (x, y) = $\frac{x \times y}{GCD(x, y)}$

### Solved Example

Question: GCD of the two numbers (75, 312) is 3, Find its LCM.
Solution:

Given that, GCD(75, 312) = 3
LCM (x, y) = $\frac{x \times y}{GCD(x,y)}$

LCM (2, 3) = $\frac{75 \times 312}{3}$ = 7800

Therefore, least common multiple (LCM) is 7800.