lunes, 6 de junio de 2016
Problema 6 de junio.
Encuentra todos los enteros positivos $n>1$, con la siguiente propiedad: para todo $k$, con $0 \le k <n$, existe un múltiplo de $n$ cuya suma de dígitos deja residuo $k$ cuando es dividido entre $n$.
Suscribirse a:
Comentarios de la entrada (Atom)
2 comentarios:
Si $n$ es múltiplo de 3, entonces para cualquier $N$ múltiplo de $n$, $N$ es múltiplo de 3, y entonces $S(N)$ es múltiplo de 3. En particular no existe un $m$ múltiplo de $n$ tal que $S(m) \equiv 1 \pmod{3}$.
Ahora mostramos que cualquier $n$ que no es múltiplo de 3 cumple. Sea $A$ el conjunto de todos los residuos módulo $n$ que dejan las sumas de los dígitos de los múltiplos de $n$. Notemos que si $r \in A$, entonces $kr \in A$ (trabajamos en $\mathbb{Z}_n$), pues si $N$ es un múltiplo de $n$ tal que $S(N) \equiv r \pmod{n}$, entonces el número que se obtiene colocando $k$ copias de $N$ seguidas tiene suma de dígitos $kS(N) \equiv kr \pmod{n}$. De manera similar, si $r, s \in A$ entonces $r + s \in A$. Se sigue que cualquier combinación lineal de los elementos de $A$ está en $A$. Ahora definimos
$$d = \text{mcd} A = \text{mcd}(a_1, a_2, \dots, a_t)$$
Donde $a_1, a_2, \dots, a_t$ son los elementos de $A$. Si $d = 1$ entonces Bezout garantiza que $A \equiv \mathbb{Z}_n$. Supongamos entonces que $d \neq 1$.
Ahora veamos que $n$ tiene algun múltiplo $N$ de la forma $777\dots 7700 \dots 0$ para alguna cantidad de sietes y ceros (posiblemente sin ceros), por Casillas con los residuos módulo $n$ de la secuencia $7, 77, 777, \dots$. Ahora elegimos un entero $a$ tal que el último 7 del número $10^a N$ está en la misma posición que el primer 7 del número $N$ (ambos números leídos de izquierda a derecha), entonces, observemos que
$$S((10^a + 1)N) = S(10^a N) + S(N) - 9c(10^a N, N) = 2S(N) - 9c(10^a N, N)$$
Donde $c(x, y)$ denota el número de acarreos que se efectuan al sumar $x$ y $y$. Sin embargo, por la manera en que los números fueron construidos, este número de acarreos es igual a 1, y por lo tanto $S((10^a + 1)N) = 2S(N) - 9$. Ya que $(10^a + 1)N$ es un múltiplo de $n$, se sigue que $d \mid 2S(N) - 9$ y por lo tanto $d \mid 9$. Ya que $d \neq 1$, se sigue que $3 \mid d$, y por lo tanto $3$ divide a todos los elementos de $A$. En particular, $3 \mid S(n)$ y por lo tanto, $3 \mid n$, contradicción.
La linea que aparece cortada dice al final $2S(N) - 9c(10^a N, N)$
Publicar un comentario