Escolhendo-se 51 números dentre os números naturais de 1 até 100 , prove que existem ao menos 2 que devem ser primos entre si.

Passo 1

O enunciado dá que se escolhem 51 números dentre os números naturais de 1 até 100. Ou seja, há um subconjunto A do conjunto
\{1,2,\dots,100\}
com |A|=51.
A pergunta é: provar que existem dois elementos distintos x,y\in A tais que \gcd(x,y)=1 (isto é, que são primos entre si).

Passo 2

Vamos organizar os 100 números em 50 pares disjuntos de números consecutivos. Escrevemos os pares
(1,2),\\ (3,4),\\ (5,6),\\ \dots,\\ (99,100).
Observações importantes sobre esses pares:
  • Eles são disjuntos (não têm elemento em comum).
  • A união de todos os pares é exatamente o conjunto \{1,2,\dots,100\}.
  • Portanto temos exatamente 50 pares que cobrem todos os 100 números.

Passo 3

Apresento agora o Princípio da Casa dos Pombos (pigeonhole principle) numa forma simples que usarei: se se colocam n objetos em m caixas e n>m, então alguma caixa contém pelo menos dois objetos.
No nosso caso:
  • as “caixas” serão os 50 pares construídos no passo anterior;
  • os “objetos” serão os 51 números escolhidos (os elementos de A).
    Como 51>50, o princípio garante que existe pelo menos uma das 50 caixas (um par) que contém pelo menos dois dos elementos escolhidos. Mas cada caixa contém no máximo dois elementos (pois é um par), logo existe um par cujo os dois elementos foram escolhidos.

Passo 4

O par identificado no passo anterior é um par de inteiros consecutivos, isto é, tem a forma (n,n+1) para algum n. Agora provamos que dois inteiros consecutivos são primos entre si. Prova curta:
suponha que d é um divisor comum de n e n+1. Então d divide a diferença
(n+1)-n=1.
Logo d divide 1, o que implica d=1. Portanto o maior divisor comum de n e n+1 é 1, isto é, \gcd(n,n+1)=1. Assim quaisquer dois elementos de um mesmo par de números consecutivos são coprimos.

Passo 5

Juntando os passos: ao escolher 51 números entre 1 e 100 obrigatoriamente existe um par do tipo (n,n+1) cujos dois elementos foram escolhidos (pigeonhole). Esses dois elementos são consecutivos, e portanto, pelo argumento do passo anterior, são primos entre si. Assim a escolha de 51 números sempre contém pelo menos dois números coprimos.

Resposta

Existem pelo menos dois números escolhidos que são primos entre si.

Exercícios relacionados