|
Tome um número natural "n" qualquer.
Considere os números 1, 11, 111, 1111, 11111,
.... e 111..11 (onde o último número é formado por (n+1) algarismos 1, e os
restos que cada um destes números deixa quando dividido por n.
Existem n+1 números mas apenas n restos possíveis
(0, 1, ..., n-1). Assim, pelo princípio de Dirichlet, têm de existir na lista
acima dois números formados só por algarismos ´1´ que deixam o mesmo resto
(suponhamos que o maior seja formado por "p" e o menor por "q" algarismos
´1´ ( p > q) ).
Subtraindo o menor do maior, você obtém um número
da forma 11...1100..00, formado por "(p-q)" 1´s seguido de "q" zeros, o qual é
divisível por "n" (estou usando o fato de que se "a" e "b" deixam o mesmo resto
na divisão por "n" então "a-b" é divi´sível por "n".
|