¿Por qué la suma de $n$ parece es igual al período de los binarios de expansión de $1/n$?

Question

La suma de $n$(supongamos $n$ es positivo impar,el uso de $n=23$ como un ejemplo):

Paso 1 : Obtener el impar parte de $23 + ~~1$, que es $~~3$,$~~3\times2^3=23 + ~~ 1$,consigue $s_1 = 3$
Paso 2 : Obtener el impar parte de $23 + ~~3$, que es $13$,$13\times2^1=23 + ~~ 3$,consigue $s_2 = 1$
Paso 3 : Obtener el impar parte de $23 + 13$, que es $~~9$,$~~9\times2^2=23 + 13$,consigue $s_3 = 2$
Paso 4 : Obtener el impar parte de $23 + ~~9$, que es $~~1$,$~~1\times2^5=23 + ~~9$,consigue $s_4 = 5$

De continuar esta operación (con $23 + 1$) repite los mismos pasos anteriores. Hay $4$ pasos en el ciclo, por lo que la longitud del ciclo de la $23$$4$, y la suma de $23$$s_1 + s_2 + s_3 + s_4 = 11$.

El período de los binarios de expansión de $1/23$$11$, así que ¿por qué la suma de $23$ parece es igual al período de los binarios de expansión de $1/23$?

Answer 1

Considerar la secuencia de $a_i = 2^{-i} \pmod{23}$ $$\begin{array}{l} a_0 = 1,~a_1=12,~a_2=6 \\ a_3 = 3 \\ a_4 = 13, ~ a_5=18, \\ a_6=9, ~ a_7 = 16, a_8=8, a_9=4, a_{10}=2 \\ a_{11} = 1 = a_0 \end{array}$$ Sus pasos de "obtener el curioso" son precisamente encontrar el siguiente número impar en esta secuencia, su $s_i$ están contando todos los pasos, y la suma de $\sum s_i$ es del orden de 2 modulo 23.

Deje $n=\operatorname{ord}_p 2$ ser del orden de 2 modulo de un primer $p$ $m$ el período de los binarios de expansión de $1/p$. Entonces, para algún entero positivo $k$ $$2^n = pk+1 \\ 2^n\frac{1}{p} = k + \frac{1}{p}$$ Es decir, la representación binaria de $1/p$ repite después de $n$ bits, por lo $n\mid m$. Del mismo modo, para algún entero positivo $j$ $$2^m \frac{1}{p} = j + \frac{1}{p} \\ 2^m = jp + 1$$ así también se $m\mid n$ y, por tanto,$n=m$.

Answer 2

Hmm... no veo donde esta viene de la parte superior de mi cabeza, o exactamente cómo demostrarlo, pero esto es algo que, al menos, a mitad de camino de una prueba. Tenemos una secuencia de

$$n + 1 = 2^{s_1} t_1$$

$$n + t_1 = 2^{s_2} t_2$$

$$\vdots$$

$$n + t_{\ell - 1} = 2^{s_\ell} t_\ell$$

donde $t_0 = t_\ell = 1$. Multiplicando juntos estas ecuaciones, vemos que

$$\prod_{i = 0}^{\ell-1} (n + t_i) = 2^{s_1 + \cdots + s_\ell} t_1 \cdots t_\ell.$$

Ampliar la LHS, en términos de primaria simétrica polinomios:

$$\sum_{j = 0}^{\ell} n^{\ell - j} S_j(t_1, \ldots, t_\ell) = 2^{s_1 + \cdots + s_\ell} t_1 \cdots t_\ell$$

Darse cuenta de que $S_\ell(t_1, \ldots, t_\ell) = t_1 \cdots t_\ell$, restar ese término de cada lado:

$$\sum_{j = 0}^{\ell-1} n^{\ell - j} S_j(t_1, \ldots, t_\ell) = \left(2^{s_1 + \cdots + s_\ell}-1\right) t_1 \cdots t_\ell$$

Saque un factor de $n$ de la izquierda:

$$n \sum_{j = 0}^{\ell-1} n^{\ell - j - 1} S_j(t_1, \ldots, t_\ell) = \left(2^{s_1 + \cdots + s_\ell}-1\right) t_1 \cdots t_\ell$$

Tenga en cuenta que si $n$ es primo (como en tu ejemplo), entonces el $t_i$ son relativamente primos a $n$; desde $n$ divide el lado izquierdo, se debe dividir el lado derecho, y desde $n$ es primo relativo a la $t_i$, se debe dividir $2^{s_1 + \cdots + s_\ell} - 1$, que dice que el período de los binarios de expansión divide $s_1 + \cdots + s_\ell$.

Este no es probablemente la mejor manera de acercarse a este, pero pensé que me gustaría seguir adelante y escribir que en caso de que ayuda.

Answer 3

Algo más general es cierto.

Deje $b\geq 2$ e e $n$ cualquier entero positivo coprime con $b$. Definir la secuencia de $s_i$ como sigue:

El primer término $s_1$ se define como el menor no entero negativo tal que $b^{s_1}t_1=n+1$$b\not\mid t_2$.
El segundo término $s_2$ como el más pequeño no entero negativo tal que $b^{s_2}t_2=n+t_1$$b\not\mid t_2$.
El tercer término $s_3$ como el más pequeño no entero negativo tal que $b^{s_3}t_3=n+t_2$$b\not\mid t_3$.
$\hspace{38 ex} \vdots$
Finalmente, el $d^{th}$ plazo $s_d$ como el más pequeño no entero negativo tal que $b^{s_d}=n+t_{d-1}$.

Que esta secuencia es puramente periódico, se explica aquí. Lo que se observa es que la suma de los $s_i$ es la longitud del ciclo de la $1\over n$ escrito en base a $b$. Pero, que la duración del ciclo de $1\over n$ es el orden de $b\pmod n$ ya que ambos de estos números puede ser descrito como el menor entero positivo $s$ tal que $b^s {1\over n}-{1\over n}\in\mathbb N$.

Por lo tanto, queda por demostrar que $s=s_1+s_2+\ldots+s_d$ es el orden de $b\pmod n$ que es fácil ver que es equivalente a mostrar que la $\operatorname{ord}_n\left(\dfrac1b\right)=s$ o que $b^s=1$ $\dfrac{1}{b^i}\neq1$ todos los $i=1,2,\ldots,s-1$.

Set $t_0=t_{d+1}=1$. La reducción de las ecuaciones $b^{s_i}t_i=n+t_{i-1}\pmod n$, obtenemos $b^{s_i}t_i=t_{i-1}\pmod n$ y, por tanto,$b^s=1\pmod n$. Ahora para la segunda parte de la nota que $$\dfrac1b=b^{s_1-1}t_1\pmod n, \ \dfrac1{b^2}=b^{s_1-2}t_1\pmod n,\ldots,\dfrac1{b^{s_1}}=t_1\pmod n, \\ \dfrac1{b^{s_1+1}}=\dfrac{1}{b}t_1=\dfrac{1}{b}b^{s_2}t_2\pmod n=b^{s_2-1}t_2\pmod n\ldots$$

No es tan difícil mostrar que todos estos valores son diferentes a los de $1\pmod n$. Tienes que hacer algo de trabajo. Puede suceder que algunas de las $s_i$ son cero y por lo tanto, usted tiene que considerar varios casos. El caso de $b=2$ es de curso más fácil ya que por el hecho de que $\gcd(n,t_i)=1, \ \forall i$ (por qué?) de ello se desprende que $s_i\neq0 \ \forall i$.

Por lo tanto,$\operatorname{ord}_n\left(\dfrac1b\right)=\operatorname{ord}_n(b)=s$.