1. 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 [2,40], 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:
P=\{2,3,5,7,11,13,17,19,23,29,31,37\}.
Qualquer inteiro n no intervalo [2,40] é divisível por pelo menos um desses primos, pois em sua fatoração primo‐potência aparece algum elemento de P.

Passo 3

Vamos classificar cada número escolhido em [2,40] segundo um de seus divisores primos em P. Mais precisamente, para cada número n escolhemos arbitrariamente um primo p\in P que divide n e colocamos n na “caixa” correspondente a p. 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 a e b. Por construção, ambos são divisíveis pelo mesmo primo p. Logo
\gcd(a,b)\ge p>1.

Resposta

Fica provado que em qualquer escolha de 13 números no intervalo [2,40] existem dois cujo divisor comum é maior que 1.

Exercícios relacionados