Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
LCD is a technology for monitors. Did you mean lcm? –  Asaf Karagila Feb 24 '13 at 21:25
1  
I assume it means least common divisor –  user63566 Feb 24 '13 at 21:30
2  
@R.J.Stephen That would be a funny way of writing $1$. –  Alexander Gruber Feb 24 '13 at 21:31
1  
What have you tried? Have you looked at examples? –  Qiaochu Yuan Feb 24 '13 at 21:31
    
@Alexander Gruber, except 1 obviously –  user63566 Feb 25 '13 at 19:38

3 Answers 3

up vote 4 down vote accepted

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$.

share|improve this answer

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.$

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.