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

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

• Does "less than $1000$" mean $< 1000$, or $\leqslant 1000$ in the problem statement? – Daniel Fischer Nov 5 '16 at 22:02

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$

• I am finding it difficult to get higher than $1.001$. For $n=1$ the only possibility is $1000$. For $n=2$ you can have $1000$ and any of the other possible factors, or you can have one of $\{8,40,200\}$ and one of $\{125,250,500\}$. For $n=3$ you can have $1000$ and one of $\{8,40,200\}$ and one of $\{125,250,500\}$. That seems be it. – Henry Nov 5 '16 at 21:37

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

• If you have $a_i=1$ and $a_j=2$ for some $i$ and $j$ then $\operatorname{lcm}(a_i,a_j)=\operatorname{lcm}(1,2)=2 \not =1000$ – Henry Nov 5 '16 at 21:40
• @Henry It is said that $lcm(a_i,a_j)=1000$ for any pair $i\ne j.$ – mfl Nov 5 '16 at 21:44
• Yes: so you cannot have both $1$ and $2$ in the sequence, since their lowest common multiple is not $1000$ – Henry Nov 5 '16 at 21:45
• @Henry I have misundertood the question. I have edited the answer now. Thank you for clarifying me mi mistake. – mfl Nov 5 '16 at 22:49