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
números dentre os números naturais de
até
. Ou seja, há um subconjunto
do conjunto
com
.
A pergunta é: provar que existem dois elementos distintos tais que
(isto é, que são primos entre si).
A pergunta é: provar que existem dois elementos distintos
Passo 2
Vamos organizar os
números em
pares disjuntos de números consecutivos. Escrevemos os pares
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
. - Portanto temos exatamente
pares que cobrem todos os números.
Passo 3
Apresento agora o Princípio da Casa dos Pombos (pigeonhole principle) numa forma simples que usarei: se se colocam
objetos em
caixas e
, então alguma caixa contém pelo menos dois objetos.
No nosso caso:
No nosso caso:
- as “caixas” serão os
pares construídos no passo anterior; - os “objetos” serão os
números escolhidos (os elementos de ).
Como, o princípio garante que existe pelo menos uma das 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
para algum
. Agora provamos que dois inteiros consecutivos são primos entre si. Prova curta:
suponha que é um divisor comum de
e
. Então
divide a diferença
suponha que
Logo
divide
, o que implica
. Portanto o maior divisor comum de
e
é
, isto é,
. Assim quaisquer dois elementos de um mesmo par de números consecutivos são coprimos.
Passo 5
Juntando os passos: ao escolher
números entre
e
obrigatoriamente existe um par do tipo
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
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.