Finding Prime Factors of Factorials

Date: 11/26/2004 at 15:07:56
From: Christine
Subject: factorials and primes

How many factors of 2 will be in 100! ?  How many factors of 3 will be
in 100! ?

I don't know how to get prime numbers out of factorials.  Do I just 
use all the numbers 1 through 100 and then look for primes?  I know
that factors of 2 will be even numbers and factors of 3 will be odd
numbers.

100! is 100*99*98*97*96....isn't this a HUGE number?  I think there
must be a pattern I can look for.  Is there a formula?

Date: 11/26/2004 at 16:38:07
From: Doctor Barrus
Subject: Re: factorials  and primes

Hi, Christine!

You're right; 100! is a HUGE number!  Since we can't just multiply it 
out and see how many times 2 goes into it, we do have to use a 
pattern.

Imagine all the numbers from 1 to 100 were written out in a line, in 
order:

  100! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * ... * 100

Let's find what power of 2 divides this product; we'll tackle 3 
later.  Underneath each of these 100 numbers let's write how many 2's 
go into THAT number:

  1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * ... * 100.
  =============================================================
      2       2       2       2        2         2   ...     2
              2               2                  2           2
                              2

You can see that under each multiple of 2 there's at least one 2; 
under each multiple of 4 there are at least two 2's; under each 
multiple of 8 there are at least three 2's (since 8=2*2*2), and so 
on.

Now each of these 2's is multiplied with the rest when we multiply 
the numbers from 1 to 100 together.  So if we can count how many 2's 
appear below our line of numbers, that will tell us the largest 
power of 2 that divides 100.  So how do we do that?

Well, we'll use our illustration and the patterns in it.  First, 
we'll count how many 2's appeared on the FIRST ROW under our number 
list.  There's one in this row for every multiple of 2 between 1 and 
100.  How many multiples of 2 are there?  Well, there should be 50, 
since 100/2 = 50.

Now how many 2's appear in the SECOND ROW under our number list?  We 
have them under 4, 8, 12, 16, and so on.  Note that there is a 2 in 
the second row under each multiple of 4.  (Does that make sense?  Why 
should there always be a 2 in the second row for these numbers?)  So 
we just have to count how many multiples of 4 there are between 1 
and 100.  There are 25, since 100/4 = 25.

How many 2's appear in the THIRD ROW under the list?  They show up 
under each number that 2 goes into three times...that is, each 
number that is divisible by 8.  If you extend your list long enough, 
you'll see 2's in the third rows under 8, 16, 24, 32, and so on.  So 
how many multiples of 8 are there between 1 and 100?  Well, the first 
one is 1*8 = 8, and the last one less than or equal to 100 is 
12*8=96, so there are 12.

We'll continue in this way for each row, until we've covered all the 
rows of 2's:

To review...

  In the FIRST ROW, there are  50 2's.
  In the SECOND ROW, there are 25 2's.
  In the THIRD ROW, there are  12 2's.

...and to finish...

  In the FOURTH ROW, there are  6 2's.
  In the FIFTH ROW, there are   3 2's.
  In the SIXTH ROW, there is    1 2.

So if we add these all up, we see that there are

  50 + 25 + 12 + 6 + 3 + 1 = 97

factors of 2 in a prime decomposition of 100!

I hope that made sense.  You can follow the same reasoning to 
calculate the total number of 3's showing up in a prime decomposition 
of 100!, or any prime, for that matter.  You might try it for 7, 11, 
and other primes, too--what's the largest prime dividing 100! ?

Well, let me know if I can help make anything clearer, and good luck!

- Doctor Barrus, The Math Forum
  http://mathforum.org/dr.math/