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

Prime Factors :

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

Examples :

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 as a product of Prime Factors.

In fact, we can do that for any natural 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 'p^a' divides 'n' exactly.

Examples :

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

2 is the prime factor of 8.

Multiplicity of 2 is 3.

Also, 12 = 2 x 2 x 3 = 2^2 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 statement is called 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 Factorization :

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 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.

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 of Prime Factorization :

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 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.

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 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.

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.

For more about Prime Factorization, go to, http://www.math-help-ace.com/Prime-Factorization.html