06 Feb Prime Factorization

If you have taken some maths tuition on prime and composite numbers and understand the concept, it is very likely that you will appreciate the technique of prime factorization. It is an amazing technique of extracting information from composite numbers. As your maths tuition teacher would have already taught you, prime numbers are those numbers which are divisible by only that number and 1. Composite numbers, on the other hand, are divisible by other numbers as well, besides itself and 1. Prime factorization is a powerful technique using which we can decompose composite numbers and can find a lot of information about the number which were not visible on the surface.

Prime Factorization
The fundamental theorem of arithmetic says that every number, except 1, is either a prime or can be written as the product of unique combination of prime numbers. Let us take an example.
Lets us consider the number 36. 36 can be expressed in the following way:
36= 2 x 2 x 3 x 3 = 22 x 32
As you can see, we have written 36 as the product of two prime numbers. According to fundamental theorem of arithmetic, we can express each and every composite number as a product of prime numbers. Further, it also says that this combination is unique – i.e. 36 can be written as a product of prime numbers in only one way – that is using two 3s and two 2s; 36 cannot be expressed as the product of any other combination of prime numbers.
Even though you have taken some math tuition on number theory and are familiar with the concepts of composite and prime numbers, it is difficult to spot just how much information is crammed inside such an expression shown above. Let us take a look.
Finding number of factors
First of all, we could find the number of factors of a number from an expression. How? Let us see. Say, we wanted to find out the number of factors of 120. First, we are going to perform a prime factorization.
120= 10 x 12 =5 x 23 x 3
The next step is to find out all the exponents of the prime numbers. So in this case, the number 5 has an exponent of 1, number 2 has an exponent of 3 and number 3 has exponent of 1. In case you do not know, if a number has no exponent mentioned explicitly, the exponent is 1 which is the case here for the numbers 5 and 3. if you are not sure what an exponent is, you will need to check with your maths tuition teacher.
Once we found the exponents, add 1 to each of the exponents. So the numbers we get are 2, 4 and 2 respectively after adding 1 to each exponent. Next, multiply the numbers and voila! The result is the number of factors for 120 which is 2 x 2 x 4 =16. Let us check our answer. Following is a list of factors if 120.
120 -> Factors 1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120 i.e. a total of 16 factors which matches our answer.

Finding number of odd and even factors
Next, we are going to see how we can find out the number of odd factors. To do that, we are going to ignore the exponent of 2 and then apply the same technique. So, the exponents to be considered in this case are the exponents of 5 which is 1 and the exponent of 3 which also happens to be 1. Next, add 1 to the exponents and multiply them. The number that we get is 4. So 120 has 4 odd factors. Indeed, once we scan our list, we see that there are 4 odd factors 1,3,5 and 15.
To find out the number of even factors, you can first calculate the number of all factors. Then subtract the number of odd factors from the number of all factors and the result will be the number of even factors which, in this case, is 16-4= 12.

Finding sum of all divisors
If finding out the number of factors, number of even factors and number of odd factors was not enough information, we could still find more. We could find out some of all the factors. How? Let us explore.
To find out the sum of all factors, take each prime number and add up all the powers of that number starting from 0 to up to the highest power present.
120= 10 x 12 =5 x 23 x 3
So, we take 2 first. The highest power of 2 present here is 3. So we will have to add 20 + 21+22+23 and the result is 15 (Please note the fact that any number when raised to the power of zero yields 1 and because of this, 20 =1 )
Similarly, we do this for the other numbers 3 and 5.
Highest power of 3 present here is 1. So the resulting sum is 30 + 31 = 4.
Highest power of 5 present here is 1. So the resulting sum is 50+51 = 6.
The next step is to multiply these results. Once we do that, we get 15 x 4 x 6 =360 and this is our answer. The sum of all factors of 120 is 360. If you add all the numbers is the above list, indeed you get 360.
We could also find out the sum of even factors and odd factors from the prime factorization of any number and that is similar to maths tuition homework for you.
As it is clear by now, prime factorization is an extremely powerful technique and by leveraging this technique, you could find lots of information about a number. It is a powerful concept to know and once you master it, you will be able to apply it to tackle a vast range of maths tuition problems. However, please do not mechanically follow the technique. Your first task, now, should be to figure out why these techniques mentioned above work. Why are these techniques able to find out the number of factors, odd factors, even factors and also the sum of factors. This understanding is essential in assimilating the concept. Try to seek help from your maths tuition teachers at math tuition or from your peers in school and try to work on it.