11
$\begingroup$

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.

  • 0
    I suppose you want strictly positive integers, otherwise the answer is $0$.2012-08-28
  • 3
    $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.2012-08-28
  • 5
    @Raskolnikov: The way I learned it, "positive" means $>0$.2012-08-28
  • 0
    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$.2012-08-28
  • 0
    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 :)2012-08-28
  • 0
    @celtschk thank you for your help!2012-08-28

1 Answers 1

7

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

  • 0
    You can write $5\cdot401$ or $5\times401$. There's no need for such crudidities as $5*401$.2012-08-28
  • 0
    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.2012-08-28
  • 0
    Thank you very much! I was looking for a solution like this, and it is very elegant!2012-08-28
  • 0
    @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....2012-08-28