Results 1 to 4 of 4

- Jun 1st 2010, 08:27 PM #1

- Jun 1st 2010, 08:50 PM #2

- Jun 1st 2010, 09:05 PM #3

- Jun 1st 2010, 10:10 PM #4
It should be clarified whether (a,b) is equivalent to (b,a). For example, if n = 10, should we count (a,b) = (2,5) and (a,b) = (5,2) as distinct or not?

Are you familiar with the function that gives the number of divisors of n, commonly notated ? You can read more about it at MathWorld, and the way to calculate it is as the product, . The reasoning behind this calculation is the same we need for our problem.

So suppose that (a,b) and (b,a) are distinct. So how many ways are there to choose the exponent of a particular for a and b, in order to satisfy condition (2) in my above post? It is , which we can get in two ways. We can think in this way: let divide a and not b. Then there are ways to choose the exponent for b. Same in reverse. Now let divide both a and b. There is only one way for this to happen. So we get . Or we can think in this way: There are ways to choose the exponents not necessarily satisfying condition (2). The ways for (2) to fail is just . Subtracting the second value from the first, we get the same result.

Do this for each prime and we get that the number of pairs (a,b) equals .

The answer for the non-distinct version is easily obtained from this. There is only one way to get a = b, and that's if a = b = n. So we just take half of the value above (which will always be odd) and round up.

Note that I omitted the trivial case n = 1 (which you would want to address for completeness).