Mostre que se um subconjunto com
elementos é escolhido do conjunto
,
então este subconjunto necessariamente contém um par de números primos entre si.
Solução:
Sabemos que dois inteiros consecutivos são primos entre si.
Solução:
Sabemos que dois inteiros consecutivos são primos entre si.
Passo 1
O enunciado considera o conjunto
e afirma que, ao escolhermos qualquer subconjunto com
elementos desse conjunto, sempre haverá dois números que são primos entre si. Para resolver isso, vamos usar o Princípio da Casa dos Pombos e a propriedade de que dois inteiros consecutivos são coprimos.
Passo 2
Particionamos os
inteiros em
pares de números consecutivos, cada um coprimo internamente:
Em cada par, os dois números são coprimos porque inteiros consecutivos não têm divisor comum além de
.
Passo 3
Aplicamos o Princípio da Casa dos Pombos: temos
“caixas” (os pares) e escolhemos
“pombos” (os elementos do subconjunto). Logo, ao distribuir
elementos em
pares, pelo menos em um dos pares ambos os elementos escolhidos devem estar presentes.
Passo 4
Nesse par que contém os dois elementos, eles são consecutivos por construção e, portanto, coprimos (primos entre si). Assim mostramos que qualquer subconjunto de
elementos contém um par de números primos entre si.
Resposta
Qualquer subconjunto com
elementos de
tem dois números consecutivos, logo primos entre si.