Potencias Modulares

Módulo 5 · Teoría de Números

¿En qué termina 7 elevado a 2027?

El número $7^{2027}$ tiene más de 1.700 cifras: ninguna calculadora del colegio lo muestra. Pero su última cifra se puede saber en un minuto, porque las últimas cifras de las potencias de 7 se repiten en un ciclo. Míralo en un reloj de 10 posiciones.

Momento animado

Las últimas cifras dan vueltas

Cada salto multiplica por 7 y se queda con la última cifra. Mira cuándo vuelve al 1.

Potenciaexponente 0

Etapas

Etapa 1 de 4 · 7⁰

Empezamos en 7⁰ = 1. Para la última cifra solo importa el residuo módulo 10, y cada salto multiplica por 7 y se queda con la última cifra.

Exponenciación Binaria

¿Cómo calcular $3^{1000000} \bmod 17$ rápido? Fermat reduce el exponente, pero hay otra técnica poderosa:

La idea: cualquier exponente se puede escribir en binario. Si $n = 13 = 1101_2$ , entonces:

a^{13} = a^8 \cdot a^4 \cdot a^1

Cada potencia de 2 se obtiene elevando al cuadrado la anterior: basta con unos $\log_2 n$ cuadrados y, como mucho, otras tantas multiplicaciones.

Laboratorio

Exponenciación rápida

Mueve la base, el exponente y el módulo: solo se multiplican los cuadrados que pide el binario del exponente.

$3^{13} \equiv 3 \pmod{7}$

13 = 1101₂ = 8 + 4 + 1

$3^{1} \equiv 3$ se usa (bit 1)
$3^{2} \equiv 2$ no se usa (bit 0)
$3^{4} \equiv 4$ se usa (bit 1)
$3^{8} \equiv 2$ se usa (bit 1)

$3^{13} \equiv 2 \cdot 4 \cdot 3 = 24 \equiv 3$

Basea = 3

Exponenten = 13

Módulom = 7

Con 3 cuadrados y 2 multiplicaciones sale 3 elevado a la 13, sin calcular el número gigante.

Concepto Clave

"La exponenciación binaria calcula aⁿ mod m en O(log n) pasos. Combinada con Fermat/Euler, es imbatible."

Orden Multiplicativo

El orden de $a$ módulo $n$ (escrito $\text{ord}_n(a)$ ) es el menor entero positivo $k$ tal que $a^k \equiv 1 \pmod{n}$ .

Propiedad Clave

$a^m \equiv 1 \pmod{n} \iff \text{ord}_n(a) \mid m$

Por Euler: $\text{ord}_n(a) \mid \varphi(n)$ siempre.

Ejemplo: Orden de 2 mod 7

$2^1$

$2^2$

$2^3$

$2^4$

$2^5$

$2^6$

$\text{ord}_7(2) = 3$ (primer 1), y $3 \mid 6 = \varphi(7)$ ✓

Concepto Clave

"El orden siempre divide a φ(n). Cuando ord_n(a) = φ(n), decimos que a es una raíz primitiva de n: sus potencias a⁰, a¹, … hasta a elevado a φ(n) − 1 recorren todos los residuos coprimos con n."

Banco de Problemas

Problemas de entrenamiento nivel olimpiada

Instrucciones: Intenta responder cada problema antes de ver la solución. Usa las Pistas Socráticas si te atascas.

Enigma del Orden Multiplicativo

Encuentre el menor entero positivo $n$ tal que $2^n \equiv 1 \pmod{1023}$ :

Práctica · La última cifra

¿En qué cifra termina

7^{2027}

Práctica · El largo del ciclo

¿En qué cifra termina

7^{2017}

Práctica · Otro ciclo

Las últimas cifras de 2, 2², 2³, 2⁴, 2⁵… son 2, 4, 8, 6, 2… ¿En qué cifra termina

2^{100}