Un lcm upperboundato

[edriv]

Abbiamo gli interi positivi $ a_1,a_2,\ldots,a_k $ e l'intero positivo n ordinati in questo modo: $ a_k<\cdots<a_2<a_1\le n $
E tali che: $ lcm(a_i,a_j) \le n $ $ \ \quad \forall 1 \le i, j \le k, i \neq j $, dove con $ lcm(a,b) $ indichiamo il minimo comune multiplo (least common multiple) tra a,b.
Dimostrare che:
$ ia_i \le n $ Per ogni i tra 1 e k.

Rubato da: Naoki Sato's dispensa

[piever]

Supponiamo per assurdo che per un valore $ i $ si ha $ ia_i=n+c $ dove $ c $ è un intero positivo.

Per ipotesi $ lcm(a_i,a_{i-1})\leq n $

Di conseguenza possiamo ricavare facilmente che $ GCD(a_i,a_{i-a})\geq \frac{a_{i-1}(n+c)}{in} $

Ora dimostriamo che se $ ia_i>n $ allora $ (i-1)a_{i-1}>n $

Abbiamo che $ a_{i-1}-a_i\geq \frac{a_{i-1}(n+c)}{in} $ quindi

$ (i-1)a_{i-1}\geq (a_i+\frac{a_{i-1}(n+c)}{in})(b-1) $$ \geq n+c-a_i+a_{i-1}-\frac{a_{i-1}}{i}\geq n+c>n $

Di conseguenza, se $ ia_i>n $ allora $ a_1>n $ che contraddice l'ipotesi.