Existencia de múltiplos de$n$ con solo 0 y 1 como sus dígitos

Question

Posibles Duplicados:
La prueba de que un número natural que multiplicado por un número entero de los resultados en un número con sólo uno y el cero como dígitos

He leído esto en algún lugar recientemente:

Para cualquier número natural $n$, existe un múltiplo de $n$, de tal manera que las múltiples tiene sólo 0 y 1 como de sus dedos.

$2 \to 10$

$3 \to 111$

$4 \to 100$

$5 \to 10$

$6 \to 1110$

$7 \to 1001$

Alguna idea de cómo ir sobre el probar esto?

Answer 1

Considere los números$a_1=1$,$a_2=11$,$a_3=111$, y así sucesivamente. Deje que$r_1, r_2,r_3,$ y así sucesivamente sean los residuos cuando los$a_i$ están divididos por$n$.

Hay a lo sumo$n$ concebible tales residuos. Por lo tanto, debe haber dos números$a_i$,$a_j$ tales que$i\lt j$ y$r_i=r_j$. Su diferencia$a_j-a_i$ es divisible por$n$, y solo tiene$0$ 's y / o$1$' s. Además, todos los$1$ 's preceden a todos los$0$' s.

Answer 2

Considerar el número 1,11,111,...,111...11, apartado 1, se repite n+1 veces). Ya que estos son n+1 números podemos utilizar el pegionhole principio deducir que 2 de ellos son congruentes $modulo$ $n$. Encontrar el valor absoluto de la diferencia entre los 2 números que son congruentes módulo n. La diferencia se compone de 1(s) y ceros. Este número también es divisible por n. (hecho)

En general, si n es indivisible por 2 y 5, existe un múltiplo de n que está escrito, como se repite secuencias de dígitos. Por ejemplo n tiene un múltiplo que es en la forma 249249249...249 La prueba es muy similar a la anterior argumento