Articles / MBA / Number System / QA

Number System : GCD(Greatest Common Divisor)/HCF and LCM (Least Common Multiple)

by Wonder Boy · Published May 9, 2020 · Updated May 9, 2020

Though you must have read these concepts in school days. Lets just revise it again and practice sufficient questions to calculate GCD /HCF/LCM in few seconds which can be used to solve some tricky but very easy questions asked in various CAT/other MBA exams.

GCD (Greatest Common Divisor) / Highest Common Factor (HCF)
GCD of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder.

For e.g. : The GCD of 12 and 18 is 6.
The GCD of two numbers x,y is denoted by GCD (x,y). So GCD(12,18) = 6.

Also known as:
Greatest Common Factor (GCF)
Highest Common Factor (HCF)
Greatest Common Measure (GCM)
Highest Common Divisor (HCD)

Lets check an example to understand how GCD takes its shape mathematically.
Lets take 2 numbers 150 & 210
The number 150 can be expressed as a product of two integers in various ways:
150 x 1 = 75 x 2 = 50 x 3 = 30 x 5 = 25 x 6 = 15 x 10
Hence the divisors of 150 are 1, 2, 3, 5, 6, 10, 15, 25, 30, 50, 75, 150

The number 210 can be expressed as a product of two integers in various ways:
210 x 1 = 105 x 2 = 70 x 3 = 42 x 5 = 35 x 6 = 30 x 7 = 21 x 10 = 15 x 14
Hence the divisors of 150 are 1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210

Lets check the numbers which are common divisors for both the numbers. They are :
1, 2, 3, 5, 6, 10, 15, 30
The greatest common divisor of these numbers is 30.
So, GCD (150, 210) = 30.

This example only shows us what GCD actually is. But this process of finding GCD seems cumbersome.

Lets learn the easier and effective way of finding GCD/HCF which can be used in exam.

Calculation using prime Factorization
Step 1: Write all the prime factors of the two numbers.
Step 2: Take out the common prime factors and multiply them.
Step 3: You will get the GCD/HCF of the two numbers.

Lets take the same example again. GCD (150,210)
150 = 2 x 3 x 5 x 5
210 = 2 x 3 x 5 x 7
So GCD (150,210) = 2 x 3 x 5 = 30.
Isn’t its easy 🙂

Now we will discuss what is LCM

LCM (Least Common Multiple)
LCM of two integers a and b, usually denoted by LCM(a, b), is the smallest positive integer that is divisible by both a and b.
Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero.

E.g. : the LCM of 12 and 18 is 36.
The LCM of two numbers x,y is denoted by LCM (x,y). So LCM(12,18) = 36.

Also known as:
lowest common multiple
smallest common multiple
lowest common denominator

Lets check an example to understand how LCM takes its shape mathematically.
Lets take 2 numbers 150 & 210 again.
Multiples of 150 are : 150, 300, 450, 600, 750, 900, 1050, 1200, 1350, 1500, 1650, 1800, 1950, 2100, 2250 ….
Multiples of 210 are : 210, 420, 630, 840, 1050, 1260, 1470, 1680, 1890, 2100, 2310, 2520 …

When you will closely watch both the list, you will find that there are few numbers common in both the list.
Lets write these multiples.
Common multiples : 1050 , 2100, 3150, 4200……
So the least common multiple of 150 and 210 is LCM (150,210) = 1050.

This example only shows us what LCM actually is. But this process of finding LCM seems cumbersome.

Lets learn the easier and effective way of finding LCM which can be used in exam.

Calculation using prime Factorization
Step 1: Write all the prime factors of the two numbers.
Step 2: Write each prime factors in terms of power
Step 3: Multiplying the highest power of each prime number together.

Lets take the same example again. LCM (150,210)
150 = 2 x 3 x 5 x 5 = $2^1$ x $3^1$ x $5^2$
210 = 2 x 3 x 5 x 7 = $2^1$ x $3^1$ x $5^1$ x $7^1$
So LCM(150,210) = $2^1$ x $3^1$ x $5^2$ x $7^1$ = 2 x 3 x 25 x 7 = 1050.
isn’t its easy 🙂

How to Improve LCM & GCD calculation speed.
After going through this theory, Solve as much question as possible from Chapter 1 : Number System (Page 19) > How to Prepare for Quantitative Aptitude for the CAT

If you have any difficulty solving problem, Ask question in reply box below.

Use this link to improve LCM and GCD calculation speed http://www.sheppardsoftware.com/mathgames/fractions/LeastCommonMultiple.htm