Suppose $n \geq a_1>a_2>...>a_k\geq1$ and $lcm(a_i,a_j) \leq n$ for $i,j=1,2,...,k$. Show that $ia_i \leq n$.

Question

Could I receive some hints on the problem. I do not know how to touch it since index $i$ seems like it does not depend on any of the other conditions.

Answer 1

Suppose that $ia_i>n$.

Let the LCM of $a_{i-1}$ and $a_i$ be given by $$sa_{i-1}=ta_i$$ where $s$ and $t$ are positive integers. These integers must be different and less than $i$ and so $$a_{i-1}>\frac{i-1}{i-2}a_i>\frac{i-1}{i-2}\frac{n}{i}.$$ Then $$(i-1)a_{i-1}>\frac{i^2-2i+1}{i^2-2i}n>n.$$ We can now repeat this argument for $(i-1)a_{i-1}$, and we get: $$a_1>2a_2> ...>(i-1)a_{i-1}>n.$$ A contradiction.

Answer 2

HINT Consider the case $k=2$. (It's always a good idea if you're stuck to try an easy case.)

If the result you are trying to prove is false then you have two unequal numbers, both greater than $\frac {n}{2}$. Their LCM is a multiple of each of the two numbers and, since they are unequal, it cannot be the same multiple of each. So the LCM must be at least twice one of the numbers and is therefore greater than $n$, a contradiction.

Can you now do the cases $k=3, 4, ... $?