Dejemos que $S$ sea un conjunto de $2009$ números enteros positivos.

Question

Dejemos que $S$ sea un conjunto de $2009$ números enteros positivos. $S$ tiene la propiedad de que para cualquier $a, b, c\in S$ si $gcd(a, b)>1$ Entonces, al menos $gcd(a, c)$ o $gcd(b, c)$ también es mayor que $1$ . Supongamos que no hay ningún grupo de $50$ elementos en los que cada dos de ellos son primos entre sí. Demostrar que existe $40$ elementos de $S$ de manera que cada dos de ellos tengan un factor común mayor que $1$ .

¿Puede darme alguna pista, por favor? No sé cómo empezar. Gracias de antemano.

Answer 1

Una pista:

Hay al menos dos elementos $x$ y $y$ en $S$ tal que $gcd(x,y)>1$ . Sea $B$ sea el conjunto máximo con esta propiedad: $ \forall x,y \in B, gcd(x,y)>1 $ . Supongamos que $B=\{x_1,x_2,...,x_k\}$ .

Ahora para $1\leq i\leq k$ definir $ A_i:=\{x\in S | gcd(x,x_i)=1\} $ .

Primero demuestre que para cada i, $ |A_i|<49 $ (Utilice el hecho de que para cada $a$ , $b$ y $c$ en $S$ , si $gcd(a,b)=1$ y $gcd(a,c)=1$ entonces $gcd(b,c)=1$ ), entonces observe que $B$ es máxima y demostrar que $ S=(\bigcup_{i=1}^{k}A_k )\cup B $ .

Ahora bien, si $k<40$ podemos concluir que $ |S|<40*49+40=2000 $ una contradicción.