Prove that if $\mathop{\mathrm{lcm}}( a, b) + \gcd(a, b) = a+b$, $a$ divides $b$ or $b$ divides $a$.

This problem seemed simple at first, however I cannot figure out a way to prove this. If I assume both parts of the statement, I can show it is true, but that is not a valid proof method.

  • $\begingroup$ ... or $b$ divides $a$. $\endgroup$ – ccorn Jul 27 '15 at 3:00
  • $\begingroup$ Yes, sorry, I have updated it $\endgroup$ – Young Padawan Jul 27 '15 at 3:01
  • $\begingroup$ Please use LaTeX notation like this: $\gcd(a,b)\operatorname{lcm}(a,b)=ab$ which typesets as $\gcd(a,b)\operatorname{lcm}(a,b)=ab$. Oh, and this example could be understood as a hint. $\endgroup$ – ccorn Jul 27 '15 at 3:08
  • $\begingroup$ @ccorn It hasn't seemed to help me $\endgroup$ – Young Padawan Jul 27 '15 at 3:10
  • 1
    $\begingroup$ ccorn's hint is: show that $\gcd(a,b)$ and $\text{lcm}(a,b)$ are roots of $x^2-(a+b)x+ab$. $\endgroup$ – Batominovski Jul 27 '15 at 3:27

Let $d = \gcd(a, b)$, and let $a = dA$ and $b = dB$.

Then, since $\operatorname{lcm}(a, b) =\frac{ab}{\gcd(a, b)} =\frac{ABd^2}{d} =ABd $, $d+ABd =Ad+Bd $, so $1+AB =A+B $ or $0 =AB-A-B+1 =(A-1)(B-1) $.

Therefore either $A=1$ or $B=1$. If $A=1$, then $a = dA = d$ divides $b = dB$. Similarly, if $B = 1$, $b$ divides $a$.

  • $\begingroup$ Ah, Mr. (or, more likely, Dr. Prof.) Hardy. You are definitely a smooth operator(name). Me, I'm too lazy - I will use $a, b, c$ for $\alpha, \beta, \gamma$ and, in general, anything to minimize keystrokes. $\endgroup$ – marty cohen Jul 27 '15 at 5:21

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.