Factoring Factorials

Date: 05/24/97 at 11:29:00
From: Andrew
Subject: Factorization

If 30! is factored into primes, how many fives will the factorization 
contain?

I read your section on factorization, but I am not sure how to start 
since the product is so large.

Date: 06/24/97 at 16:25:07
From: Doctor Sydney
Subject: Re: factorization

Andrew -

Factoring is seeing which numbers, when multiplied together, give you 
a specific number.  30! means 1 x 2 x 3 x ... x 29 x 30, so instead 
of multiplying them all out and then factoring the product, you can 
just factor the smaller parts of it, namely the numbers from 1 to 30. 
That is why 30! is called "thirty factorial" - it's broken up into 
factors when you write it out (though they're not prime factors). 

To factor a number, you write the number down as a product of numbers, 
each of which is a "prime" number. A "prime number" can be divided 
only by itself and the number 1. For instance, the number 5 is prime 
because only 1 and 5 divide it (2, 3, and 4 don't divide it!). The 
number 10, on the other hand, is not prime because it is divisible by 
2 and 5.

So, how do we actually go about factoring a number?  Good question!  
One way to factor a number is known as using a "factor tree."  To 
factor using this method, you first write the number you are factoring 
as a product of two or more numbers.  For example, suppose we want to 
factor the number 30.  We know that 30 = 5 x 6, so we write for the 
first step of our factor tree:

               30
              /  \
             5    6

Next we factor the factors, if possible.  In other words, for each 
number in the product from the first step, we try to write it down as 
a product of even smaller numbers. For instance, in our example, we 
would try to factor both 5 and 6. As we noted above, 5 is prime, so 
we can't factor it further. We are done with that branch of the factor 
tree. However, 6 is not prime. 6 = 2 x 3, so we can extend our factor 
tree as follows:

               30
              /  \
             5    6
                 / \
                2   3

Now, we continue this process until all of the branches of the tree 
end in prime numbers. In our example, we are done after two steps, 
since 5, 2, and 3 are all prime numbers. Once we have finished our 
tree, we are done factoring our number: The factors of the number are 
the numbers at the end of the different branches on the factor tree.  
To figure out what power each prime factor is raised to, count the 
number of times the prime factor appears in the factor tree. In our 
example, each of the factors appears only once, so the prime 
factorization of 30 is:  30 =  2 x 3 x 5.

Let's look at another more complicated example. Factor 120 into prime 
factors. First, we write 120 as a product of two or more numbers. We 
could choose any two factors, like 12 and 10 or 30 and 4, or we could 
choose 3 factors, like 30, 2, and 2. Let's choose 30 and 4. Our first 
step, then, is to write the first branches of our factorization tree:

                 120
                 / \
                4  30

Now we factor 4 and 30. 4 = 2 x 2, and we already factored 30 above 
so, we end up with the following factor tree:

                 120
                 / \
               4    30
              / \   / \
             2  2  5   6
                      / \
                     2   3 
              
Since the ends of the branches (2, 2, 5, 2, and 3) are all prime 
numbers, we are done factoring, and we have found that 
120 = 2 x 2 x 5 x 2 x 3, or to write it in a more orderly fashion, 
120 = 2 x 2 x 2 x 3 x 5.

Okay, enough on factorization. Let's look at your problem and see if 
we can use a factor tree to help us to arrive at a solution. We have 
been given the number 30! and we have been asked to figure out how 
many 5's are in the prime factorization. Well, whenever we factor 
something using the factor tree method, we start by writing our 
number as a product of 2 or more numbers, right?  Lucky for us, 
30! can quite easily be written as a product of two or more numbers.  
Since 30! = 2 x 3 x 4 x ... x 30, we can write the first part of our 
factor tree as follows:

                           30!
                       / / / ... \
                      2 3 4  ...  30

To get the prime factorization of 30!, we would proceed by factoring 
each of the numbers in the product of the first step. That is, we 
would factor 2, 3, 4,... and so on all the way up to 30. To solve 
your problem, however, we don't need to find a prime factorization. 
That would be pretty laborious, eh? 
 
What we want to know is how many 5's are in the prime factorization.  
In other words, how often does 5 appear in the factor tree? How can 
we figure this out?  Well, look at each branch of the factor tree and 
figure out how many fives it contains; the total number of fives in 
all of the branches is the number of fives in the prime factorization.  

I hope this helps. Please do write back if you are still confused or 
have any more questions.

-Doctors Mandel and Sydney,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/