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

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.

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×1 = 75×2 = 50×3 = 30×5 = 25×6 = 15×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×1 = 105×2 = 70×3 = 42×5 = 35×6 = 30×7 = 21×10 = 15×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

Nice article.

Fully revised.

Nice. Great work.