Find sum of possible pairs for given LCM and GCD

Question

I am given $A$ and $B$. I have to find out sum of $(m+n)$ for all pairs of numbers where $m\leq n$, $\gcd(m,n)=B$ and $\operatorname{lcm}(m,n)=A$

For $A=72$, $B=3$
Possible pairs will be - $(3,72)$, $(9,24)$

This is for a programming problem. I need to find sum for any given A and B.

Answer 1

First, you can solve the case when $B=1$. The general case $A,B$ can be solved then by solving for $A_1=A/B, B_1=1$ and multiplying the answer by $B$.

So, given $A$ and $B=1$, prime factorize $A=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$.

Then a pair $m,n$ with $\gcd(m,n)=1$ and $\mathrm{lcm}(m,n)=A$ is just a partition of the set of primes in $A$.

Turns out that this sum is:

$$\left(1+p_1^{a_1}\right)\left(1+p_2^{a_2}\right)\cdots\left(1+p_k^{a_k}\right)$$

The case $A=B=1$ is a special case, since it is possible for $m=n$ then, so you get $2$.

For example, in the case $A=24, B=1$, $A=2^3\cdot 3$ so the total is $(1+8)(1+3)=36$. And the case $A=72,B=3$ is therefore $3\cdot 36=108$.

First, let's just take the case $A=p^k$ for some prime $p$. Then there is only one pair, $m=1,n=p^k$ and the total is $1+p^k$.

Similarly, if $A=p_1^ap_2^b$, with $p_1^a<p_2^b$, the only pairs or $(m,n)=(1,A)$ or $(m,n)=(p_1^a,p_2^b)$ so the sum is $1+p_1^a+p_2^b+p_1^ap_2^b = (1+p_1^a)(1+p_2^b)$.

In general, for $A>1$, the sum is the sum of all divisors $d$ of $A$ such that $\gcd(d,A/d)$. The trick is to realize that your term $m+n$ is really two separate values of $d$.

It's not clear how efficient this algorithm is - it depends on prime factorization, which is relatively hard in general.