Mostre que em todo subconjunto de
elementos há um par de elementos primos entre si neste subconjunto. Dica:Não tente usar a dica do exercício anterior.
Passo 1
O enunciado pede para mostrar que qualquer subconjunto
com
sempre contém dois elementos coprimos. Vamos usar o princípio da casa dos pombos: se tivermos mais “pombos” (elementos de
) do que “casas” (grupos em que particionamos
), alguma casa terá pelo menos dois pombos.
Passo 2
Particionamos
em
pares
Cada
é uma “casa” do princípio da casa dos pombos.
Passo 3
Como
tem
elementos e há somente
pares
, pelo princípio da casa dos pombos
deve conter pelo menos dois elementos de um mesmo par
. Ou seja, existem
tais que
Passo 4
Para qualquer
, temos
já que números consecutivos são sempre coprimos. Logo, em
encontramos um par de elementos cujo máximo divisor comum é
.
Resposta
Qualquer subconjunto de
com
elementos contém um par de elementos coprimos.