¿Lo que ' s el resto si se divide $99{,}999^{99}$ $999{,}999$?

Question

¿Qué es el resto si se divide <span class="math-container">$99{,}999^{99}$</span> <span class="math-container">$999{,}999$</span>?

¿Hay cualquier método fórmula o truco para conseguirlo? También amablemente ignorar el uso indebido de la etiqueta, no sé que etiqueta a elegir

Answer 1

$\!\bmod 999999\!:\,\ 10\cdot99999\equiv -9\ $ lo $\ 99999 \equiv -9/10$

Por lo tanto $\,99999^{\large99}\equiv -9^{\large 99}/10^{\large 99}\equiv -9^{\large 99}/10^{\large 3}\equiv -10^{\large 3}\cdot 9^{\large 99}\ $ a través de $\ 10^{\large 6}\equiv 1$

$n := 999999/27 = 7\cdot 11\cdot 13\cdot 37.\,$ mod cada una de las $p,\,$ $9\,$ tiene orden de $\,3,5,3,9\,$ lo $\,9^{\large \color{#c00}{45}}\equiv 1\pmod{\!n}$

por lo $\ 9^{\large 99}\!\bmod 999999 = 27(3\cdot 9^{\large \color{#c00}{97}}\!\bmod n) = 27(3\cdot 9^{\large 7}\!\bmod n) \equiv 9^{\large 9}\!\pmod{\!999999}$

Por lo tanto llegamos a la conclusión de $\ 99999^{\large 99}\equiv -10^{\large 3}\cdot 9^{\large 99}\equiv {-}10^{\large 3}\cdot 9^{\large 9}\equiv 123579\,\pmod{\!999999}$

Answer 2

Trabajamos en el ring $R=\Bbb Z/N$, con la operación de modulo $N=999999=10^6-1$. (Igualdades siguiente dirección de cómputos en $R$.) Entonces $$ \begin{aligned} 99999^{99} &=(99999-999999)^{99} =(-900000)^{99}=-9^{99}\cdot (10^5)^{99}\\ &=-3^{198}\cdot 10^{495}=-3^{198}\cdot {\underbrace{(10^6)}_{=1}}^{82}\cdot 10^3=-3^{198}\cdot 1000\ . \end{aligned} $$ Ahora el orden de (la unidad) $3$ en el ring

$\Bbb Z/37037 =\Bbb Z/(7\cdot 11\cdot 13\cdot 37) \cong (\Bbb Z/7)\times (\Bbb Z/11)\times (\Bbb Z/13)\times (\Bbb Z/37) $

is $90$, but we need only the simpler information that $3^{180}$ is one modulo $37037$. This is so because $180$ is a multiple of $(7-1)$, $(11-1)$, $(13-1)$, and $(37-1)$. So instead of $3^{198}$ we write the smaller power $3^{18}=387420489$.

We finally search for a number which is $0$ modulo $27$, and also $-387420489000$ modulo $37037$, which is $12468$. After rearrangements modulo $3,9,27$ obtenemos el resultado $$123579\ .$$

---

Nota: Un sistema de álgebra computacional como sage ofrece de inmediato

sage: Zmod(999999)(99999)^99
123579