1
$\begingroup$

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.

  • 1
    (1,2012) (2,2012) (4, 2012) (503,2012) (1006,2012) (2012,2012) (4,503) (4,1006)2011-09-06

1 Answers 1

5

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$.

  • 0
    @Srivatsan Narayanan:Thanks!2011-09-06