Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer
Nice! I like it. – Kirthi Raman May 7 '12 at 11:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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