4
$\begingroup$

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.

1 Answers 1

5

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

  • 0
    +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?2010-09-06
  • 0
    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$.2010-09-06