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.

Passo 2

Definimos, para cada k\ge1, o número
A_k = \underbrace{11\ldots1}_{k\text{ vezes}}
ou seja, em fórmula
A_k = 1 + 10 + 10^2 + \cdots + 10^{k-1} = \frac{10^k - 1}{9}.
Note que cada A_k tem exatamente k dígitos “1”.

Passo 3

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:
  1. ou algum A_k já é múltiplo de n, isto é, A_k \equiv 0 \pmod n;
  2. 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
B = A_j - A_i
é também divisível por n, pois
A_j - A_i \equiv 0 \pmod n.

Passo 5

Observe que
A_j - A_i = \underbrace{11\ldots1}_{j \text{ vezes}} - \underbrace{11\ldots1}_{i \text{ vezes}} = \underbrace{11\ldots1}_{(j-i)\text{ vezes}}\times 10^{\,i}.
Em decimal, isso é um número com j-i dígitos “1” seguido de i dígitos “0”. Logo, B é um múltiplo de n cuja escrita contém apenas os dígitos 0 e 1.

Resposta

Fica então demonstrado que, para todo inteiro positivo n, existe um múltiplo de n composto somente pelos dígitos 0 e 1.

Exercícios relacionados