# GCD and LCM Problem

Let $x$ and $y$ be positive integers, $x < y$, and $x + y = 667$. Find all pairs $(x,y)$ if $\text{lcm}\,(x,y)/\gcd\,(x,y) = 120$. This problem was from my number theory homework, and I don't get it. Any suggestions?

Let be $d=\gcd(x,y)$. Then $d$ divides $667=23\times29$ so $d$ and $s=(x+y)/d$ are in the set$\{1,23,29,667\}$.

On the other hand, $d\,\text{lcm}(x,y)=xy$, so $$p=\frac xd\frac yd=\frac{\text{lcm}(x,y)}d=120$$

Then, $x/d$ and $y/d$ are the roots of the polynomial $$X^2-sX+120$$ Hence, the discriminant $s^2-480$ is a perfect square. This excludes $s=1$. Moreover, $23^2-480=49=7^2$, $29^2-480=361=19^2$ and $667^2-666^2=1333>480$, so $667^2-480$ is not a perfect square.

If $s=23$, then $d=29$ and the roots of the poynomial are $8$ and $15$. This gives $x=232$, $y=435$.

If $s=29$, then $d=23$ and the roots are $5$ and $24$. Now, $x=115$ and $y=552$.

This is ajotatxe's answer from a different point of view.

Let $g = \gcd(x,y)$ and let $X = \dfrac xg$ and $Y = \dfrac yg$ Then

$\qquad X$ and $Y$ are integers
$\qquad X < Y$
$\qquad \gcd(X,Y) = 1$
$\qquad \operatorname{lcm}(X,Y) = XY$
$\qquad \gcd(x,y) = g = g\gcd(X,Y)$.
$\qquad \operatorname{lcm}(x,y) = \dfrac{xy}{g} = gXY = g \operatorname{lcm}(X,Y)$

So

\begin{align} \dfrac{\operatorname{lcm}(x,y)}{\gcd(x,y)} &= 120 \\ \dfrac{\operatorname{lcm}(X,Y)}{\gcd(X,Y)} &= 120 \\ XY &= 120 \\ \end{align}

Keeping in mind that $\gcd(X,Y)=1$, our choices are

$(X,Y) \in \{(1,120), (3,40), (5,24), (8,15) \}$

which translates into

$(x,y) \in \{(1g,120g), (3g,40g), (5g,24g), (8g,15g) \}$

where we still have to figure out what $g$ is.

Since, $x+y = 667$, and the factors of $667$ are $\{1, 23, 29, 667 \}$

We note that

$5g+24g = 29g$ implies $g = 23$

and

$8g + 15g = 23g$ implies $g = 29$

So $(x,y) \in \{23(5,24), 29(8,15) \} = \{ (115,552), (232, 435) \}$.

$$\gcd(x,y) = d\mid667$$ so $$d = 1, 23,$$ or $$29$$. Let $$x = da, y = db, \gcd(a,b) = 1$$. Then $$\frac{\operatorname{lcm}(x,y)}{\gcd(x,y)} = ab = 120$$. Then $$(a,b) = (1,120); (2,60), \cdots, (10, 12)$$.

Then check the pair that satisfy $$a+b = 23,29,$$ or $$667$$.