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.

How can we show that the number of pairs (where $(a, b)$ is the same as $(b, a)$) with $LCM(a, b) = n$ is equal to:

$\frac{(2e_1+1)(2e_2+1)...(2e_k+1)+1}{2}$

Where

$n=p_1^{e_1}\cdot p_2^{e_2}\cdot ...\cdot p_k^{e_k}, p_i\space prime\space \forall 1\leq i\leq k$

I managed to guess this formula for a programming problem I was working on, but I'd be interested in a deduction or proof.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

First count the pairs with $\gcd(a,b)=n$ counting $(a,b)$ and $(b,a)$ as distinct. You have $a=\prod p_i^{r_i}$ and $b=\prod p_i^{s_i}$ and need $\max(r_i,s_i)=e_i$ for all $i$. So, given a positive integer $e$, how many pairs $(r,s)$ of nonnegative integers are there with $\max(r,s)=e$?

share|improve this answer
    
+1, I see it now. Assuming $r=e$, then there are $e+1$ such pairs, so $2e+1$ if we consider $(s,r)$ distinct. Does this mean the formula can be simplified to avoid a division by $2$ at the end? Is there a way to count it directly for unordered pairs? –  IVlad Sep 6 '10 at 18:21
    
It's best to compute the number of ordered pairs and then at the last stage adjust to count ordered pairs. They come in twos except for those with $a=b$. –  Robin Chapman Sep 6 '10 at 18:53
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.