4
$\begingroup$

How can we show that the number of pairs $(a,b)$ (where the pairs $(a, b)$ and $(b, a)$ are considered same) with $\operatorname{lcm}(a, b) = n$ is equal to

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

Where

$n=p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$, $p_i$s are prime for all $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.

$\endgroup$

1 Answer 1

5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ +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? $\endgroup$
    – IVlad
    Sep 6, 2010 at 18:21
  • $\begingroup$ 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$. $\endgroup$ Sep 6, 2010 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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