¿Cuál es el resto cuando 3 ^ 30 se divide por 20 ^ 10?

Podrías encender una computadora y preguntar, y obtuve 1091132094649, pero debes decir, ¿cómo podría hacerse esto con un mínimo de lápiz y papel, o cómo podría hacerse un problema mucho mayor en una computadora sin un uso extravagante? de ciclos de CPU.

Probablemente desee el teorema del resto chino para esto. 20 = 2 ^ 2 * 5, entonces 20 ^ 10 = 2 ^ 20 * 5 ^ 10.

Entonces, ¿qué es 3 ^ 30 mod 5 ^ 10? Trabajo en base 5 aritmética. 3 ^ 3 = 102, 3 ^ 6 = 102 * 102 = 10404, 3 ^ 12 = 114001231, ahora multiplique por 3 ^ 3 = 102, pero DESCONOCIENDO todos los dígitos más allá de la décima potencia de 5: 12133131112 recorta a 2133131112. Finalmente cuadre esto fuera, descartando todo lo que supere la décima potencia de 5 a medida que avanzas: 4304012044. Base 10, para volver al césped familiar, este es 9047774.

Ahora querrás 3 ^ 30 mod 2 ^ 20. El mismo ejercicio, pero esta vez estás trabajando en binario. Terminas aprendiendo que es 686265 mod 2 ^ 20.

Ahora es el momento del teorema del resto chino. Esto dice que dados dos módulos relativamente primos, aquí 2 ^ 20 y 5 ^ 10, y condiciones de congruencia mod cada uno, aquí que la respuesta es 9047774 mod el primero y 686265 mod el otro, hay un n único entre 0 y el producto de sus módulos, menos 1. Y lo encuentra a través de la idea de que si n = a mod p y b mod q, entonces n = a + pk so (a + pk) = b mod q. entonces pk = (ba) mod q, entonces k = (inverso de p) * (ba) mod q. Y el inverso de p mod q se encuentra con el algoritmo euclidiano extendido. (Extrae el mcd de p y q, sabiendo muy bien que será 1 al final, pero haciendo un seguimiento de lo que aprende sobre s * p + t * q = cada vez más pequeño, a medida que avanza, hasta obtener s * p + t * q = 1 y luego s es el inverso de p mod q.)