Problema numero 5 - The theory of numbers

Salto el 3 y 4 no los sé hacer de inmediato.

Encontrar el menor residuo positivo de 26^1000 módulo 29

26 :~ -3 (mod 29)

26^2 = 26·26 :~ (-3)(-3) :~ 9 (mod 29)

26^4 = 26^2·26^2 :~ 9·9 :~81 :~ 23 :~ -6 (mod 29)

26^8 = 26^4·26^4 :~ (-6)(-6) :~ -36 :~ 7 (mod 29)

26^16 :~ 49 :~ 20 :~ -9 (mod 29)

26^32 :~ 81 :~ -6 (mod 29)

Hemos encontrado una repetición, eso nos permite repetir ciclos (-6, 7, -9) sin hacer cuentas

26^64 :~ 7 (mod 29)

26^128 :~ -9

26^256 :~ -6

26^512 :~ 7

Ahora para obtener 1000 veamos que producto de potencias con congruencia conocida debemos usar

1000 - 512 = 488

488 - 256 = 232

232 - 128 = 104

104 - 64 = 40

40 - 32 = 8

Luego 1000 = 512 + 256 + 128 + 64 + 32 + 8

26^1000 = 26^512 · 26^256 · 26^128 · 26^64 · 26^32 · 26^8

26^1000 :~ 7· (-6) · (-9) · 7 · (-6) · 7 (mod 29)

Y vamos haciendo las multiplicaciones paso a paso o dos si se pueden. Si te dejaran usar calculadora harías todas de golpe

7·(-6) = -42 :~ 16 (mod 29)

16 · (-9) = -144 :~ -1 (mod 29)

1 · 7 · (-6) = - 42 :~ 16 (mod 29)

16 · 7 = 112 :~ 25 (mod 29)

Lo de todo de golpe sería

7· (-6) · (-9) · 7 · (-6) · 7 = -111132

-111132 / 29 = -3832.13

Tomamos siempre el entero menor tanto sea positivo como negativo, eso significa -3833 en este caso. Y luego es siempre el número menos el cociente por el divisor

-111132 - (-3833)·29 = 25

Bueno pues al final

26^1000 ;:~ 25 (mod 29)

Y eso es todo.