Problema numero 7 - The theory of numbers

Determinar las tres cifras últimas de 7^493. Y la pista que da es trabajar en módulo 10^3 (eso ya lo sabíamos) y ver que 7^20 :~ 1 (mod 1000)

Esa segunda si que es una buena pista, vamos a probarla

7^1 :~ 7 (mod 1000)

7^2 :~ 49 (mod 1000)

7^4 :~ 49·49 :~ 2401 :~ 401 (mod 1000)

7^8 :~ 401 · 401 :~ 160801 :~ 801 (mod 1000)

7^16 :~ 801·801 :~ 641601 :~ 601 (mod 1000)

Y ahora

7^20 = 7^16 · 7^4 :~ 601 · 401 :~ 241001 :~ 1 (mod 1000)

Luego es verdadera la pista

Ahora todo (7^20)^n :~ 1 (mod 1000) luego

7^480 :~ 1 (mod 100)

Con lo cual

7^493 = 7^480 · 7^13 :~ 1 · 7^13 :~ 7^13 (mod 1000)

Y ahora aprovecharemos los cálculos ya efectuados

7^13 = 7^8 · 7^4 · 7 :~ 801 · 401 · 7 :~ 2248407 :~ 807 (mod 1000)

Luego las tres cifras ultimas de 7^493 son 807

Y eso es todo.