# Prove that either $m$ divides $n$ or $n$ divides $m$ given that $\operatorname{lcm}(m,n) + \operatorname{gcd}(m,n) = m + n$?

We are given that $m$ and $n$ are positive integers such that $\operatorname{lcm}(m,n) + \operatorname{gcd}(m,n) = m + n$.

We are looking to prove that one of numbers (either $m$ or $n$) must be divisible by the other.

-
LCD is a technology for monitors. Did you mean lcm? – Asaf Karagila Feb 24 '13 at 21:25
I assume it means least common divisor – user63566 Feb 24 '13 at 21:30
@R.J.Stephen That would be a funny way of writing $1$. – Alexander Gruber Feb 24 '13 at 21:31
@Alexander Gruber, except 1 obviously – user63566 Feb 25 '13 at 19:38
What I want to know is, what's the greatest common multiple of $m$ and $n$? Excluding $\infty$, obviously :-) – TonyK Feb 25 '13 at 19:58

We may suppose without loss of generality that $m \le n$. If $\text{lcm}(m,n) > n$, then $\text{lcm}(m,n) \ge 2n$, since $\text{lcm}(m,n)$ is a multiple of $n$. But then we have

$\text{lcm}(m,n) < \text{lcm}(m,n)+\gcd(m,n) = m + n \le 2n \le \text{lcm}(m,n)$,

a contradiction. So $\text{lcm}(m,n) = n$.

-

Hint $\$ For $\rm\:x = gcd(m,n),\ lcm(m,n) = mn/x,\:$ and the equation becomes $\rm\:(x-m)(x-n) = 0.$ Therefore $\rm\:x = gcd(m,n) = m,\:$ so $\rm\:m\mid n,\$ or $\rm\:x = gcd(m,n) = n,\:$ so $\rm\:n\mid m.$

-

Let $a$ be the gcd, and $b$ the lcm. We are told that $$a+b=m+n.$$ It is a result I hope known to you that the gcd of two positive integers, times their lcm, is equal to the product of the two integers. Thus $$ab=mn.$$ So $a$ and $b$ are the roots of the same quadratic equation as $m$ and $n$, namely the equation $x^2-(m+n)x+mn=0$.

Without loss of generality we may assume that $m\le n$. Thus $a=m$ and $b=n$. sinnce $\gcd(m,n)=m$, we conclude that $m$ divides $n$.

-