# Pairs of numbers with a given LCM

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.

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$?
• +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? Sep 6, 2010 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$. Sep 6, 2010 at 18:53