# Find the Prime Factorization

Prime factorization is a way of expressing a number as a product of prime numbers.  Due to the commutative property of multiplication the order of numbers in a product does not matter. Hence the prime factorization of a number is unique.

Example:
The Prime factorization of the number 56 is , 56 = 2 x 2 x 2 x 7 or using exponents 56 = 23 x 7.

## How to find the prime factorization ?

The prime factors of the given number are found using divisibility tests or trial divisions.The quotient obtained at each level of division is again tested for division. The process is continued till the quotient obtained is a prime number. The prime factorization of the numbers is then written as the product of all prime divisors and the final prime quotient.

Example:
Find the prime factorization of each number 156 and 255.
First let us find the prime factorization of 156.
Since 156 is an even number, it is divisible by 2.  Division of 156 by 2 yields a quotient 78. The number can be now written in factored form as,
156 = 2 x 78
Again 78 is divisible by 2 and the division yields the quotient 39. Now the factored form of 156 is
156 = 2 x 2 x 39.
The sum of the digits of the number 39 is 3+9 = 12 which is divisible by 3. Hence 39 is divisible by 3. The division of 39 by 3 yields the quotient 13. The quotient 13 is a prime number.  Hence the division cannot be continued. The required prime factorization is therefore,
156 = 2 x 2 x 3 x 13     or using exponents 156 = 22 x 3 x 13.

A factor tree gives a visual explanation of the process involved.
156
/\
/  \
Prime factor  →         78
/\
/  \
Prime factor  →            2  39
/\
/  \i
Prime factor  →               13   ← Prime factor.

Now to find the prime factorization of 255.
Since the ones digit is 5, the number is divisible by 5. The quotient on division of 255 by 5 is 51.
255 = 5 x 51
The sum of the digits of the number 51, 5+1 =6 is divisible by 3. Hence 51 is divisible by 3. The division of 3 yields a quotient 17.
51 = 3 x 17
and 255 = 5 x 3 x 17.  Since the last quotient is a prime number, the division is not continued. Thus the required prime factorization is
255 = 3 x 5 x 17.

## Prime  factorization to find the GCF of numbers

The greatest common factor of two or more numbers is the product of all common factors of the numbers given. To find the GCF, the prime factorization for all the numbers is first done.  From the list of prime factors of each number, the common factors are picked and then the GCF is calculated.

Example:
Find the GCF of the numbers 36 and 48.
First we need to write the prime factorizations for the numbers given.
36 = 2 x 2 x 3 x 3                and          48 = 2 x 2 x 2 x 2 x 3.
Picking the highlighted common factors and multiplying them,
GCF of 36 and 48 = 2 x 2 x 3 = 12.

## Finding LCM using prime factorization

The least common multiple of two or more numbers is the least multiple common to all the numbers.
One method of finding the LCM is to list the multiples of the numbers given and picking the first occurring common multiple in the lists as the LCM. This will work fine for smaller numbers. But for larger numbers, finding the multiples is not an easy task. So we can follow the following steps.
1. Write the prime factorization of the given numbers.
2. Find the GCF of the numbers using the prime factorization.
3. The LCM is the product of GCF and the left out non common numbers in the prime factorization.

Example:
Find the LCM of the numbers 36 and 48 using prime factorization.
The prime factorization for 36 and 48 are
36 = 2 x 2 x 3 x 3    and   48 = 2 x 2 x 2 x 2 x 3
Picking the common factors, the GCF = 2 x 2 x 3 = 12
Now LCM is got by multiplying the GCF with the left out factors in the prime factorization.
LCM of 36 and 48 = 12 x 3 x 2 x 2 = 144.