Un número natural que multiplicado por un número entero de los resultados en un número con sólo unos y ceros

Question

Recientemente he resuelto un problema, que dice que,

Un entero positivo puede ser multiplicado por otro número entero resultante en un entero positivo que está compuesto solamente de uno y cero como dígitos.

¿Cómo puedo demostrar que esto es cierto(actualmente supongo que lo es). También, es posible establecer un límite superior de la longitud(número de dígitos) del número generado?

Answer 1

Aquí es una solución alternativa, que se basa en la Paloma principio:

Lista de todos los números 1, 11, 111, ... , 111...1 donde la última contiene $n+1$.

Mire ahora sus restos cuando se divide por $n$. Por la paloma principio, dos de ellos tienen el mismo resto. Pero entonces su diferencia es de la forma $1111..100000..0$ y es divisible por $n$..

Answer 2

No sólo es posible encontrar un múltiplo de $n$, cuya expansión decimal consiste únicamente $0$s y $1$s, es posible organizar toda la $1$s a venir antes de que todo el $0$s.

Supongamos primero que a $n$ es coprime $10$. Entonces por Fermat–Euler, $10^{\varphi (9n)} \equiv 1 \pmod{9n}$. Mus $(10^{\varphi (9n)} -1)/9 \equiv 0 \pmod{n}$, y por tanto no es un múltiplo de $n$, que consiste únicamente de $1$s, es decir, $(10^{\varphi (9n)} -1)/9$.

Ahora veamos el caso contrario de que $n=2^5^b$ natural $a, b$. A continuación, algunos de los múltiples de $$ n es una potencia de 10$$: $2^{b-a}n$ o $5^{a-b}n$, dependiendo de si $a$ o $b$ es mayor.

Por tanto, para general $n$, podemos expresar $n$ $2^5^b m$, donde $m$ es coprime $10$. Entonces podemos encontrar un múltiplo de $m$, que es una cadena de $1$s y un múltiplo de $2^5^b$, que es una potencia de 10$$, y por lo tanto un múltiplo de $n$, que es una cadena de $1$s seguido por una cadena de de $0$s. En concreto, hay $\varphi (9m)$ $1$s y $\max(a,b)$ $0$, entonces $\varphi (9m)+\max(a,b)$ da un límite superior en el número de dígitos necesarios.