Potencias Modulares

Modulo 5 · Teoría de Números

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: solo necesitas $\lceil \log_2 n \rceil$ multiplicaciones.

Exponenciación Rápida (Binary Exponentiation)

Base: 3

Exponente: 13

Módulo: 7

Exponente en binario: 1101

bit 0: 3^1 ≡ 3, acum = 3

bit 2: 3^4 ≡ 4, acum = 5

bit 3: 3^8 ≡ 2, acum = 3

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

Concepto Clave

"La exponenciación binaria calcula a^n 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: genera todos los residuos coprimos con n (0, 1, ..., φ(n)-1 si vemos las potencias de a mod 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.

OIM 2018

Enigma de las Potencias Modulares

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

Ver Solución Razonada

1.Observar que $1023 = 2^{10} - 1$ .

2.Por definición, $2^{10} = 1024 \equiv 1 \pmod{1023}$ .

3.¿Es 10 el menor? El orden debe dividir a 10. Los divisores son 1, 2, 5. Verificar: $2^1=2, 2^2=4, 2^5=32$ . Ninguno es ≡ 1 mod 1023.

\text{ord}_{1023}(2) = 10