How do i show that :$\sum_{i=1}^{n} \frac{1}{a_i}<2 $ using both $\ Lcm $, and $\gcd$?

Question

let $a_1, a_2 ,a_3,\cdots a_n $ be a sequence of distinct integer numbers

such that each term is less than $1000 $ and$\ Lcm (a_i,a_j)=1000 $ where $i\neq j$ are positive integer .

, My question here is :

How do i show that :$\sum_{i=1}^{n} \frac{1}{a_i}<2 $ using both $\ Lcm (a_i,a_j)$ and $\gcd(a_i,a_j)$ ?

Source: This is a Russian olympiad math .$1951$, really it's solved using only $\ Lcm(a_i, a_j)$ .

Thank for any help

Answer 1

Since $1000 = 2^3 5^3$ it has $16$ divisors for the $a_i$ namely $1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000$

The sum of their reciprocals is $2.34$ which is slightly too much

If one of the $a_i=1$ then for all the others we have $\operatorname{lcm}(1,a_j)=1000$ so $a_j=1000$ making the sum of reciprocals $1.001 \lt 2$

If none of the $a_i=1$ then the sum of reciprocals is no more than $1.34 \lt 2$

Answer 2

We have that $lcm(a_i,a_j)=1000$ for $i\ne j.$ So if $a_i=2^{r_i}5^{s_i}$ and $a_j=2^{r_j}5^{s_j}$ it must be $\max\{r_i,r_j\}=\max\{s_i,s_j\}=3$ for any $j\ne i.$ Suppose $a_1= 2^{r_1}5^{s_1}$ has minimum $r$ and $a_2= 2^{r_2}5^{s_2}$ has minimum $s.$ (We assume $r_1s_1\ne 0$ because in such a case $1$ is in the list. So there are only two numbers $1$ and $1000$ and it is $\dfrac 11+\dfrac{1}{1000}<2.$) So, they must be of the form $a_1= 2^{r_1}5^{3}$ and $a_2= 2^{3}5^{s_2}.$ Now, the list can only contain one more number $a_3=1000.$ In other case $a_3=2^{r_3}5^{s_3}$ fails one of the equalities $lcm(a_1,a_3)=lcm(a_2,a_3)=1000.$ Thus

$$\sum_{i=1}^n\dfrac{1}{a_i}\le \dfrac{1}{2^{r_1}5^{3}}+\dfrac{1}{2^{3}5^{s_2}}+\dfrac{1}{1000}< \dfrac{1}{125}+\dfrac{1}{8}+\dfrac{1}{1000}<2.$$