Prime factorization

Prime factorization is expressing a positive integer as product of its prime factors.

Consider, for example the number 100.

The factors of 100 are: 1, 2, 4, 5, 10, 20, 50 and 100.

Among the factors of 100, only 2 and 5 are prime numbers.

Therefore, the prime factors of 100 are 2 and 5.

If 100 is expressed as product of only the prime factors 2 and 5, then such an expression is called prime factorization of 100.

Below, we will discuss two methods of carrying out prime factorization of a natural number. They are:

1. Factor tree method and
2. Division method.

1. The factor tree method of prime factorization:

In the above method, the natural number 100 was repeatedly expressed as product of its factors, until all of the factors are prime numbers.

100 = 2 × 50 = 2 × 2 × 25 = 2 × 2 × 5 × 5

Using exponents laws, 100 = 2² × 5²

This method of resolving a number into only its prime factors is called prime factorization.

And this method of prime factorization  is called factor tree method.

Now, let us resolve 100 into its factors differently:

100 = 50 × 2 = 25 × 2 × 2 = 5 × 5 × 2 × 2

Using exponents laws, 100 = 5² × 2²

In this factor tree of prime factorization, though the order of prime factors is different, but 100 has been resolved into a same group of prime factors, i.e. 2 and 5.

So, the prime factorization of a natural number using the factor tree method yields a same group of prime factors

A few examples of factor tree method of prime factorization

1. 210 = 2 × 105 = 2 × 3 × 35 = 2 × 3 × 5 × 7
2. 84  = 2 × 42 = 2 × 2 × 21 = 2 × 2 × 3 × 7

From these examples, factor tree method is a protracted procedure, involving repetition of writing same factors.

The division method proves better by being easier and faster.

2. Division method of prime factorization

Let us divide number 100 only by its prime factors, starting from 2 as below:

The above method is dividing a natural number, such as 100, by its prime factors.

The division process ends, when 1 is the quotient, or the number to be divided further.

Therefore, the prime factorization of 100 thru the division method is

100 = 2 × 2 × 5 × 5

Using exponent laws, the prime factors can be grouped as under

100 = 2² × 5²

Some more examples of prime factorization of numbers using division method:

Problem 1:

How many prime factors does A have, if A is the product of all the positive integers from 2 through 10?

Solution:

A = 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10 =

2 × 3 × 2 × 2 × 5 × 2 × 3 × 7 × 2 × 2 × 2 × 3 × 3 × 2 × 5 =

2⁸ × 3⁴ × 5² × 7¹

Therefore, A = 2⁸ × 3⁴ × 5² × 7¹.

But 2⁸ × 3⁴ × 5² × 7¹ is prime factorization of A.

Therefore the prime factors of A will be the bases in the product:

2⁸ × 3⁴ × 5² × 7¹

which are 2, 3, 5 and 7.

Hence A has 4 prime factors.

Problem 2:

Find the greatest prime factor in the following sum:

3 + 3² + 3³

Solution:

3 + 3² + 3³ = 3 × (1 + 3 + 3²) = 3 × (13) = 3 × 13

Since, 3 × 13 constitutes prime factorization of the given sum, the greatest prime factor is 13 in the sum:

3 + 3² + 3³