Finding Prime Factors of FactorialsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/