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.

  • 0
    Possible duplicate: http://math.stackexchange.com/questions/4152/pairs-of-numbers-with-a-given-lcm2011-09-06
  • 0
    @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!2011-09-06
  • 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$.

  • 1
    Curiously, this answer is also the number of divisors of $N^2$. Can you think of a direct proof?2011-09-06
  • 1
    @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.2011-09-06
  • 0
    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.2011-09-06
  • 0
    @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).2011-09-06
  • 0
    @Srivatsan Narayanan:Thanks!2011-09-06