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 5 números compostos menores que 100, existe ao menos um par que não é primo entre si (isto é, cujo máximo divisor comum é maior que 1). 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 n<100 tem pelo menos um fator primo menor ou igual a 7. De fato, o menor primo maior que 7 é 11 e
11^2 = 121 > 100
Logo, se n fosse produto apenas de primos maiores ou iguais a 11, teríamos n>=11^2=121, o que contradiz n<100. Portanto, qualquer composto menor que 100 é divisível por algum primo em 2,3,5,7.

Passo 3

Agora, associe cada um dos 5 números compostos a um dos primos 2,3,5,7 que o divide. Temos 4 categorias (os primos 2, 3, 5 e 7) e 5 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 pin2,3,5,7. Então
gcd(esses dois números) ;>=; p ;>;1, ú
logo eles não são primos entre si.

Resposta

Concluímos que em qualquer escolha de 5 números compostos menores que 100 existem sempre ao menos dois que não são primos entre si.

Exercícios de Livros Relacionados