¿Cómo se relaciona el desplazamiento de la última cifra de un número al frente y la multiplicación con los órdenes multiplicativos?

Question

Parece haber una relación entre órdenes multiplicativos módulo $n$ y un rompecabezas que Presh Talwalkar dio hace unos días en https://www.youtube.com/watch?v=1lHDCAIsyb8

Espero que alguien pueda dar una explicación más rigurosa del patrón que veo.

$\bullet\textbf{ The Puzzle }\bullet$

El enunciado del rompecabezas es el siguiente: "¿Qué número positivo se duplica cuando su última cifra se convierte en la primera?"

Por ejemplo, la solución más pequeña -suponiendo una representación en base 10- es $105263157894736842$ . Lo que significa que $$(2)\cdot105263157894736842 \quad\ \ \ $$ $$||$$ $$210526315789473684$$

Naturalmente, se puede proceder a encontrar soluciones en otras bases. La solución en base 5 es $$(2)\cdot102342_5 \quad\ \ \ $$ $$||$$ $$210234_5$$

$\bullet\textbf{ Multiplicative Order Connection }\bullet$

Las soluciones en base 10 son $18$ dígitos y la solución de base-5 es $6$ dígitos. Escribí un programa para generar la solución más pequeña en todas las bases y luego conté el número de dígitos en cada solución. Esta es la secuencia, empezando por la base 2 $$2,4,3,6,10,12,4,8,18,6,11,20,...$$ $$\uparrow \quad\quad\quad\quad\ \uparrow \quad\quad$$ $$\text{Base-} 5 \quad\quad\quad \text{Base-} 10 \quad\quad$$ Una búsqueda rápida en http://oeis.org/ muestra que estos números son el orden multiplicativo de $$2\ (\text{mod } 2B-1)$$ donde $B$ es la base de representación en la que estamos trabajando. Véase http://oeis.org/A002326

Este acertijo se puede generalizar aún más encontrando números que se triplican en lugar de duplicarse al mover el último dígito hacia adelante. Introduzcamos un factor multiplicador arbitrario: $k$

Así que las soluciones mencionadas anteriormente y el rompecabezas de Talwalkar son un caso particular cuando $k=2$

Para un ejemplo diferente, veamos $k=5$ en la base 7. La solución más pequeña es $$(5) \cdot 1013042156536245_7 \quad\ \ \ $$ $$||$$ $$5101304215653624_7$$

Esta solución es $16$ dígitos de longitud. Como hicimos antes para la base-10, podemos escribir una secuencia del número de dígitos en la solución de cada base empezando por la base-2 $$6,6,9,2,14,16,4,5,42,18,...$$ $$\uparrow\ \ $$ $$\text{Base-}7\ \ $$ Otra búsqueda en http://oeis.org/ muestra rápidamente que estos números son el orden multiplicativo de $$5\ (\text{mod } 5\cdot7-1)\quad\text{or rather}\quad 5 \ (\text{mod }34)$$

$\bullet\textbf{ A Conjecture }\bullet$

El patrón podría estar claro ahora. Después de comprobar otros casos, parece que el número positivo más pequeño en cualquier base $B$ - que es $k$ veces el valor obtenido al desplazar su último dígito hacia delante - tiene un número de dígitos igual al orden multiplicativo de $$k\ (\text{mod } Bk-1)$$ Puedo ver cómo el orden multiplicativo estaría relacionado con este problema. Pero no encuentro una razón exacta para que esta relación sea así. ¿Hay alguna razón intuitiva?

Answer 1

Dada alguna solución en base $B$ - comencemos por asignar la variable $x$ al dígito que se desplaza al frente y se asigna a la variable $y$ al resto del número (Talwalkar lo hizo en su vídeo). Así que si tenemos un factor multiplicador de $k$ buscamos una solución para $$k(By+x)=B^nx+y$$ $$\text{where}\quad 0<x<B \quad\text{and}\quad n > \text{log}_B(y) \quad\text{and}\quad B\geq2 \quad\text{and}\quad 2\leq k < B$$ reordenando obtenemos $$y = \frac{x(B^n-k)}{Bk-1}$$ Desde $y$ es un número entero, concluimos que $x$ o $B^n-k$ es divisible por $Bk-1$ . Pero $x$ no puede ser divisible por $Bk-1$ porque tenemos $$x<B<2B-1\leq Bk-1\quad\Rightarrow\quad x<Bk-1$$ Por lo tanto, $B^n-k$ debe ser divisible por $Bk-1$ . En consecuencia, escribimos $$B^n-k\equiv 0\ (\text{mod }Bk-1)$$ $$\Updownarrow$$ $$ \quad\quad\quad\quad\quad\quad k\equiv B^n\ (\text{mod }Bk-1) \quad\quad\quad\quad\quad(1) $$ Ya casi hemos llegado. A continuación tenemos que observar una sencilla propiedad de nuestra aritmética modular, a saber, que $Bk$ tiene un resto de $1$ cuando se divide por $Bk-1$ (duh). Así que decimos que $$Bk\equiv 1\ (\text{mod }Bk-1)$$ $$\Downarrow$$ $$ \quad\quad\quad\quad\quad\quad (Bk)^n\equiv 1\ (\text{mod }Bk-1) \quad\quad\quad\quad\quad(2) $$ Ahora multiplicamos los lados izquierdo y derecho de las ecuaciones $(1)$ y $(2)$ respectivamente y observar $$k\cdot(Bk)^n\equiv B^n\cdot1\ (\text{mod }Bk-1)$$ $$\Downarrow$$ $$k^{n+1}B^n\equiv B^n\ (\text{mod }Bk-1)$$ $$\Downarrow$$ $$k^{n+1}\equiv 1\ (\text{mod }Bk-1)$$ Lo que significa que $n+1$ es el orden multiplicativo de $k\ (\text{mod }Bk-1)$ . Pero antes de concluir que la solución también tiene $n+1$ dígitos, hay que decir más.

La solución más pequeña tiene $1$ como primer dígito. Ya que $x$ es el primer dígito de la solución veces $k$ podemos concluir que $x=k$ . Ahora, para ponerlo todo junto, nuestra solución es $$By+x=\frac{1}{k}(B^nx+y)=\frac{1}{k}(B^nk+y)=B^n+\frac{y}{k}$$ que tiene $n+1$ dígitos.

$\bullet\textbf{ Conclusion }\bullet$

Hemos visto que el orden multiplicativo de $k\ (\text{mod }Bk-1)$ es el número de dígitos de la solución más pequeña del acertijo de Talwalkar para la base $B$ y el factor multiplicador $k$ .

Cabe señalar que también podemos concluir que $k$ y $B$ tienen el mismo orden multiplicativo aquí. De la siguiente manera $$k\cdot1\equiv B^n\cdot(Bk)\ (\text{mod }Bk-1)$$ $$\Downarrow$$ $$k\equiv B^{n+1}k\ (\text{mod }Bk-1)$$ $$\Downarrow$$ $$1\equiv B^{n+1}\ (\text{mod }Bk-1)$$

La solución más pequeña tiene el mismo número de dígitos que el orden multiplicativo de $B\ (\text{mod }Bk-1)$ y de $k\ (\text{mod }Bk-1)$