How Many Factor Pairs Does a Given Number Have?Date: 03/19/2004 at 10:53:48 From: BJ Subject: Factorization/Prime Numbers When trying to factor a trinomial, I multiply the leading coefficient and the constant, then break the result into a prime factorization. Then I try to list all possible pairs of factors based on that prime factorization. I'm wondering if there is a formula or algorithm that will tell me exactly how many pairs of factors a number has? This would eliminate the chance of me missing factor pairs and mistakenly calling the trinomial prime when it really can be factored. For example, 168 breaks down into prime factors of 2^3 * 3 * 7. From these numbers I find the following factor pairs of 168: 2,84 4,42 8,21 3,56 1,168 6,28 -2,-84 -4,-42 -8,-21 -3,-56 -1,-168 -6,-28 I have 12 pairs of factors. Is there an algorithm that would tell me that 168 will have 12 pairs of factors? Date: 03/19/2004 at 12:31:20 From: Doctor Tom Subject: Re: Factorization/Prime Numbers Hi BJ, Well, it won't tell you there are 12 pairs since there are in fact 16 (you left out 7,24 and 12,14 and their negatives), but here's the algorithm that will give the correct answer: Look at the exponents on the prime factors. In your example, they are 3, 1 and 1: 168 = (2^3)(3^1)(7^1). Take all the exponents, add 1 to each, and multiply the numbers: (3 + 1)(1 + 1)(1 + 1) = 4*2*2 = 16 There's the answer unless the number happens to be a perfect square in which case you need to add 1. Here's why it works. I'll just explain for your example, and you can see why it'll always work. Let's begin by making a list of all the factors. The factor will have some number of powers of 2 in it between 0 and 3: (0, 1, 2 or 3). Thus there are 3 + 1 = 4 choices for the number of factors of 2. Similarly, there are 0 or 1 factors of 3 and 0 or 1 factors of 7. Once you choose the number of each of the prime factors in your divisor, you know what that divisor is. There are 4 ways to choose the number of factors of 2; 2 ways to choose the number of factors of 3 and 2 ways to choose the number of factors of 7, so there are 4*2*2 = 16 factors. Each of those factors pairs with another different one (unless the original number is a perfect square) so you'll divide the number by 2. But you can flip the signs of both so you need to multiply by 2 again. In the case of a perfect square, there's a slight problem; let's consider the case 36 = 2^2 3^2. There are 3*3 = 9 factors: 1, 2, 3, 4, 6, 9, 12, 18, 36. They pair up in four pairs: (1, 36), (2, 18), (3, 12) and (4, 9) with 6 left over since it would pair with itself as (6, 6). Thus there are 5 pairs, and doubling that for the signs, we get 10 pairs. Notice that the ONLY time you'll get an odd number for your product is when you've got a perfect square, so another way to describe the algorithm is to work out the product I mentioned above, and then if the result is odd, add 1. That's it! So, if p1, p2, p3, ..., pn are distinct prime numbers, and if N = (p1^k1)(p2^k2)...(pn^kn) Then calculate: M = (k1 + 1)(k2 + 1)...(kn + 1) If M is even, then N has M factor pairs. If M is odd, N has M + 1 factor pairs. - Doctor Tom, The Math Forum http://mathforum.org/dr.math/ Date: 03/19/2004 at 12:46:50 From: Doctor Peterson Subject: Re: Factorization/Prime Numbers Hi, BJ. Yes, there is a simple formula for the number of factors of a number. Given the prime factorization, as in your case 2^3 * 3^1 * 7^1, you can choose any divisor by selecting the exponent for each prime factor, such as 2^2 * 3^0 * 7^1. This gives you 4 choices for the power of 2 (0, 1, 2, and 3), 2 choices for the power of 3, and 2 choices for the power of 7; the total number of divisors is the product of these numbers, 4*2*2 = 16. The number of _pairs_ of positive factors is half that, or 16 (watch out if the number of factors is odd!), and when you include negative factors it's doubled again to 16. So you missed some. The factors should be 2^a 3^b 7^c product --- --- --- ------- 1 1 1 1 2 1 1 2 4 1 1 4 8 1 1 8 1 3 1 3 2 3 1 6 4 3 1 12 8 3 1 24 1 1 7 7 2 1 7 14 4 1 7 28 8 1 7 56 1 3 7 21 2 3 7 42 4 3 7 84 8 3 7 168 You missed 12, 24, 7, and 14. Of course, before I gave up and said the quadratic couldn't be factored, I would check the discriminant, which is foolproof. If you have any further questions, feel free to write back. - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/