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/