OliForum Matematico

Determinare per quali $n \in \mathbb{Z}^{+}, n \geq 3$ esistono $n$ interi positivi distinti $a_1, \cdots, a_n$ tali che:
$(a_i,a_j)>1$ $\forall 1 \leq i < j \leq n$
e
$(a_i,a_j,a_k)=1$ $\forall 1\leq i<j<k \leq n$.

N.B. $(x,y)$ sarebbe il massimo comun divisore tra $x$ e $y$.

Sbaglio o vale per qualsiasi $ n $?

Dimostriamo per induzione...
Innanzitutto verifichiamo che la proprietà vale per $ n=3 $. Infatti, prendendo $ a_1=6, \; a_2=10, \; a_3=15 $ osserviamo che:

• $ MCD(a_1,a_2)=2 $
• $ MCD(a_2,a_3)=5 $
• $ MCD(a_1,a_3)=3 $
• $ MCD(a_1,a_2,a_3)=1 $

A questo punto prendiamo una lista $ a_1, \; a_2, \; a_3, \; ... \; a_n $ di $ n $ elementi tali che $ \forall \; 1\leq i\leq n, \; a_i \in \mathbb{Z}^+ $, e che verifichino la proprietà richiesta. Scegliamo ora $ n $ primi distinti $ p_1, \; p_2, \; p_3,\; ... \; p_n $, tali che $ \forall \; 1\leq k\leq n, \; p_k $ non compaia nella scomposizione di alcun $ a_i $.
Possiamo osservare che la lista formata dagli $ n+1 $ elementi $ a_1\cdot p_1, \; a_2\cdot p_2, \; a_3\cdot p_3, \; ...\; a_n\cdot p_n, \; p_1\cdot p_2\cdot p_3\cdot ...\cdot p_n $ verifica ancora la proprietà richiesta, che dunque vale per ciascun $ n\in \mathbb{N}\setminus\left\{0, \; 1, \; 2\right\} $.

Oppure si può costruire un grafo di $n$ nodi dove tutti i nodi sono collegati tra di loro. Su ogni arco scrivi un numero primo, in modo che tutti gli archi hanno un numero primo diverso. Ogni nodo contiene il numero formato dal prodotto dei numeri scritti sui suoi archi.
A questo punto presi due qualunque nodi, essi hanno sicuramente un collegamento e dunque MCD maggiore di 1. Presi invece $3$ nodi, siccome ogni primo compare solo in due nodi, non ci può essere un primo comune a tutti e 3 e quindi MCD=1.