Let $x,y$ be positive integers, $x<y$, and $x+y=667$. Given that $\dfrac{\text{lcm}(x,y)}{\text{gcd}(x,y)}=120,$ find all such pairs $(x,y)$.

The only way I can think of solving this is trying all possibilities where one number is odd and the other even, and testing them all. Using this, I found one solution, $(115,552)$, but I'm wondering if there is a more efficient way to do this problem.

  • $\begingroup$ Python script gives $(115,552)$ and $(232,435)$. $\endgroup$ – barak manos Dec 24 '16 at 19:16
  • $\begingroup$ @barakmanos I want to solve without scripts or calculators $\endgroup$ – suomynonA Dec 24 '16 at 19:16
  • 1
    $\begingroup$ Of course, that's why I wrote this as a comment and not as an answer - in order to provide some more insight on the question (BTW, you've failed to specify the other pair for some reason). $\endgroup$ – barak manos Dec 24 '16 at 19:17
  • $\begingroup$ BTW, since the prime factorization of $667$ is $23\cdot29$, there aren't many possibilities to explore (i.e., the $\gcd$ is $\in[1,23,29]$). So you only have $23+29$ pairs to check. $\endgroup$ – barak manos Dec 24 '16 at 19:20

If a number divides $x$ and $y$ then the number divides $x+y$. Therefore $\gcd(x,y)$ is a divisor of $667$.

Since $667=23\times 29$ there are only $4$ cases.

If $\gcd(x,y)=1$ we get $\text{lcm}(x,y)=120$, clearly impossible since one of the numbers is larger than $120$.

If $\gcd(x,y)=23$ then $\text{lcm}(x,y)=23\times 120$, dividing everything by $23$ we must find coprime $x'$ and $y'$ that add to $29$ and have product equal to $120$. Solving the quadratic equation leads to $(5,24)$ and $(24,5)$

If $\gcd(x,y)=29$ then we must find coprime $x'$ and $y'$ that add to $23$ and have product $120$. Solving the quadratic leads to $(8,15)$ and $(15,8)$

If $\gcd(x,y)=23\times 29$ then we must find $x',y'$ that add to $1$ and have product $120$, clearly impossible.

So the only solutions are $(5\times 23,24\times 23),(24\times 23, 5\times 23),(8\times 29, 15\times 29),(15\times 29,8\times 29)$

| cite | improve this answer | |

Let $\dfrac xX=\dfrac yY=(x,y)=d$(say) $\implies(X,Y)=1$


As $120=1\cdot120,2\cdot60,3\cdot40,4\cdot30,5\cdot24,6\cdot20,8\cdot15,10\cdot12$

The possible set of values of $(X,Y)$ such that $X<Y;(X,Y)=1$ are $\{(1,120);(3,40);(5,24);(8,15)\}$

Now use the fact that $\displaystyle667=x+y=d(X+Y)\implies\dfrac{23\cdot29}{X+Y}=d$ which is a positive integer to find the possible set of values of $(X,Y)$ to be $\{(5,24);(8,15)\}$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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