¿Existe un algoritmo más simple para encontrar el número de dígitos que ocurren antes de repetir en la serie de congruencia 1 / N (base 10)?

Answer 1

Sea [math] n = 2 ^ {\ alpha} \ cdot 5 ^ {\ beta} \ cdot m [/ math], donde [math] \ gcd (m, 10) = 1 [/ math]. Deje [math] \ gamma = \ max \ {\ alpha, \ beta \} [/ math]. Entonces la expansión decimal de [math] \ frac {1} {n} [/ math] tiene la forma

[matemáticas] 0.a_1 \ ldots a _ {\ gamma} \ overline {a _ {\ gamma + 1} \ ldots a _ {\ gamma + \ ell}} [/ math].

Por lo tanto, la expansión decimal consta de al menos una de dos partes: una parte finita, no recurrente , y una parte recurrente . Es posible que solo uno de estos aparezca en una expansión decimal, o ambos . Por ejemplo, [math] \ frac {1} {2} = 0.5 [/ math] tiene solo la parte finita, no recurrente, [math] \ frac {1} {3} = 0. \ overline {3} [ / math] solo la parte recurrente, y [math] \ frac {1} {6} = 0. 1 \ overline {6} [/ math] ambas partes.

• La parte no recurrente aparece si y solo si [math] \ gamma \ ne 0 [/ math]. En otras palabras, precisamente cuando al menos uno de [matemática] 2 [/ matemática], [matemática] 5 [/ matemática] divide [matemática] n [/ matemática]. El número de dígitos en esta parte es [math] \ gamma [/ math]. Por lo tanto, el número de dígitos en la parte no recurrente es siempre [matemática] \ gamma [/ matemática], ya sea que [matemática] \ gamma [/ matemática] sea [matemática] 0 [/ matemática].
• La parte recurrente aparece si y solo si [matemática] m> 1 [/ matemática]. La longitud [math] \ ell [/ math] de esta parte (el número de dígitos que se repiten) es el entero positivo más pequeño [math] k [/ math] para el cual [math] m \ mid (10 ^ k- 1) [/ matemáticas]. Por lo tanto, [math] \ ell \ mid \ phi (m) [/ math], pero nada más se puede decir sobre [math] \ ell [/ math] en general.
• La expansión decimal es finita si y solo si [matemática] m = 1 [/ matemática], es decir, cuando [matemática] n = 2 ^ {\ alpha} \ cdot 5 ^ {\ beta} [/ matemática]. Como [math] \ dfrac {1} {n} = \ dfrac {2 ^ {\ alpha- \ gamma} \ cdot 5 ^ {\ beta- \ gamma}} {10 ^ {\ gamma}} [/ math], el numerador es [matemática] 1 [/ matemática] o una potencia de [matemática] 2 [/ matemática] o una potencia de [matemática] 5 [/ matemática]. Por lo tanto, hay dígitos [matemáticos] \ gamma [/ matemáticos] después del decimal.
• La expansión decimal es puramente recurrente (no tiene una parte no recurrente) si y solo si [math] \ gamma = 0 [/ math].

Permítanme tomar tres ejemplos para aclarar estos puntos .

• [math] \ dfrac {1} {2 ^ 2 \ cdot 5 ^ 3} = \ dfrac {2} {10 ^ 3} = 0.002 [/ math] tiene [math] \ gamma = \ max \ {2,3 \ } [/ math] dígitos después del decimal. No hay parte recurrente desde [matemáticas] m = 1 [/ matemáticas].
• [math] \ dfrac {1} {7} = 0. \ overline {142857} [/ math] tiene [math] \ ell = 6 [/ math] dígitos que son recurrentes. Tenga en cuenta que [matemáticas] 7 \ mid (10 ^ 6–1) [/ matemáticas] y [matemáticas] 7 \ nmid (10 ^ k-1) [/ matemáticas] para [matemáticas] 1 \ le k <6 [/ matemáticas]. Tenga en cuenta también que [matemáticas] 10 ^ 6–1 = 7 \ cdot 142857 [/ matemáticas].
• [math] \ dfrac {1} {2 ^ 2 \ cdot 5 ^ 3 \ cdot 7} = \ dfrac {2} {7 \ cdot 10 ^ 3} = 0.000 \ overline {285714} [/ math] tiene [math] \ gamma = 3 [/ math] y [math] \ ell = 6 [/ math].

Hay mucho más que decir sobre las expansiones decimales, incluidas las pruebas de lo que incluí aquí y un método alternativo para calcular la expansión decimal de cualquier número racional escribiendo los dígitos de derecha a izquierda (en orden inverso a lo normal). Mi artículo reciente en la edición de abril de 2017 de Mathematics Magazine discute este aspecto computacional .

Answer 2

Cada número entero positivo [math] n [/ math] puede escribirse como [math] n = n_O \ cdot2 ^ a \ cdot5 ^ b [/ math], con [math] \ def \ gcd {\ operatorname {gcd}} \ gcd (n_O, 10) = 1 [/ matemática].

Tomemos la función [math] \ varphi [/ math] de Euler. [math] \ varphi (n) [/ math] es el número de parientes principales de [math] n [/ math] entre [math] 0 [/ math] y [math] n [/ math].

Si [math] \ gcd (m, n) = 1 [/ math], entonces se puede demostrar que [math] \ newcommand \ mmod [1] {\; _ {\ text {mod} \; # 1}} m ^ {\ varphi (n)} \ equiv1 \ mmod n [/ math]. Esto también significa que [matemáticas] m ^ {k + \ varphi (n)} \ equiv m ^ k \ mmod m [/ matemáticas].

Deje [math] \ gcm (10, n) = 1 [/ math], luego [math] 10 ^ {\ varphi (n)} \ equiv1 \ mmod n [/ math], lo que significa que [math] n [/ matemáticas] divide [matemáticas] 10 ^ {\ varphi (n)} – 1 [/ matemáticas], esto es, que hay [matemáticas] d [/ matemáticas] tales como:

\ begin {ecation} n \ cdot d = \ underbrace {99 \ ldots9} _ {\ varphi (n) \; 9 \ text s}. \ end {ecation}

Dado que [matemáticas] 1 = \ sum_ {j = 1} ^ \ infty9 \ cdot10 ^ {- j} = \ sum_ {j = 1} ^ \ infty (10 ^ k-1) \ cdot10 ^ {- jk} [ / math], luego [math] 1 = \ sum_ {j = 1} ^ \ infty nd \ cdot10 ^ {- j \ varphi (n)} [/ math], y de esto obtenemos: [math] \ frac1n = \ sum_ {j = 1} ^ \ infty d \ cdot10 ^ {- j \ varphi (n)} [/ math].

En otras palabras, [math] d [/ math], lleno de ceros si es necesario para completar [math] \ varphi (n) [/ math] dígitos, es el período de [math] \ frac1n [/ math].

Ahora, observe que, al hacer esto, el período de [matemáticas] \ frac13 [/ matemáticas] no sería [matemáticas] 3 [/ matemáticas] sino [matemáticas] 33 [/ matemáticas], y el período de [matemáticas] \ frac1 {11} [/ math] sería [math] 0909090909 [/ math]. Entonces, el período más corto real de [math] \ frac1n [/ math] podría ser un divisor de [math] \ varphi (n) [/ math].

Si [math] n [/ math] es par o divisible por cinco, entonces usaríamos [math] \ varphi (n_O) [/ math] el mayor factor de [math] n [/ math] como [math] \ gcd (10, n_O) = 1 [/ matemáticas].

Ahora. ¿Cómo podemos encontrar [math] \ varphi (n) [/ math]?

Primero [math] \ varphi (p) = p-1 [/ math] para cualquier número primo [math] p [/ math]. Por definición del número primo, todos los enteros menores son primos relativos.

Entonces, podemos demostrar que [math] \ varphi (p ^ {n + 1}) = p ^ n (p-1) [/ math] si [math] p [/ math] es primo. Y que si [math] \ gcd (m, n) = 0 [/ math], entonces [math] \ varphi (m \ cdot n) = \ varphi (m) \ cdot \ varphi (n) [/ math].

Entonces, hay una manera de predecir un período de [math] \ frac1n [/ math].

No estoy familiarizado con un método para predecir un período más corto.

Answer 3

Doy una respuesta práctica a la pregunta específica.

Si N no se divide entre [matemática] 2 [/ matemática] y [matemática] 5 [/ matemática], entonces el número de dígitos decimales repetitivos formados por la fracción [matemática] 1 / N [/ matemática] será el número más pequeño [matemática ] l [/ math] para el cual

[matemáticas] 10 ^ l \ bmod N = 1 \ text {} (0 \ lt l \ lt N) [/ matemáticas]

Esto se escribe como [math] 10 ^ l \ equiv 1 [/ math], ya que trabajamos en [math] \ bmod N [/ math].

Calculamos [math] l [/ math] con el siguiente procedimiento iterativo.

[matemáticas] m_0 = 1 [/ matemáticas]

[matemáticas] m_k \ equiv 10m_ {k – 1} [/ matemáticas]

Cuando para algún valor [matemática] k [/ matemática] es [matemática] m_k = 1 [/ matemática], entonces será [matemática] l = k [/ matemática].

Ejemplo con [matemáticas] N = 13 [/ matemáticas]

[matemáticas] m_0 = 1 [/ matemáticas]

[matemáticas] m_1 \ equiv 10 \ cdot 1 \ equiv 10 [/ matemáticas]

[matemáticas] m_2 \ equiv 10 \ cdot 10 \ equiv 9 [/ matemáticas]

[matemáticas] m_3 \ equiv 10 \ cdot 9 \ equiv 12 [/ matemáticas]

[matemáticas] m_4 \ equiv 10 \ cdot 12 \ equiv 3 [/ matemáticas]

[matemáticas] m_5 \ equiv 10 \ cdot 3 \ equiv 4 [/ matemáticas]

[matemáticas] m_6 \ equiv 10 \ cdot 4 \ equiv 1 [/ matemáticas]

Entonces [matemáticas] l = 6 [/ matemáticas], es decir [matemáticas] 1/13 = 0. \ bar {076923} [/ matemáticas]

Nota: [math] a \ bmod b = a – b \ text {int} (a / b) [/ math].

Answer 4

No existe un algoritmo más simple para encontrar el número de dígitos que ocurren antes de repetir en la serie de congurencias 1 / N, ya que hay varias razones detrás de esto.