Un conjunto $\mathcal{C}$ formado por dos o más enteros positivos tiene la siguiente propiedad: si escogemos cualesquiera dos de sus elementos (distintos), calculamos su máximo común divisor y sumamos $1$, obtenemos un elemento de $\mathcal{C}$. Determine cuántos elementos puede tener $\mathcal{C}$ como mínimo, si el mayor elemento es $120$.
Probemos primero que $2$ es un elemento de $C$. Sean $c_1 < c_2$ los dos elementos más pequeños de $C$ y sea $d=\text{mcd} (c_1, c_2)$, como $d$ es un divisor de $c_1$ tendremos $d\leq c_1$ y como $d+1$ deberá ser un elemento de $C$ solo podrá ser igual a $c_1$ o a $c_2$ pues $d+1\leq c_1+1\leq c_2$. Como $d$ es un divisor de $c_1$ y $c_2$ ya sea que se cumpla que $d+1=c_1$ o $d+1=c_2$ se tendrá que $d|d+1$ y esto implica que $d=1$ y así concluimos que $d+1=2$ pertenece a $C$.
Ahora, como $120$ y $2$ pertenecen a $C$ el número $\text{mcd} (120, 2)+1=3$ pertenece a $C$, similarmente deducimos que $\text{mcd} (120, 3)+1=4$ pertenece a $C$, luego del mismo modo $\text{mcd} (120, 4)+1=5$ pertenece a $C$, luego $\text{mcd} (120, 5)+1=6$ pertenece a $C$ y también $\text{mcd} (120, 6)+1=7$ pertenece a $C$.
Hasta ahora tenemos que los números $2, 3, 4, 5, 6, 7, 120$ pertenecen $C$ y así $C$ tiene al menos $7$ elementos. Consideremos el conjunto $C'=\{2, 3, 4, 5, 6, 7, 120\}$ con $7$ elementos, probaremos que $C'$ cumple las condiciones pedidas para un conjunto $C$ y así probaremos que la menor cantidad posible de elementos de un conjunto $C$ es 7. Sean $x, y$ cualesquiera dos elementos distintos de $C'$, es fácil observar que $\text{mcd} (x, y)$ será menor o igual que el segundo elemento más grande de $C'$, es decir $\text{mcd} (x, y) \leq 7$, pero en el conjunto $C'$ no hay dos múltiplos de $7$ por lo que $\text{mcd} (x, y) \leq 6$. Luego, $2\leq \text{mcd} (x, y)+1 \leq 7$ y como los números del $2$ al $7$ pertenecen a $C'$ entonces $C'$ cumple lo pedido.
