# Solving $xy = a + b\cdot\operatorname{lcm}(x,y) + c\cdot\gcd(x,y)$ given $a,b,c$

Given $a$, $b$, and $c$, find the number of pairs of positive integers $(x, y)$ satisfying this equation:

$$xy = a + b\cdot\operatorname{lcm}(x,y) + c\cdot\gcd(x,y).$$

If $a=2, b= 1, c= 1$, then the answer is 2.

If $a=160, b= 0, c= 90$, then the answer is 8.

If $a=300, b= 7, c= 5$, then the answer is 4.

-
You tagged this "algorithms". Does that mean you are looking for an algorithmic answer, and not necessarily a formula? – Zev Chonoles Feb 19 '12 at 17:41
Looking for formula – jasmine Feb 19 '12 at 17:44
First, note that $xy=lcm(x,y)\gcd(x,y)$. So you first want to find solutions to $LG-bL-cG-a = (L-c)(G-b) - (a+bc) = 0$. – Thomas Andrews Feb 19 '12 at 17:45

First, note that $xy=lcm(x,y)\gcd(x,y)$. So you first want to find solutions to $LG-bL-cG-a = (L-c)(G-b) - (a+bc) = 0$.

So we first need to know the factorizations of $a+bc$.

Even then, we need the conclusion that $G|L$, and then we can get many different $x,y$ for that pair $(L,G)$. Specifically, if $k$ is the number of distinct prime factors of $L/G$, there are $2^k$ different pairs $(x,y)$.

I seriously doubt there is much clever that can be done here.

The case where $L-c=a+bc$ and $G-b=1$ will be yield $G|L$ if and only if $a$ is divisible by $b+1$, in which case, the number of solutions from this pair is $2^k$, where $k$ is the number of distinct prime factors of $\frac{a}{b+1}+c$.

If $a,b,c>0$ and $a+bc$ is prime, these $2^k$ are the only solutions.

For the case $(a,b,c)=(2,1,1)$, $a+bc=3$, and the only factorizations are $(L-c,G-b)=(3,1)$ or $(1,3)$, which yields $(L,G)=(4,2)$ or $(2,4)$. But only the former works, so $(L,G)=(4,2)$ and the number of solutions is $2^1$ since $4/2$ has $1$ prime factor.

For $(a,b,c)=(160,0,90)$, $a+bc=160$, and there are lots of factorizations, the only two of which are relevant are $160=160*1$ and $160=80*2$. Then $(L,G)=(250,1)$ or $(L,G)=(170,2)$. In both cases, $L/G$ has two distinct prime factors, so both factorizations contribute $4=2^2$ solutions.

For $(a,b,c)=(300,7,5)$, $a+bc=335=5*67$. The only relevant factorization is $(L-c,G-b)=(67,5)$, so $(L,G)=(72,12)$, and $L/G=6$ has two prime factors, so there are $4=2^2$, therefore four answers total.

-
Nice! I like it. – Kirthi Raman May 7 '12 at 11:31