Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
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

1 Answer 1

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|improve this answer
    
Nice! I like it. –  Kirthi Raman May 7 '12 at 11:31

Your Answer

 
discard

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.