PRIME FACTORIZATION -
FINDING PRIME FACTORS,
G.C.F. AND L.C.M.
MADE EASY

Your Ad Here















       Please study
       Division before Prime Factorization,
       if you have not already done so.
       It is a prerequisite here.

The following definitions are also prerequisites here.

Factors :

      The natural numbers which exactly divide (with remainder zero)
      a given natural number, n are the factors of that natural number, n.

Example :

8 ÷ 1 gives remaider 0 (the quotient being 8)
8 ÷ 2 gives remaider 0 (the quotient being 4)
8 ÷ 4 gives remaider 0 (the quotient being 2)
8 ÷ 8 gives remaider 0 (the quotient being 8)

∴ 1, 2, 4, 8 are the factors of 8.

Simialrly, Factors of 12 are 1, 2, 3, 4, 6, 12.

Factors of 30 are 1, 2, 3, 5, 6, 10, 15, 30.

Factors of 42 are 1, 2, 3, 6, 7, 14, 21, 42.

Prime Numbers :

      A natural number ( ≠ 1) which does not have any factors
      other than 1 and itself is called a Prime Number.

Examples :
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
are the prime numbers below 50.

Note : (i) 1 is not a prime number (see the definition, number ≠ 1).
(ii) 2 is the only even prime number.
(iii) There are only 4 single digit prime numbers.

To know more about prime numbers, go to Prime Numbers and
List of Prime Numbers.

Prime Factors :

      The factors of a natural number which are prime numbers
      are called the Prime Factors of that natural number.

Examples :
Look at the example given under the definition of Factors.

Factors of 8 are 1, 2, 4, 8. Out of these, only 2 is the Prime Factor.
Also 8 = 2 x 2 x 2;

Factors of 12 are 1, 2, 3, 4, 6, 12.
Out of these, only 2, 3 are the Prime Factors.
Also 12 = 2 x 2 x 3;

Factors of 30 are 1, 2, 3, 5, 6, 10, 15, 30.
Out of these, only 2, 3,5 are the Prime Factors.
Also 30 = 2 x 3 x 5;

Factors of 42 are 1, 2, 3, 6, 7, 14, 21, 42.
Out of these, only 2, 3, 7 are the Prime Factors.
Also 42 = 2 x 3 x 7;

In all these examples here, every number is expressed asa product of Prime Factors. In fact, we can do that for anynatural number ( ≠ 1).

Multiplicity of Prime Factors :

      For a prime factor p of a natural number n,
      the multiplicity of p is the largest exponent a
      for which pa divides n exactly.

Examples :

We have 8 = 2 x 2 x 2 = 23
2 is the prime factor of 8.
Multiplicity of 2 is 3.

Also, 12 = 2 x 2 x 3 = 22 x 3
2 and 3 are the prime factors of 12.
Multiplicity of 2 is 2, and Multiplicity of 3 is 1.

Prime Factorisation :

       Expressing a given natural number as the product of Prime Factors
      is called Prime Factorisation.
      or Prime Factorisation is the process of finding all the prime factors,
      together with their multiplicity for a given natural number.

Prime Factorisation for a Natural Number
is unique except for the order.
This idea is covered in

Fundamental Theorem of Arithmetic.





Method of Prime Factorisation
of a given natural number

STEP 1 :

Divide the given natural number by its smallest prime factor

STEP 2 :

Divide the quotient obtained in step 1,
by its smallest prime factor.

Go on dividing each of the subsequent quotients by their smallest prime factors, till the last quotient is 1.

STEP 3 :

Express the given natural number as the product of all these factors.

This becomes the Prime Factorization of the natural number

The steps and the method of presentation
will be clear by the following examples.













Solved Example 1 of Prime Factorisation :

Find the Prime Factorization of 144.

Solution:


               2 | 144
                 ----------
               2 |  72
                 ----------
               2 |  36
                 ----------             
               2 |  18
                 ----------
               3 |   9
                 ----------
               3 |   3
                 ----------
                     1 



See the method of presentation given above.

144 is divided by 2 to get quotient of 72 which again is
divided by 2 to get quotient of 36 which again is
divided by 2 to get quotient of 18 which again is
divided by 2 to get quotient of 9 which again is
divided by 3 to get quotient of 3 which again is
divided by 3 to get quotient of 1.

See how the prime factors are presented to the left of the vertical line
and the quotients to the right, below the horizontal line.

Now 144 is to be expressed as the product of all the prime factors
which are 2, 2, 2, 2, 3, 3.

∴ Prime Factorization of 144
= 2 x 2 x 2 x 2 x 3 x 3. = 24 x 32 Ans.

Solved Example 2 of Prime Factorisation :

Find the Prime Factorization of 420.

Solution:


               2 | 420
                 ----------
               2 | 210
                 ----------
               3 | 105
                 ----------             
               5 |  35
                 ----------
               7 |   7
                 ----------
                     1
 



See the method of presentation given above.

420 is divided by 2 to get quotient of 210 which again is
divided by 2 to get quotient of 105 which again is
divided by 3 to get quotient of 35 which again is
divided by 5 to get quotient of 7 which again is
divided by 7 to get quotient of 1.

See how the prime factors are presented to the left of the vertical line
and the quotients to the right, below the horizontal line.

Now 420 is to be expressed as the product of all the prime factors
which are 2, 2, 3, 5, 7.

∴ Prime Factorization of 420
= 2 x 2 x 3 x 5 x 7 = 22 x 3 x 5 x 7. Ans.

Some times you may have to apply  Divisibilty Rules
to find out the least prime factor with which
we have to carry out the division.

Let us see an Example.

Solved Example 3 of Prime Factorisation :

Find the Prime Factorization of 17017.

Solution:
The given number = 17017.

Obviously this is not divisible by 2.(last digit is not even.)

Sum of the digits = 1 + 7 + 0 + 1 + 7 = 16 is not divisible by 3
and so the given number is not divisible by 3.

As the last digit is not 0 or 5, it is not divisible by 5.

Let us apply divisibilty rule of 7.

Twice the last digit = 2 x 7 = 14; remaining number = 1701;
difference = 1701 - 14 = 1687.
Twice the last digitof 1687 = 2 x 7 = 14; remaining number = 168;
difference = 168 - 14 = 154.
Twice the last digitof 154 = 2 x 4 = 8; remaining number = 15;
difference = 15 - 8 = 7 is divisible by 7.

∴ the given number is divisible by 7.

Let us divide by 7. 17017 ÷ 7 = 2431.

As divisibilty by 2, 3 is ruled out,
divisibilty by 4, 6, 8, 9 is also ruled out.

Let us apply the divisibility rule by 11.

Sum of alternate digits of 2431 = 2 + 3 = 5.
Sum of remaining digits of 2431 = 4 + 1 = 5.
Difference = 5 - 5 = 0. ⇒ 2431 is divisible by 11.

2431 ÷ 11 = 221.

As divisibilty by 2 is ruled out,
divisibilty by 12 is also ruled out.

Let us apply divisibilty rule of 13.

Four times the last digitof 221 = 4 x 1 = 4; remaining number = 22;
sum = 22 + 4 = 26 is divisible by 13.

∴ the 221 is divisible by 13.

221 ÷ 13 = 17.

Let us present all these divisions below.


                7 | 17017
                 ----------
               11 |  2431
                 ----------
               13 |   221
                 ----------             
               17 |    17
                 ----------
                        1
 



∴ Prime Factorization of 17017
= 7 x 11 x 13 x 17. Ans.

Greatest Common Factor, G.C.F.

      Greatest Common Factor, G.C.F. of two or more numbers is
       the greatest number that divides each one of them exactly.
      or Greatest Common Factor, G.C.F. is the Greatest
      of the common factors of two or more numbers.

G.C.F. is also known as Greatest Common Divisor, G.C.D.

some times it is also called Highest Common Factor, H.C.F.

To find the G.C.F. , an efficient method is
Division method based on Euclidean Algorithm. Here, we will discuss the Method of Prime Factorisation.

Method of Prime Factorisation for finding G.C.F. of two or more numbers

STEP 1 :

Express each one of the given numbers as the product of Prime Factors.
If any Prime Factor is repeated, write it in exponential form.

In other words. find all the prime factors and their multiplicitys
for each of the given numbers.

STEP 2 :

The Product of Terms containing least powers of Common Prime Factors gives the H.C.F. of the given numbers.

The method will be clear by the following examples.

Solved Example 4 of Prime Factorisation :

Find the H.C.F. of 216, 252 using Prime Factorisation.

Solution :


               2 | 216                  2 | 252                           
                 ----------               ----------
               2 | 108                  2 | 126 
                 ----------               ----------
               2 |  54                  3 |  63  
                 ----------               ----------           
               3 |  27                  3 |  21
                 ----------               ----------
               3 |   9                  7 |   7
                 ----------               ----------
               3 |   3                        1
                 ----------
                     1 



Thus Prime Factorization of 216
= 2 x 2 x 2 x 3 x 3 x 3 = 23 x 33;

Prime Factorization of 252
= 2 x 2 x 3 x 3 x 7 = 22 x 32 x 7;

H.C.F. = Product of Terms containing least powers of
Common Prime Factors.
= 22 x 32 = 4 x 9 = 36. Ans.

Solved Example 5 of Prime Factorisation :

Find the H.C.F. of 1197, 5320, 4389 using Prime Factorisation.

Solution :
We have to apply Divisibility Rules
here, to choose the least Prime Factors to divide.

1197 is divisible by 3,
since sum of its digits = 1 + 1 + 9 + 7 = 18 is divisible by 3.

1197 ÷ 3 = 399 which again is divisible by 3,
since 3 + 9 + 9 = 21 is divisible by 3.

399 ÷ 3 = 133.

133 is divisible by 7, since 13 - 2 x 3 = 7 is divisible by 7.

133 ÷ 7 = 19.

All this division is shown in first vertical presentation, below.

Similarly, division of 5320, after applying the apropriate division rules,
is shown in second vertical presentation, below.

and division of 4389, after applying the apropriate division rules,
is shown in third vertical presentation, below.


                3 | 1197                  2 | 5320                  3 | 4389                     
                  ----------                ----------                ----------
                3 |  399                  2 | 2660                  7 | 1463
                  ----------                ----------                ----------
                7 |  133                  2 | 1330                 11 |  209
                  ----------                ----------                ----------
               19 |   19                  5 |  665                 19 |   19
                  ----------                ----------                ----------
                       1                  7 |  133                         1
                                            ----------
                                         19 |   19
                                            ----------
                                                 1
   



Thus, Prime Factorization of 1197
= 3 x 3 x 7 x 19 = 32 x 7 x 19.

Prime Factorization of 5320
= 2 x 2 x 2 x 5 x 7 x 19 = 23 x 5 x 7 x 19.

Prime Factorization of 4389
= 3 x 7 x 11 x 19 = 3 x 7 x 11 x 19.

H.C.F.of the given three numbers 1197, 5320, 4389
= Product of terms containing least powers of Common Prime Factors.
= 7 x 19 = 133. Ans.

The same problem was solved as Solved Example 6 in Division Method based on Euclidean Algorithm Compare the two methods and you can use any method of your choice,
unless specifically asked to solve by one particular method.

Least Common Multiple, L.C.M.

      The Least Common Multiple, L.C.M. of two or more numbers is
      the least natural number which is a multiple of each of the given numbers.
      or L.C.M. is the least of the common multiples of two or more numbers.

To find the L.C.M. , one of the methods adopted is
Common Division method.
Here, we will discuss the Method of Prime Factorisation.
Great deals on School & Homeschool Curriculum Books and Software

Method of Prime Factorisation for finding L.C.M. of two or more numbers

STEP 1 :

Express each one of the given numbers as the product of Prime Factors.
If any Prime Factor is repeated, write it in exponential form.

In other words. find all the prime factors and their multiplicitys
for each of the given numbers.

STEP 2 :

The product of all the different prime facors
each raised to the highest power that appears
in the prime factorisation of any of the given numbers,
gives the L.C.M. of the given numbers.

This method of Prime Factorisation will be clear by the following examples.

Get The Best Grades With the Least Amount of Effort

Here is a collection of proven tips,
tools and techniques to turn you into
a super-achiever - even if you've never
thought of yourself as a "gifted" student.

The secrets will help you absorb, digest
and remember large chunks of information
quickly and easily so you get the best grades
with the least amount of effort.

If you apply what you read from the above
collection, you can achieve best grades without
giving up your fun, such as TV, surfing the net,
playing video games or going out with friends!

Know more about the

Speed Study System.



Solved Example 6 of Prime Factorisation :

Find the L.C.M. of 288, 432, 486 using Prime Factorisation.

Solution :


                2 | 288                  2 | 432                  2 | 486                     
                  ----------               ----------               ----------
                2 | 144                  2 | 216                  3 | 243
                  ----------               ----------               ----------
                2 |  72                  2 | 108                  3 |  81
                  ----------               ----------               ----------
                2 |  36                  2 |  54                  3 |  27
                  ----------               ----------               ----------
                2 |  18                  3 |  27                  3 |   9
                  ----------               ----------               ----------    
                3 |   9                  3 |   9                  3 |   3
                  ----------               ----------               ----------
                3 |   3                  3 |   3                        1
                  ----------               ----------                                    
                      1                          1                                  
                                        



Thus, Prime Factorization of 288
= 2 x 2 x 2 x 2 x 2 x 3 x 3 = 25 x 32.

Prime Factorization of 432
= 2 x 2 x 2 x 2 x 3 x 3 x 3 = 24 x 33.

Prime Factorization of 486
= 2 x 3 x 3 x 3 x 3 x 3. = 2 x 35.

L.C.M..of the given three numbers 288, 432, 486
= The product of all the different prime facors
each raised to the highest power that appears in
the prime factorisation of any of the given numbers
= 25 x 35 = 7776. Ans.

Great Deals on School & Homeschool Curriculum Books

Solved Example 7 of Prime Factorisation :

Find the L.C.M. of 576, 672, 720 using Prime Factorisation.

Solution :


                2 | 576                  2 | 672                  2 | 720                     
                  ----------               ----------               ----------
                2 | 288                  2 | 336                  2 | 360
                  ----------               ----------               ----------
                2 | 144                  2 | 168                  2 | 180
                  ----------               ----------               ----------
                2 |  72                  2 |  84                  2 |  90
                  ----------               ----------               ----------
                2 |  36                  2 |  42                  5 |  45
                  ----------               ----------               ----------    
                2 |  18                  3 |  21                  3 |   9
                  ----------               ----------               ----------
                3 |   9                  7 |   7                  3 |   3
                  ----------               ----------               ----------            
                3 |   3                        1                        1
                  ----------                                               
                      1                                            



Thus, Prime Factorization of 576
= 2 x 2 x 2 x 2 x 2 x 2 x 3 x 3 = 26 x 32.

Prime Factorization of 672
= 2 x 2 x 2 x 2 x 2 x 3 x 7 = 25 x 3 x 7.

Prime Factorization of 720
= 2 x 2 x 2 x 2 x 5 x 3 x 3. = 24 x 5 x 32.

L.C.M..of the given three numbers 576, 672, 720
= The product of all the different prime facors
each raised to the highest power that appears in
the prime factorisation of any of the given numbers
= 26 x 32 x 5 x 7 = 20160. Ans.













Solved Example 8 of Prime Factorisation :

Find the L.C.M. of 1620, 1728, 1890 using Prime Factorisation.

Solution :


                2 | 1620                  2 | 1728                  2 | 1890                     
                  ----------                ----------                ----------
                2 |  810                  2 |  864                  5 |  945
                  ----------                ----------                ----------
                5 |  405                  2 |  432                  3 |  189
                  ----------                ----------                ----------
                3 |   81                  2 |  216                  3 |   63
                  ----------                ----------                ----------
                3 |   27                  2 |  108                  3 |   21
                  ----------                ----------                ----------    
                3 |    9                  2 |   54                  7 |    7
                  ----------                ----------                ----------
                3 |    3                  3 |   27                         1
                  ----------                ----------
                       1                  3 |    9
                                            ----------
                                          3 |    3
                                            ----------
                                                 1



Thus, Prime Factorization of 1620
= 2 x 2 x 5 x 3 x 3 x 3 x 3 = 22 x 5 x 34.

Prime Factorization of 1728
= 2 x 2 x 2 x 2 x 2 x 2 x 3 x 3 x 3 = 26 x 33.

Prime Factorization of 1890
= 2 x 5 x 3 x 3 x 3 x 7. = 2 x 5 x 33 x 7.

L.C.M..of the given three numbers 1620, 1728, 1890
= The product of all the different prime facors
each raised to the highest power that appears in
the prime factorisation of any of the given numbers
= 26 x 34 x 5 x 7 = 181440. Ans.

Exercise 1 of Prime Factorization

(1) Find the Prime Factorization of 105.

(2) Find the Prime Factorization of 462.

(3) Find the Prime Factorization of 4641.

(4) Find the H.C.F. of 5508, 9282 using Prime Factorisation.

(5) Find the H.C.F. of 1701, 2106, 2754 using Prime Factorisation.

(6) Find the L.C.M. of 72, 192, 240 using Prime Factorisation.

(7) Find the L.C.M. of 168, 180, 330 using Prime Factorisation.

(8) Find the L.C.M. of 180, 384, 432 using Prime Factorisation.

For Answers, see at the bottom of the page.

Answers to Exercise 1 of Prime Factorisation :

(1) 3 x 5 x 7 (2) 2 x 3 x 7 x 11 (3) 3 x 7 x 13 x 17

(4) 102 (5) 81 (6) 2880 (7) 27720 (8) 17280

Progressive Learning of Math : Prime Factorization

Recently, I have found a series of math curricula
(Both Hard Copy and Digital Copy) developed by a Lady Teacher
who taught everyone from Pre-K students to doctoral students
and who is a Ph.D. in Mathematics Education.

This series is very different and advantageous
over many of the traditional books available.
These give students tools that other books do not.
Other books just give practice.
These teach students “tricks” and new ways to think.

These build a student’s new knowledge of concepts
from their existing knowledge.
These provide many pages of practice that gradually
increases in difficulty and provide constant review.

These also provide teachers and parents with lessons
on how to work with the child on the concepts.

The series is low to reasonably priced and include

Elementary Math curriculum

and

Algebra Curriculum.