Prime factors, HCF, LCM and Euclid Algorithm

Prime Numbers

Numbers that can only be divided by itself and 1 are called prime numbers.

E.g. 2,3,5,7,9,11,13,.........................

1 is not a prime number; 2 is the only number that is both prime and even.

Prime Factors

When the factors of a number is written in the form of prime factors, they are called prime factors.

E.g. 12 - 1,2,3,4,6 and 12 are factors of 12, but they are all not prime factors

However, when 12 is written in terms of 2X2X3, both 2 and 3 are called prime factors.

In order to find prime factors of a number, keep dividing it with prime numbers, starting with the smallest, until you end up with a prime number.

E.g.

240 :-2 = 120 ⇒ 120 :- 2 = 60 ⇒ 60 :- 2 = 30 ⇒ 30 :-2 = 15 ⇒ 15 :- 3 = 5
240 = 2 X 2 X 2 X 2 X 3 X 5
240 = 24 X 3 X 5

Prime factors can be used to find HCF and LCM of two numbers.

HCF

1. Find the prime factors of both numbers first.
2. Then take the common prime factors out.
3. Multiply the lowest power of common prime factors; that gives HCF

E.g.1

Find the HCF of 150 and 120.
150 = 2 X 3 X 5 X 5 = 2 X 3 X 52
120 = 2 X 2 X 2 X 3 X 5 = 23 X 3 X 5
The product of lowest power of common factors = 2 X 3 X 5 = 30
So, HCF of 150 and 120 is 30.

E.g.2

Find the HCF of 75 and 120.
75 = 3 X 5 X 5 = 3 X 52
120 = 2 X 2 X 2 X 3 X 5 = 23 X 3 X 5
The product of lowest power of common factors = 3 X 5 = 15
So, HCF of 75 and 120 is 15.

LCM

1. Find the prime factors of both numbers first.
2. Then take the highest power of prime factors of both numbers.
3. Multiply the above prime factors together; that gives LCM

E.g.1

Find the LCM of 150 and 120.
150 = 2 X 3 X 5 X 5 = 2 X 3 X 52
120 = 2 X 2 X 2 X 3 X 5 = 23 X 3 X 5
The product of highest power of prime factors = 23 X 3 X 52 = 600
So, LCM of 150 and 120 is 600.

E.g.2

Find the LCM of 150 and 60.
150 = 2 X 3 X 5 X 5 = 2 X 3 X 52
60 = 2 X 2 X 3 X 5 = 22 X 3 X 5
The product of highest power of prime factors = 22 X 3 X 52 = 300
So, LCM of 150 and 60 is 300.

Now, in order to complement what you have just learnt, use the following programme.

 and

This programme uses the world-famous Euclid's Algorithm that was invented around 300 B.C., in order to find the HCF of two numbers. So, I take this opportunity to honour the intellectual giant for providing us with this great mathematical tool.

Euclid's Algorithm

Suppose you want to find the HCF of a and b. Here are the steps of the simple algorithm:

1. Input the two numbers - a and b.
2. If a<b exchange a and b.
3. Divide a by b and get the the remainder r.
4. If r is not equal to zero, replace a by b and b by r, then repeat step 3.
5. If r = 0, then b is the HCF of a and b.

Resources at Fingertips

This is a vast collection of tutorials, covering the syllabuses of GCSE, iGCSE, A-level and even at undergraduate level. They are organized according to these specific levels.
The major categories are for core mathematics, statistics, mechanics and trigonometry. Under each category, the tutorials are grouped according to the academic level.
This is also an opportunity to pay tribute to the intellectual giants like Newton, Pythagoras and Leibniz, who came up with lots of concepts in maths that we take for granted today - by using them to serve mankind.

Email:

Stand Out - from the crowd

"There's no such thing as a free lunch."

The best things in nature are free with no strings attached - fresh air, breathtakingly warm sunshine, scene of meadow on the horizon...

Vivax Solutions, while mimicking nature, offers a huge set of tutorials along with interactive tools for free.

Please use them and excel in the sphere of science education.

Everything is free; not even registration is required.

"