Múltiplo más bajo con vista

Question

Tengo un problema interesante:

Encontrar el menor múltiplo de $130013$ que consta de sólo dos dígitos $9$ base$10$ sistema de numeración.

Llegó a la búsqueda de la menor $n$ tal forma que:

$\begin{cases} 10^n \equiv 1 \pmod{13} \\ 10^n \equiv 1 \pmod{73} \\ 10^n \equiv 1 \pmod{137} \end{cases}$

Y con la ayuda de mi calculadora me enteré de que $n=\text{lcm}(6,8,8)=24$. Debido a $10^{\phi(p)}\equiv_p 1 $ primer $p$, por lo que tengo que comprobar todos los divisores de forma consecutiva: $12,\ 72, \ 136$, como candidatos. Pero, por desgracia, hay muchos divisores de los números en total, y esto lleva a muchos cálculos.

Así que mi pregunta es: ¿es una manera más sencilla de encontrar el orden de un elemento del grupo multiplicativo $\mathbb{Z}_p^*$? Supongo que la respuesta es, lamentablemente, negativo. Así que tal vez, al menos en este caso en particular es más fácil, tal vez algún truco útil que puedo usar aquí?

Answer 1

Un número que puede ser escrito como una...999 999 tiene la forma $10^n - 1$.

Observar que $7 * 11 * 130013 = 7 * 11 * 13 * 10001 = 1001 * 10001 = (10^3+1) \times (10^4 + 1) $.

Recordar la factorización de $a^n - b^n$, esto nos indica que el $10^3 + 1$ $10^4 + 1$ son factores de $10^n +1 $ si $n$ es el doble de un múltiplo de 3 y de 4, o que $n$ es un múltiplo de 24. (Como Maesumi señala, $10^{24} - 1$).

Ahora, considerar el menor valor de $n$ que funciona. Si es menor de 24, a continuación, $n$ debe ser un factor de 24. Ya sabemos que $10^4 + 1$ es también un factor de $10^n -1$, esto nos indica que el $n$ debe ser un múltiplo de 8. Por lo tanto, $n=8$ es la única otra posibilidad. Sin embargo, $10^ 8 -1 \not \equiv 0 \pmod{13} $. Por lo tanto hemos terminado.

Answer 2

No la respuesta que quieres pero me hizo multiplicación básica ajuste de cifras como que necesitaba hacer nueves, y tuve

$130013 \times 7,691,538,538,453,846,923=10^{24}-1$.

¡Hurra, puedo posponer jubilación un año más!

Answer 3

Permítanme tratar de responder a su pregunta original.

Problema: calcular de manera Eficiente el orden de un elemento $a$ del grupo multiplicativo $\mathbb Z^*_n$.

En su cálculo, se utiliza de forma implícita el hecho de que el orden es un divisor de a $\varphi(n)$. Así que lo que siempre funciona, es la comprobación de $a^d=1$ todos los $d\mid \varphi(n)$ (puede excluir $d=\varphi(n)$, ya que esto siempre es cierto). Un número natural $m\in \mathbb N$ son en la mayoría de las $\log_2m$ no trivial divisores, por lo tanto es necesario en la mayoría de las $\log_2\varphi(n)$ comprueba con este método. (Hay $7$ no trivial divisores de $\varphi(137)=136$ en su caso). Supongo que usted utiliza este método.

Si conoce la factorización de $\varphi(n)$, se hace más fácil, usted puede reducir el número de controles a $\log_2\log_2\varphi(n)$.

Nota: el Cómputo de la factorización es mucho más caro. Pero como que estaba tratando de manual de calcular esto, supongo, que es fácil para usted para recuperar la factorización (En este caso: $136=2^3\cdot 17$).

Algoritmo: Escribir $\varphi(n)=p_1^{e_1}\cdot\dots\cdot p_k^{e_k}$, luego el orden de $a$ es de la forma $$p_1^{d_1}\cdot\dots\cdot p_k^{d_k} \text{ for } 0\leq d_i\leq e_i$$ Ahora, para cada una de las $i$ hacer lo siguiente. Para$c$$0$$e_i$, tenemos $$a^{p_1^{e_1}\cdot\dots\cdot p_i^c\cdot\dots\cdot p_k^{e_k}}=1 \Leftrightarrow p_1^{d_1}\cdot\dots\cdot p_k^{d_k} \mid p_1^{e_1}\cdot\dots\cdot p_i^c\cdot\dots\cdot p_k^{e_k} \Leftrightarrow d_i\leq c$$ Empezar con $c=\lfloor\frac{e_i}{2}\rfloor$, si la verificación se mantiene, entonces la conclusión de $d_i\leq c$, de lo contrario $d_i>c$. Continuar con el binario de búsqueda por reducir a la mitad el respectivo intervalo. Será necesario en la mayoría de las $\log_2(e_i)$ cheques.

---

Ejemplo: $136=2^3\cdot 17$. El orden de $10$ $2^{d_1}\cdot 17^{d_2}$ donde $0\leq d_1\leq 3,0\leq d_2\leq 1$.

• Calcular el $d_1$:
  • Compruebe $2^1\cdot 17$: Tenemos $10^{2^1\cdot 17}=100\not\equiv 1\pmod{137}$. Por lo $d_1>1$.
  • Compruebe $2^2\cdot 17$: Tenemos $10^{2^2\cdot 17}=-1\not\equiv 1\pmod{137}$. Por lo $d_1>2$, lo $d_1=3$.
• Calcular el $d_2$:
  • Compruebe $2^3\cdot 17^0$: Tenemos $10^{2^3}=\equiv 1\pmod{137}$. Por lo $d_1\leq 0$$d_1=0$.

Juntos: $2^{d_1}\cdot 17^{d_2}=2^3\cdot 17^0=8$.