Considere
como um número inteiro positivo. Mostre que entre um grupo de
números inteiros (não necessariamente consecutivos) há dois com exatamente o mesmo resto quando divididos por
.
Passo 1
O enunciado pede para mostrar que, dado um inteiro positivo
e quaisquer
números inteiros, sempre podemos encontrar dois deles que deixam o mesmo resto na divisão por
. O conteúdo principal aqui é o Princípio da Casa dos Pombos (pigeonhole principle).
Passo 2
Seja
o conjunto dos
inteiros. Para cada
definimos o seu resto na divisão por
: existe único
tal que
Passo 3
Note que há exatamente
valores possíveis de resto:
. Mas estamos atribuindo a estes
“caixas” de restos um total de
números
.
Passo 4
Pelo Princípio da Casa dos Pombos, se temos mais “pombos” (
números) do que “caixas” (
restos), então pelo menos duas vezes um mesmo resto deve ocorrer. Isto é, existem índices
tais que
Logo
ou seja,
e
deixam exatamente o mesmo resto na divisão por
.
Resposta
Entre quaisquer
inteiros existem sempre dois que têm o mesmo resto na divisão por
.