Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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  
(1,2012) (2,2012) (4, 2012) (503,2012) (1006,2012) (2012,2012) (4,503) (4,1006) –  Srivatsan Sep 6 '11 at 23:09
add comment

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
1  
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
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. –  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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.