Problema numero 6 - The theory of numbers

Es calcular los dos dígitos finales en decimal de 9^99 y lo que sugiere es calcular 9^99 módulo 10^2.

Hagámoslo

9 :~ 9 (mod 100)

9^2 :~ 9·9 :~ 81 (mod 100)

9^4 :~ 81·81 :~ 61 (mod 100)

9^8 :~ 61·61 ;~ 3721 :~ 21 (mod 100)

9^16 :~ 21·21 :~ 441 :~ 41 (mod 100)

9^32 :~ 41·41 :~ 1681 :~ 81 (mod 100)

Hemos repetido el residuo de 9^4, lo aprovechamos para escribir el siguiente sin repetir el cálculo que ya hicimos cuando se calculó el residuo de 9^8

9^64 :~ 61 (mod 100)

Ya tenemos los residuos de un sistema binario que nos serviría para números hasta 127

99 = 64 + 32 + 2 + 1

9^99 = 9^64 · 9^32 · 9^2 · 9

9^99 :~ 61 · 81 · 81 · 9 :~

Se podrían hacer las cuentas ya. Pero vamos a aprovechar cálculos que ya hicimos

El 81·81 era congruente con 61 y entonces queda un 61·61 congruente con 21, al final queda 21·9 = 189 :~ 89 (mod 89)

Luego es congruente con 89

Y eso es todo.