¿Por qué no puede la fracción decimal de la parte de $\frac{1}{d}$, $d \in \mathbb{N}^\ast$ tienen un ciclo recurrente de longitud mayor que $d$?

Question

Estoy tratando de resolver el problema de 26 de proyecto de euler que se pide Encontrar el valor de $d < 1000$ que $1/d$ contiene el más largo ciclo recurrente en su fracción decimal parte.

Me di cuenta de que todas las duraciones del ciclo son más pequeños de lo $d$ (al menos para los números de $d < 1'000'000$), y me preguntaba por qué esto parece ser cierto. Hay una razón profunda para esto, o esto es algo trivial no estoy viendo?

Answer 1

Porque no hay máximo de $d-1$ posibles restos al dividir $1 \cdot 10, 2 \cdot 10 , ... (d-1) \cdot 10$ $d$ y, finalmente, en el proceso de división de dividir algunos de estos números con $d$ nuevo y, a continuación, todas las repeticiones.

Answer 2

A ver como está familiarizado con el largo algoritmo de la división, me voy a dar una razón basada en que (al menos de la manera que yo espero que usted está acostumbrado a hacerlo, algo similar a la de este video, solo que seguir adelante, después del punto decimal). Durante el largo algoritmo de la división, después de haber "tirado hacia abajo", todos los no-cero dígitos, y empezar a tirar hacia abajo ceros, tenga en cuenta que cualquier resto que se obtiene (el resultado de la "sustracción" de parte, antes de que te tire hacia abajo de la próxima $0$) totalmente dictan cómo todo el resto de las divisiones ir. Para esta discusión, voy a asumir que usted ha llegado a este punto de la división larga ya (como el periódico de la naturaleza no aparecerá hasta que usted comience a tirar abajo sólo $0$'s).

Por ejemplo, supongamos que usted está calculando el $10\div7$, ha llegado a la respuesta $1.4$, y un ramainder de $2$. Tire hacia abajo de una $0$, consigue $20$, escribir un $2$ en la respuesta, restar $20-14 = 6$. Así que si un resto es $2$, el siguiente dígito en la respuesta será siempre ser $2$, y la próxima resto será siempre ser $6$.

Continuando, vemos que en cualquier momento el resto es $6$, el siguiente dígito de la respuesta va a ser $8$ y el resto se $4$. Y en cualquier momento el resto es $4$... supongo que usted puede ver cómo continúa. Siempre que llegamos a un resto hemos tenido antes, el patrón empezará a repetirse.

Ya que nunca obtener un resto de $0$ (ya que significaría la división no da una infinita expansión), y usted nunca conseguirá un resto igual a o mayor que $7$ (siempre y cuando haga cosas corerctly), sólo hay $6$ posibles restos. Lo que significa que el patrón de repetición de los restos, y por lo tanto el patrón de repetición de los decimales en la respuesta, puede en la mayoría de los ser $6$ largo.

Esta discusión, por supuesto, el trabajo de algún otro número de $7$. Nota, sin embargo, que esto no prueba que la expansión será siempre ser $d-1$ largo. Sólo que $d-1$ es el más largo que posiblemente puede obtener.

Por ejemplo, con $d = 9$, el resto no cambia nunca (al menos en base diez). Si el cálculo de $10\div 9$, y ha llegado a $1.1$ con un resto de $1$, tire hacia abajo de una $0$, obtener el siguiente dígito $1$, y un resto de $1$ nuevo. El patrón justo repite inmediatamente.