فاکتورهای شمارش تعداد زیادی

Counting Factors of Large Numbers. Consider this question. How many factors does 8,400 have? Well, hm, that’s a large number. For smaller numbers, numbers less than 100 we.

We could simply list the factor pairs, but that would take too long for a number as large as this. Fortunately, there’s a trick we can use to answer this question. So, this trick involves a four step procedure. Step one is simply finding the prime factorization of the number. Okay. That’s something we can do.

Clearly, 8,400 is 84 times 100. 84 is 7 times 12. Of course, a 100 is 10 times 10. Break this all into prime factors, group these all together. We get 2 to the 4th times 3 times 5 squared times 7. That’s the prime factorization.

We need to get the prime factorization into this form with powers of the prime numbers. So we actually need those exponents, because step two is we’re gonna make a list of the exponents of the prime factors. Well, this is a bit curious. Clearly, 2 has an exponent exponent of 4.

5 is an exponent of 2. But the 3 and the 7, they’re just kind of sitting there. They don’t have an exponent it looks like. Whenever you have one factor of something, that’s really an exponent of 1. We don’t write the exponent of 1, because it would be redundant, but it really has an exponent of 1.

And therefore, reading across those exponents are 4, 1 on the 3, 2 on the 5 and then 1 on the 7. 4, 1, 2, 1. That’s our list of exponents. So that’s step two, we have this list. Step three, add 1 to every number of the list.

So we had 4, 1, 2, 1, add 1 to each one of those numbers, we get 5, 2, 3, 2. That’s our new list. All we’ve done is we’ve added 1 to each number. Once we have this new list, multiply all those numbers together. So, 5 times 2 times 3 times 2. Well clearly, 5 times 2 is 10, 3 times 2 is 6.

Multiply this together, we get 60. The number 8,400 has 60 different factors. So those factors, of course would include 1, which is a factor of every number and 8,400. Of course, every number is a factor of itself. So those would be two numbers on the list.

Altogether, there are 60 numbers on this list. At the end of this video, I will discuss why this procedure works. Lets review the steps. To find the number of factors that positive integer N has. Find the prime factorization of N and write it in terms of the prime factors, powers of the prime factors, because we actually need those exponents.

Step two is create a list of the exponents. Remember to use 1 for a prime factor that has no exponent. Once we have that list, step three is add 1 to every number on the list, creating a new list. And once we have that new list, multiply them altogether. Find the product of that new list, that product is the number of factors N has.

Let’s practice on another large number. How many factors does 21,600 have? Well first of all, why don’t you pause the video here and try this on your own and then we’ll talk about it. First, the prime factorization.

Well clearly, 21,600, we can write that as 216 times 100. Let’s just handle the 216 separately, first. The 216 is 2 times 108 and the 108 is also divisible by 2, that’s 2 times 54. 54, we can write that as 6 times 9. And then we can break those into individual prime factors and get down to this, the prime factorization of 216.

So incidentally, you could find the prime factorization of 216 if you happen to notice that 216 is 6 cubed. So 6 cubed would be 6 times 6 times 6. That’s 2 times 2, times 2 times 3, times 3 times 3. If you notice that that would be a shortcut. We didn’t need that, we actually got to the prime factorization anyway.

So now we multiply this by the prime factorization of 100, which of course is 2 times 5 times 2 times 5. Collect everything together. We get 2 to the 5th times 3 to the 3rd times 5 squared, that’s the prime factorization. Well now, we’re in the home stretch.

Now it’s easy. Now we make, we simply make a list of those exponents, 5, 3, 2. Those are the three exponents of the prime factors. We add 1 to every number on the list 6, 4, 3 and we multiply those together. And of course, that 4 times 3 is 12, so we get 6 times 12 is 72. This number, 21,600 has 72 total factors.

Again, one of those factors has to be 1. One of those factors has to be 21,600. Those would be two factors on the list, but there are 72 factors on the list all together. To find the number of odd factors, basically we would repeat this procedure, but ignore the factors of 2.

So, we’d find the prime factorization as usual. We’d make a list of the exponents of odd prime factors, the odd prime factors only pretending that powers of 2 did not exist. Once we have that list, we add 1 to each number in the list. And multiplied the numbers on the new list together, that’s the number of odd prime factors.

So here again is the prime factorization of 21,600. We’re going to ignore that 2 to the 5th, we’re going to pretend that doesn’t even exist. The only exponents that interest us are the exponent 3 and the exponent 2. Those are the two exponents on the odd prime factors. So our list is just 3 and 2.

Add 1 to each of those, we get 4 and 3. Multiply those two, we get 12. There must be 12 odd factors. We have no direct way to calculate the number of even factors. We have to calculate the total number of factors and the number of odd factors and then subtract.

For example, 21,600 has 72 total factors. 12 odd factors. So it must have 72 minus 12, 60 even factors. At this point, I will discuss a little about why this procedure works. If you understand this, it will help you remember the procedure and it will also help you on other kinds of math problems.

So it actually is not a waste of time at all to really understand why this procedure works, but knowing this is not strictly necessary for the test. So if you don’t wanna learn anything beyond the bare minimum you need for the test, you can just skip the rest of the video. That’s perfectly fine. So, why does this work?

Let’s go back to 21,600, that’s the prime factorization. The factors of this number must be built of these prime factors. Remember, what we discussed in the last video. That’s one of the uses of the prime factorization, it allows us to see any possible factor of the number. If the factor F is built of these prime factors, how many powers of 2 could F contain?

Well, F might contain no factors of 2 at all or it might contain some. It might contain any number up to 5. Therefore, the possibilities are zero, 0, 2, 3, 4 and 5. That’s six possibilities. That’s a list of the possible number of factors of 2 that F could contain. Similarly, the possibility for factors of three are 0, 1, 2, 3, four possibilities and the possibilities for factors of 5 are 0, 1 and 2, three possibilities.

F could contain no factors of 5, it could contain one factor of 5 or it contain two factors of 5. Those are the possibilities. Any of those possibilities can go with any of the others, so we multiply them. It’s a slightly different way to say the same thing. It’s as if we have three slots and we get to make whatever choice we want in each of the three slots, three separate choices.

So here what we’re doing is we’re trying to build a factor of 21,600. In the first slot, we get to pick how many factors of 2 do we want? We could choose anything on the list from 0 to 5, so that’s six possibilities for that first slot. The second slot we wanna know how many factors of 3 do we want? We could pick anything from zero to three.

In the third slot, we wanna know how many factors of 5 do we want? We can choose anything from zero to two. Now notice, supposedly pick, for example, zero, zero, zero. We pick zero in all three slots. That would produce the factor of 1. And 1 of course is a factor of 21,600, because anything is a, 1 is a factor of anything at all.

We could also max out the list. We could max it out, so we pick 5 in the first slot, 3 in the second slot, 2 in the third slot. And of course, what that would do is give us 21,600 itself. That is the prime factorization of the number. And of course, any number’s a factor of itself, so that’s perfectly fine.

We could get the number itself as one of its factors. Or we could choose, we could mix and match. We could choose any number in one slot and match it with any number in any of the other slots and that would give us one of the factors of 21,600. So overall, the exponents of each prime factor of N, delineate the possibilities for the individual factors of N.

Adding 1 includes the 0 case, because any individual factor of N may or may not include any one of the prime factors. For example, among the prime factors of 21,600, 36 is a factor that doesn’t have 5 as a factor. That would mean that we set 0 in the third slot to get a factor of 36. 100 is a factor that doesn’t have and threes as a factor.

So we’d have 0 in the second slot to get a factor of 100. 75 is a factor that doesn’t have 2 as a factor. So we’d have to have a 0 in the first slot to produce 75. Finally, we multiply the possibility. 6 in the first slot, then 3 in the sec, 4 in the second slot and 3 in the third slot.

We multiply those. Why do we multiply them? Well, it may be intuitive to you, the mix and match principle. If it’s not intuitive to you, this piece will make more sense when you learn the Fundamental Counting Principle in the Counting module. So don’t worry about that so much now, you’ll get to it later when you study the counting videos.

In summary, to the number of factors of N. Here are the steps, you find the factorization of N. List the exponents, add 1 to create a new list and find a product of the new list. There’s a similar procedure to find the number of odd factors. If we want the number of even factors, we have to find all the factors, subtract the number of odd factors.

And we discussed a little about why the procedure works.