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

  • $\begingroup$ Does "less than $1000$" mean $< 1000$, or $\leqslant 1000$ in the problem statement? $\endgroup$ – 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$

  • $\begingroup$ 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. $\endgroup$ – 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.$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.