Associated Topics || Dr. Math Home || Search Dr. Math

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/
Associated Topics:
High School Number Theory
Middle School Prime Numbers

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search