La solución se basa en dos hechos que por separado son casi triviales: si se escogen n + 1 enteros menores o iguales que 2n resulta que al menos dos de ellos deben ser consecutivos. Por otra parte, dos enteros consecutivos siempre son primos entre sí.

1. Dos números consecutivos son siempre primos entre sí.

• Sean m y m+1 dos números naturales consecutivos.
• Supongamos que no son primos entre sí: entonces existe un número \(r\in N,\ r\neq1\), factor común de m y m+1, y dos números a y b N tales que m = r·a; m + 1= r·b.
• Despejando a y b, tenemos que \(a=\dfrac {m}{r}; \ b=\dfrac {m+1}{r}=\dfrac {m}{r}+\dfrac {1}{r}\).
• Se observa que \(b=a+\dfrac {1}{r}\) . Pero como r ≠1 y \(a\in N, \ a+\dfrac{1}{r}\), no es natural, lo que contradice que \(b\in N\).
• Por ello, m y m+ 1 son siempre primos entre sí.

2. Tomando n + 1 números menores o iguales que 2n, al menos dos de ellos se diferencian en una unidad.

• Escogemos la mitad más 1 de los elementos que componen el conjunto, por lo que, en el caso más desfavorable, dos de ellos son consecutivos.