1
$\begingroup$

The greatest common divisor of two positive integers less than 100 is equal to 3. Their least common multiple is twelve times one of the integers. What is the largest possible sum of the two integers?

This problem has defeated me. Any help is greatly appreciated.

$\endgroup$
  • $\begingroup$ And what did you try? $\endgroup$ – Parcly Taxel Dec 6 '17 at 15:06
  • $\begingroup$ lcm(a,b)=12a and gcd(a,b)=3. So lcm(a,b)=gcd(a,b)*4a. So a and b are divisible by 3. That helped me narrow down some values,but I don't know what to do to actually find the values without doing guess and check. $\endgroup$ – ddswsd Dec 6 '17 at 15:09
1
$\begingroup$

Call the two numbers $x$ and $y$ and note that $\gcd(x,y)×\operatorname{lcm}(x,y)=xy$. Substituting what we know we find $$3×12x=xy$$ $$y=36=3×12$$ Then $x$ is the largest number less than 100, divisible by 3 and whose quotient after division by 3 is coprime with 12. 99 and 96 don't work because their quotients (33 and 32) are not coprime with 12, but 93 works. The largest possible sum is thus $93+36=129$.

$\endgroup$
  • $\begingroup$ Damn! That is clever. Thank you! $\endgroup$ – ddswsd Dec 6 '17 at 15:16
1
$\begingroup$

HINT:
Note that those integers are of the form $3a, 3b$ and $3ab=12(3a).$ From here we can find that $b=12,$ and then for $a$ you can pick any odd integer that is not divisible by $3$ and less than $33. $

$\endgroup$

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.