Business

Prime factorization of natural numbers: lucid explanation of the method to find prime factors

Prime factors (FP):

The factors of a natural number that are prime numbers are called FP of that natural number.

Examples:

The factors of 8 are 1, 2, 4, 8.

Of these, only 2 is the PF.

Also 8 = 2 x 2 x 2;

The factors of 12 are 1, 2, 3, 4, 6, 12.

Of these, only 2, 3 are the FP

Also 12 = 2 x 2 x 3;

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

Of these, only 2, 3.5 are the FP

Also 30 = 2 x 3 x 5;

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

Of these, only 2, 3, 7 are the FP

Also 42 = 2 x 3 x 7;

In all of these examples here, each number is expressed as a product of FP

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

FP Multiplicity:

For a FP ‘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 FP of 8.

The multiplicity of 2 is 3.

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

2 and 3 are the FP of 12.

The multiplicity of 2 is 2 and the multiplicity of 3 is 1.

Prime factorization:

Expressing a given natural number as the product of FP is called prime factorization.

or prime factorization is the process of finding all FPs, along with their multiplicity for a given natural number.

The prime factorization for a natural number is unique, except for the order.

This statement is called the Fundamental Theorem of Arithmetic.

Prime factorization method of a given natural number:

STEP 1:

Divide the given natural number by its smallest FP

STEP 2:

Divide the quotient obtained in step 1 by your smallest FP.

Continue dividing each of the subsequent quotients by its smallest FPs, until 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 presentation method will become clear with the following examples.

Worked 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 presentation method given above.

144 is divided by 2 to get the quotient of 72, which is again

divided by 2 to get the quotient of 36, which is again

divided by 2 to get the quotient of 18, which is again

divided by 2 to get the quotient of 9, which is again

divided by 3 to get the quotient of 3, which is again

divided by 3 to get the quotient of 1.

See how FPs are presented to the left of the vertical line

and the quotients to the right, below the horizontal line.

Now 144 must be expressed as the product of all FP

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

Worked example 2:

Find the prime factorization of 420.

Solution:

2 | 420

———-

2 | 210

———-

3 | 105

———-

5 | 35

———-

7 | 7

———-

end | 1

 

See the presentation method given above.

420 is divided by 2 to get the quotient of 210 which is again

divided by 2 to get the quotient of 105, which is again

divided by 3 to get the quotient of 35, which is again

divided by 5 to get the quotient of 7, which is again

divided by 7 to get the quotient of 1.

See how FPs are presented to the left of the vertical line

and the quotients to the right, below the horizontal line.

Now 420 must be expressed as the product of all FP

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

Sometimes you may have to apply the Divisibility Rules to find out the minimum FP with which we have to perform the division.

Let’s look at an example.

Worked example 3:

Find the prime factorization of 17017.

Solution:

The given number = 17017.

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

Sum of digits = 1 + 7 + 0 + 1 + 7 = 16 is not divisible by 3

and so the given number is not divisible by 3.

Since the last digit is neither 0 nor 5, it is not divisible by 5.

Let’s apply the divisibility rule of 7.

Twice the last digit = 2 x 7 = 14; remaining number = 1701;

difference = 1701-14 = 1687.

Twice the last digit of 1687 = 2 x 7 = 14; remaining number = 168;

difference = 168-14 = 154.

Twice the last digit of 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’s divide by 7.

17017 ÷ 7 = 2431.

Since divisibility by 2, 3, 5, is ruled out

Divisibility by 4, 6, 8, 9, 10 is also ruled out.

Let’s apply the rule of divisibility by 11.

Alternate digit sum of 2431 = 2 + 3 = 5.

Sum of the remaining digits of 2431 = 4 + 1 = 5.

Difference = 5-5 = 0.

So, 2431 is divisible by 11.

2431 ÷ 11 = 221.

Since divisibility by 2 is ruled out, so is divisibility by 12.

Let’s apply the divisibility 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 221 is divisible by 13.

221 ÷ 13 = 17.

We present all these divisions below.

7 | 17017

———-

11 | 2431

———-

13 | 221

———-

17 | 17

———-

end | 1

 

Therefore, prime factorization of 17017

= 7 x 11 x 13 x 17. Years.

Leave a Reply

Your email address will not be published. Required fields are marked *