Provar que, dados 5 números compostos menores que 100, existe ao menos dois que não são primos entre si.
Passo 1
O enunciado pede para mostrar que, dados quaisquer
números compostos menores que
, existe ao menos um par que não é primo entre si (isto é, cujo máximo divisor comum é maior que
). Vamos usar fatoração de números compostos e o princípio da casa dos pombos para construir a prova.
Passo 2
Primeiro, note que todo número composto
tem pelo menos um fator primo menor ou igual a
. De fato, o menor primo maior que
é
e
Logo, se
fosse produto apenas de primos maiores ou iguais a
, teríamos
, o que contradiz
. Portanto, qualquer composto menor que
é divisível por algum primo em
.
Passo 3
Agora, associe cada um dos
números compostos a um dos primos
que o divide. Temos
categorias (os primos
,
,
e
) e
objetos (os números). Pelo princípio da casa dos pombos, ao menos duas dessas associações caem na mesma categoria, ou seja, há dois números que compartilham um mesmo primo divisor
. Então
logo eles não são primos entre si.
Resposta
Concluímos que em qualquer escolha de
números compostos menores que
existem sempre ao menos dois que não são primos entre si.