Prime Factorization of Natural Numbers – Lucid Explanation of the Method of Finding Prime Factors

Prime Factors (P.F.s) :

The factors of a natural number which are prime numbers are called the P.F.s of that natural number.

Examples :

Factors of 8 are 1, 2, 4, 8.

Out of these, only 2 is the P.F..

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 P.F.s.

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 P.F.s.

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 P.F.s.

Also 42 = 2 x 3 x 7;

In all these examples here, every number is expressed as a product of P.F.s.

In fact, we can do that for any natural number ( ≠ 1).

Multiplicity of P.F.s :

For a P.F. ‘p’ of a natural number ‘n’, the multiplicity of ‘p’ is the largest exponent ‘a’ for which ‘p^a’ divides ‘n’ exactly.

Examples :

We have 8 = 2 x 2 x 2 = 2^3.

 2 is the P.F. of 8.

Multiplicity of 2 is 3.

Also, 12 = 2 x 2 x 3 = 2^2 x 3

2 and 3 are the P.F.s of 12.

Multiplicity of 2 is 2, and Multiplicity of 3 is 1.

Prime Factorization :

Expressing a given natural number as the product of P.F.s is called Prime Factorization.

or Prime Factorization is the process of finding all the P.F.s, together with their multiplicity for a given natural number.

Prime Factorization for a Natural Number is unique except for the order.

This statement is called  Fundamental Theorem of Arithmetic.

Method of Prime Factorization of a given natural number :

STEP 1 :

Divide the given natural number by its smallest P.F.

STEP 2 :

Divide the quotient obtained in step 1, by its smallest P.F..

Go on dividing each of the subsequent quotients by their smallest P.F.s, 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 :

Find the Prime Factorization of 144.

Solution:

2 | 144

———-

2 |  72

———-

2 |  36

———-           

2 |  18

———-

3 |   9

———-

3 |   3

———-

end| 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 P.F.s 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 P.F.s

which are 2, 2, 2, 2, 3, 3.

So, Prime Factorization of 144

= 2 x 2 x 2 x 2 x 3 x 3. = 2^4 x 3^2 Ans.

Solved Example 2  :

Find the Prime Factorization of 420.

Solution:

2 | 420

———-

2 | 210

———-

3 | 105

———-           

5 |  35

———-

7 |   7

———-

end| 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 P.F.s 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 P.F.s

which are 2, 2, 3, 5, 7.

So, Prime Factorization of 420

= 2 x 2 x 3 x 5 x 7 = 2^2 x 3 x 5 x 7. Ans.

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

Let us see an Example.

Solved Example 3 :

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.

So, the given number is divisible by 7.

Let us divide by 7.

17017 ÷ 7 = 2431.

As divisibilty by 2, 3, 5 is ruled out,

divisibilty by 4, 6, 8, 9, 10 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.

So, 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 digit of 221 = 4 x 1 = 4; remaining number = 22;

sum = 22 + 4 = 26 is divisible by 13.

So, the 221 is divisible by 13.

221 ÷ 13 = 17.

Let us present all these divisions below.

7  | 17017

———-

11 |  2431

———-

13 |   221

———-           

17 |    17

———-

end| 1

 

Thus, Prime Factorization of 17017

= 7 x 11 x 13 x 17. Ans.