# Least Common Multiple and Greatest Common Divisor

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.

• ... or $b$ divides $a$. – ccorn Jul 27 '15 at 3:00
• Yes, sorry, I have updated it – Young Padawan Jul 27 '15 at 3:01
• 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. – ccorn Jul 27 '15 at 3:08
• @ccorn It hasn't seemed to help me – Young Padawan Jul 27 '15 at 3:10
• ccorn's hint is: show that $\gcd(a,b)$ and $\text{lcm}(a,b)$ are roots of $x^2-(a+b)x+ab$. – 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$.
• 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. – marty cohen Jul 27 '15 at 5:21