Longitud del período de la expansión decimal de una fracción

Question

Cada número racional (fracción) puede ser escrito como un número decimal periódico. ¿Existe un método o indicio para determinar la longitud del período de una fracción arbitraria? Por ejemplo, $1/3=0.3333...=0.(3)$ tiene un período de longitud 1.

Por ejemplo: ¿cómo determinar la longitud de un período de $119/13$?

Answer 1

Esta respuesta busca explicar por qué funciona la respuesta de Ross Millikan y proporciona más información sobre técnicas para acelerar el proceso de buscar el período:

Consideremos la fracción $\frac17$. La expansión decimal de esto es $$ \frac17 = 0.\overline{142857} $$ para un período de 6. Ahora considera qué sucede cuando lo multiplicamos por $10^6$: $$ 10^6\times\frac17 = 142857.\overline{142857} $$ Restando la fracción original de esto obtenemos $$ (10^6-1)\times\frac17 = 142857 $$ Por lo tanto, tenemos $$ \frac17 = \frac{142857}{10^6-1} $$ Como puedes ver, el denominador es uno menos que una potencia de 10, y la potencia es el período de la expansión decimal. Esto no es casualidad, y funciona para cualquier fracción - si puedes reescribirla en esta forma, el denominador revela el período.

Ahora, reorganicemos la ecuación: $$ 10^6-1 = 142857\times 7 $$ Así que $10^6$ debe ser uno más que un múltiplo de 7 (o, más generalmente, $10^n$ debe ser uno más que un múltiplo de $d$, donde $d$ es el denominador de la fracción y $n$ es el período de la expansión decimal) - de hecho, debe ser la menor potencia de 10 (mayor que 1) que tiene esta propiedad.

Por lo tanto, podemos usar la aritmética modular para buscar el período. Dado que $a\times d\equiv 0 \pmod d$, tenemos que $10^n-1\equiv0 \pmod d$, o $$10^n \equiv 1\pmod d$$ Y por lo tanto solo necesitas buscar el menor $n>0$ que satisface esto.

Por supuesto, hay otros enfoques para obtener el mismo resultado, pero todos son variantes fundamentalmente de la misma idea. Dicho esto, si puedes factorizar $\phi(d)$ - la función totient de Euler del denominador - entonces puedes acelerar el proceso de buscar el menor $n$. Por ejemplo, al verificar 13, tienes $\phi(13)=12$, por lo que $n\in\{1,2,3,4,6,12\}$ (ya que estos son los factores de 12) - esto puede ahorrarte mucho cálculo (especialmente cuando $\phi(d)$ tiene solo unos pocos factores grandes y 2).

Por ejemplo, $\phi(167)=166 = 2\times83$, por lo que $n\in\{1,2,83,166\}$. Por lo tanto, solo necesitamos verificar estos cuatro, y podemos hacerlo de manera bastante eficiente. Obviamente, ni $10$ ni $100=10^2$ son equivalentes a 1 módulo 167, por lo que solo necesitamos verificar realmente 83. Para esto, podemos usar la exponenciación binaria. Nota que $83 = 2^6 + 2^4 + 2^1 + 2^0$. Entonces podemos escribir $$\begin{align} 10^{83} &= 10^{2\times(2^5 + 2^3 + 1)}\times 10\\ &= (10^{2^3\times(2^2+1)}\times 10)^2 \times 10\\ &= ((10^{2^2}\times10)^{2^3}\times 10)^2 \times 10 \end{align}$$ Entonces, trabajando en aritmética modular, podemos continuar $$\begin{align} 10^{83} &\equiv ((10^{2^2}\times10)^{2^3}\times 10)^2 \times 10 \mod 167\\ &\equiv ((100^2\times 10)^{2^3}\times 10)^2\times10\mod167\\ &\equiv ((147\times 10)^{2^3}\times 10)^2\times10\mod167\\ &\equiv (134^{2^3}\times 10)^2\times10\mod167\\ &\equiv (87^{2^2}\times 10)^2\times10\mod167\\ &\equiv (54^2\times 10)^2\times10\mod167\\ &\equiv (77\times 10)^2\times10\mod167\\ &\equiv 102^2\times10\mod167\\ &\equiv 50\times10\mod167\\ &\equiv 166\mod167 \end{align}$$ Esto es lo mismo que $-1\pmod{167}$, por lo que $n=166$ es el único período posible, y $\frac1{167}$ tiene un período de 166.

También nota que en realidad no necesitas expandir el producto de esa manera. Simplemente puedes escribir el número en binario ($83_{10} = 1010011_2$), luego trabajar a través de los dígitos binarios de izquierda a derecha - comienza con 1, y para cada dígito, $b$, multiplica por $10^b$. Eleva al cuadrado después de cada dígito excepto el último.

Answer 2

Suponiendo que no hay factores de $2,5$ en el denominador, una forma es simplemente elevar $10$ a potencias módulo el denominador. Si encuentras un $-1$ ya has recorrido la mitad del camino. Tomando tu ejemplo: $10^2\equiv 9, 10^3\equiv -1, 10^6 \equiv 1 \pmod {13}$ entonces la repetición de $\frac 1{13}$ tiene una longitud de $6$. Siempre será un factor de la función totiente de Euler del denominador. Para el primo $p$, eso es $p-1$.

Answer 3

La longitud del período está dada por el orden multiplicativo de $10 \pmod q$, donde $q$ es tu cociente. Está estrechamente relacionado con el logaritmo discreto. Wikipedia enumera varios algoritmos que son más rápidos que recorrer todas las potencias de diez, lo cual es relevante si estás tratando con números muy grandes (cientos de dígitos).

Answer 4

Primero debes simplificar al denominador entero más bajo.

Luego, la prueba de finitud de la parte repetitiva de la representación decimal implica el principio del palomar. Cuando sigues dividiendo, en algún momento encontrarás un valor repetido para el resto. Dado que los restos que mantienen la operación en curso van desde 1 hasta (denominador-1), el número posible de palomares es (denominador-1) como el número de palomares; así que ese es tu peor escenario posible - en cualquier base.

Los casos particulares, como se describen en las otras respuestas, dependen de la base, porque el denominador puede tener una relación especial con la base.

• por ejemplo, en base 10 las fracciones sobre 3 tendrán un decimal repetitivo, (3) o (6), ya que 3 divide a 9(=10-1) y el resto seguirá repitiéndose.