- Mostre que para qualquer conjunto de 13 números escolhidos no intervalo [2, 40], existem pelo menos dois inteiros com um divisor comum maior que 1.
Passo 1
O enunciado pede para mostrar que, se tomarmos qualquer conjunto de 13 números do intervalo
, obrigatoriamente existem dois desses números cujo máximo divisor comum é maior que 1. O conteúdo usado aqui é o Princípio da Casa dos Pombos (pigeonhole principle) combinado com a fatoração em números primos.
Passo 2
Observe que os números primos menores ou iguais a 40 são exatamente doze:
Qualquer inteiro
no intervalo
é divisível por pelo menos um desses primos, pois em sua fatoração primo‐potência aparece algum elemento de
.
Passo 3
Vamos classificar cada número escolhido em
segundo um de seus divisores primos em
. Mais precisamente, para cada número
escolhemos arbitrariamente um primo
que divide
e colocamos
na “caixa” correspondente a
. Assim temos 12 caixas (uma para cada primo).
Passo 4
Pelo Princípio da Casa dos Pombos, se colocamos 13 números em apenas 12 caixas, em pelo menos uma caixa haverá dois números distintos, digamos
e
. Por construção, ambos são divisíveis pelo mesmo primo
. Logo
Resposta
Fica provado que em qualquer escolha de 13 números no intervalo
existem dois cujo divisor comum é maior que 1.