Mostre que todo inteiro positivo n tem um múltiplo que se escreve apenas com os algarismos 0 e 1 .
Passo 1
O enunciado pede para mostrar que, dado qualquer inteiro positivo n, existe um múltiplo de n cuja representação decimal contenha somente os dígitos 0 e 1. O conteúdo principal é teoria de restos módulo n e o princípio da casa dos pombos (princípio de Dirichlet) para encontrar dois números com o mesmo resto.
Considere os n+1 números A_1,A_2,\dots,A_{n+1} e seus restos ao dividir por n. Como há somente n possíveis restos (de 0 a n-1), o princípio da casa dos pombos garante duas coisas:
ou algum A_k já é múltiplo de n, isto é, A_k \equiv 0 \pmod n;
ou existem índices 1 \le i < j \le n+1 tais que
A_i \equiv A_j \pmod n.
Passo 4
Se algum A_k satisfaz A_k \equiv 0\pmod n, então já encontramos um múltiplo de n escrito só com dígitos 1 e terminamos.
Caso contrário, escolhamos i<j com A_i\equiv A_j\pmod n. Então