A “fast” way to compute number of pairs of positive integers $(a,b)$ with lcm $N$

I am looking for a fast/efficient method to compute the number of pairs of $(a,b)$ so that its LCM is a given integer, say $N$.

For the problem I have in hand, $N=2^2 \times 503$ but I am very inquisitive for a general algorithm. Please suggest a method that should be fast when used manually.

-
Possible duplicate: math.stackexchange.com/questions/4152/… –  Srivatsan Sep 6 '11 at 22:48
@Srivatsan:Indeed,also seems duplicate to me,but however that is asking for the proof,I have only ask for the method/process ;-)And also thanks for sharing that $N^2$ pattern! –  Quixotic Sep 6 '11 at 22:54
(1,2012) (2,2012) (4, 2012) (503,2012) (1006,2012) (2012,2012) (4,503) (4,1006) –  Srivatsan Sep 6 '11 at 23:09

1 Answer

If $N$ is a prime power $p^n$, then there are $2n+1$ such (ordered) pairs -- one member must be $p^n$ itself, and the other can be a lower power.

If $N=PQ$ for coprime $P$ and $Q$, then each combination of a pair for $P$ and a pair for $Q$ gives a different, valid pair for $N$. (And all pairs arise in this manner).

Therefore, the answer should be the product of all $2n+1$ where $n$ ranges over the exponents in the prime factorization of $N$.

-
Curiously, this answer is also the number of divisors of $N^2$. Can you think of a direct proof? –  Srivatsan Sep 6 '11 at 22:36
@Srivatsan, no direct proof comes to mind. Each divisor $d$ of $N^2$ corresponds to the pair $(gcd(N,d), gcd(N,N^2/d))$, but proving that those are the right pairs -- or even that they are all different -- would seem to require disassembling everything into prime-factor exponents, and then we haven't really gotten anywhere after all. –  Henning Makholm Sep 6 '11 at 22:48
And as I am not looking for only pairs (not ordered) hence the result is $\lfloor \frac{\sigma_{0}(N^2)}{2}\rfloor$.However proving this seems interesting. –  Quixotic Sep 6 '11 at 22:49
@Foo The correct answer is $\lceil \frac{\sigma_0(N^2)}{2} \rceil$. The reason, as Henning explained, is that the $(N,N)$ pair is not double counted by his answer (every other pair is). –  Srivatsan Sep 6 '11 at 22:53
@Srivatsan Narayanan:Thanks! –  Quixotic Sep 6 '11 at 23:02