Problema número 10 de adler

Use el teorema de Euler para encontrar los dos últimos dígitos de 7^209

El teorema de Euler dice que si a y m son primos entre sí entonces

a^fi(m) ~: 1 (mod m)

Donde fi(m) es una función que indica los coprimos con m que hay entre 1 y m

.

Como 7 y 100 son primos entonces

7^Fi(100) ~: 1 (mod 100)

Hay mucha teoría sobre el calculo de fi(m), entre ella destacan

Si m y n primos entre si fi(nm) = fi(n)·fi(m)

Si p es primo pi(p^k) = p^k - p^(k-1)

Con esto podemos calcular

fi(100) = fi(2^2 · 5^2) = fi(2^2) · fi(5^2) = (2^2 - 2) (5^2 - 5) = 2·20 = 40

Luego 7^40 ~: 1 (mod 100)

Una propiedad de las congruencias es

si a ~: b (mod n) entonces a^r ~: b^r (mod n) siendo r € N

Vamos a elevar a la 5

(7^40)^5 ~: 1^5 (mod 100)

(7^200) ~: 1 (mod 100)

Y el problema se recude a calcular las dos últimas cifras de 7^9, eso ya se puede hacer a mano o calculadora

7^2 = 49

7^3 = 343 ~: 43 mod (100)

7^4 ~: 43 · 7 = 301 ~: 1 (mod 100)

Ahora elevamos la congruencia al cuadrado

7^8 ~: 1·1 (mod 100)

7^9 ~ 7 (mod 100)

Luego las dos últimas son 07

Y eso es todo.