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.

I don't know how I could find, WITH proof, the smallest possible least common multiple of three positive integers which sum to $2005$.

If someone can provide a proof I would be very happy.

share|improve this question
    
I suppose you want strictly positive integers, otherwise the answer is $0$. –  Raskolnikov Aug 28 '12 at 16:11
2  
$2005=5\cdot 401$ where both $5$ and $401$ are primes. Since $401$ is the larger one, it should be ideal if all summands contain that factor, that is, are of the form $k\cdot 401$. The three $k$-factors have to add to five, which for three positive integers is only possible for $1+2+2$, which gives $2005 = 401 + 802 + 802$ where $\operatorname{lcm}(401,802,802)=802$, therefore I'm pretty sure the correct answer is $802$. However I don't know how to prove it. –  celtschk Aug 28 '12 at 16:12
4  
@Raskolnikov: The way I learned it, "positive" means $>0$. –  celtschk Aug 28 '12 at 16:14
    
Small lcm connote large gcd, which means a large prime factor shared in common, and $5$ and $401$ are the only prime factors of $2005$. –  Michael Hardy Aug 28 '12 at 16:15
    
I got a rough lower bound that the LCM is greater than 668, and by getting the three numbers to divide each other, I got an LCM of 802. I see @celtschk went along the same lines. I think this is a pretty good candidate for a computer check :) –  rschwieb Aug 28 '12 at 16:16

1 Answer 1

up vote 7 down vote accepted

$2005=4\cdot401$ with $401$ prime.

Then

$$2005=2\cdot401+2\cdot401+401 \,.$$

Thus we found three numbers with lcm 802. We claim that this is the smallest possible value.

Suppose by contradiction that we can find

$a+b+c =2005$ and $l=\operatorname{lcm}(a,b,c) < 802$. We can assume that $a \leq b \leq c$.

Since $b, c \leq l$ it follows that

$$ 2005=a+b+c \leq a+2l < a+2\cdot802$$

Thus $a > 401> \frac{l}{2}$. Since $a> \frac{l}{2}$ and $a\mid l$, it follows that $a=l$.

Then $$l =a \leq b \leq c \leq l \Rightarrow a=b=c=l \Rightarrow 3l=2005$$

Contradiction.

share|improve this answer
    
You can write $5\cdot401$ or $5\times401$. There's no need for such crudidities as $5*401$. –  Michael Hardy Aug 28 '12 at 16:18
    
Shouldn't it be "$b,c\le l$" in line 7 (and then of course also for the first inequality sign in the following line)? That of course doesn't invalidate the proof. –  celtschk Aug 28 '12 at 16:25
    
Thank you very much! I was looking for a solution like this, and it is very elegant! –  Nitesh Aug 28 '12 at 16:27
    
@celtschk Ty fixed. Nitesh You were welcome. The proof is pretty natural once you realize that the only way some numbers with fixed sum have low lmc is if they have a big common part. If 2005 would had have different prime factorization the problem could had been terrible.... –  N. S. Aug 28 '12 at 16:30

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.