Mejor respuesta
2 ^ 30 * 3 ^ 20
= (2 ^ 3) ^ 10 * (3 ^ 2) ^ 10
= 8 ^ 10 * 9 ^ 10
= (8 * 9) ^ 10
= 72 ^ 10
desde 72 mod 7 = 2,
72 ^ 10 mod 7
= (2 ^ 10) mod 7
= 1024 mod 7
= 2
Respuesta
Podrías encender una computadora y preguntar, y yo obtuve 1091132094649, pero debes querer decir, ¿cómo se puede hacer esto con un mínimo de trabajo de lápiz y papel, o cómo se puede hacer un problema mucho mayor en una computadora sin un uso extravagante de los ciclos de la CPU?
Probablemente quiero 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? Trabaja en aritmética de base 5. 3 ^ 3 = 102, 3 ^ 6 = 102 * 102 = 10404, 3 ^ 12 = 114001231, ahora multiplique por 3 ^ 3 = 102, pero DESCARTANDO todos los dígitos más allá de la décima potencia de 5: 12133131112 recorta a 2133131112. Finalmente eleve al cuadrado esto fuera, descartando todo lo que esté por encima de la décima potencia de 5 sobre la marcha: 4304012044. Base 10, para volver al terreno familiar, este es 9047774.
Ahora querrás 3 ^ 30 mod 2 ^ 20. El mismo ejercicio, pero esta vez está trabajando en binario. Terminas aprendiendo que es 686265 mod 2 ^ 20.
Ahora es el momento del teorema chino del resto. 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 tus módulos, menos 1. Y lo encuentras mediante la idea de que si n = a mod p y b mod q, entonces n = a + pk entonces (a + pk) = b mod q. entonces pk = (b-a) mod q, entonces k = (inverso de p) * (b-a) mod q. Y la inversa de p mod q se encuentra con el algoritmo euclidiano extendido. (Extrae el mcd de pyq, sabiendo muy bien que será 1 al final, pero manteniendo un registro de lo que aprende sobre s * p + t * q = cada vez más pequeño, a medida que avanza, hasta que obtenga s * p + t * q = 1 y luego s es la inversa de p mod q.)