1 Respuesta
El teorema de Euler dice que si a y n son primos relativos se cumple
a^[fi(n)] ~: 1 (mod n)
Donde fi(n) es una función de Euler que indica el número de coprimos con n que hay en 1,2,3,..., n
En este problema tenemos que calcular las dos últimas cifras de un número. Esa cifras son el módulo 100 de ese número, luego donde pone n pondremos 100 y tenemos
a ^[fi(100)] ~: 1 (mod 100)
Debemos calcular fi(100). Para ello hay que usar unos teoremas.
Hay uno que dice que si m y n son coprimos entonces fi(mn) = fi(m)·fi(n)
Y hay otro que dice que si p es primo fi(p^k) = p^k - p^(k-1)
Con esto hacemos
100 = 2^2 · 5^2
fi(2^2) = 2^2 - 2^1 = 2
fi(5^2) = 5^2 - 5 = 20
y como 4 y 25 son primos entre sí
fi(100) = fi(4)·fi(25) = 2·20 =40
Luego el teorema de Euler se traduce en
7^40 ~: 1 (mod 100)
Se pueden elevar los dos miembros de una congruencia a la misma potencia, los elevamos a la 5
(7^40)^5 ~: 1^5 (mod 100)
7^200 ~: 1 (mod 100)
El residuo modulo 100 de 7^209 será el de 7^9, habrá que hacerlo a mano procurando usar el menor número posible de operaciones y lo más sencillas posible.
7 ~: 7 (mod 100)
7^2 ~: 49 (mod 100)
7^4 = 2401 ~: 1 (mod 100)
7^8 ~: 1^2 (mod 100)
7^9 ~: 7 (mod 100)
Luego las dos últimas cifras son 07
Y eso es todo.
