Number Theory Least Common Multiple Question

Question

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.

I suppose you want strictly positive integers, otherwise the answer is $0$.
$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.
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$.
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 :)

N. S. · Accepted Answer · 2012-08-28 16:27:14Z

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.

edited Aug 28 '12 at 16:27

answered Aug 28 '12 at 16:14

N. S.
27.2k22760

	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

1 Answer