Reducción de Exponentes Grandes

Teoría

La técnica de reducir exponentes grandes es una herramienta fundamental en la aritmética modular que sirve para calcular $a^k \pmod n$ cuando $k$ es extremadamente grande. Calcular $a^k$ directamente suele ser imposible por lo enorme que es el número resultante. Pero la teoría de números te da un atajo aprovechando que las potencias en aritmética modular son cíclicas. Específicamente, la secuencia de potencias $a^1, a^2, a^3, \dots \pmod n$ tarde o temprano se vuelve periódica. En cuanto identificas un ciclo, puedes "adelantarte" en la secuencia reduciendo el exponente $k$ módulo la longitud de ese ciclo.

Para un módulo primo $p$, esta longitud de ciclo tiene que ver con $p-1$. El Pequeño Teorema de Fermat dice que si $p$ es primo y $a$ no es divisible entre $p$, entonces $a^{p-1} \equiv 1 \pmod p$. Como multiplicar por 1 no cambia nada, elevar $a$ a la potencia $p-1$ básicamente "reinicia" el proceso de multiplicación. Por eso, puedes quitar múltiplos de $p-1$ del exponente sin cambiar el resultado módulo $p$. Esto te permite cambiar un exponente masivo $k$ por un residuo mucho más chico $r$, donde $r = k \pmod{p-1}$.

Este concepto se generaliza a módulos compuestos con el Teorema de Euler, donde reduces el exponente módulo $\phi(n)$. Algo clave que debes notar es la diferencia entre los dos módulos involucrados: la base se calcula módulo $n$ (o $p$), mientras que el exponente se reduce módulo $\phi(n)$ (o $p-1$). Confundir estos dos módulos es un error muy común en las olimpiadas de matemáticas.

Fórmulas Clave

Pequeño Teorema de Fermat (Módulo Primo) Si $p$ es un número primo y $\gcd(a, p) = 1$, entonces: $$a^{p-1} \equiv 1 \pmod p$$

Fórmula de Reducción de Exponentes (Módulo Primo) Basándote en el Pequeño Teorema de Fermat, para cualquier entero $k \ge 0$: $$a^k \equiv a^{k \pmod{p-1}} \pmod p$$

Teorema de Euler (Módulo General) Si $n$ es un entero positivo y $\gcd(a, n) = 1$, entonces: $$a^{\phi(n)} \equiv 1 \pmod n$$ donde $\phi(n)$ es la función phi de Euler.

Reducción General de Exponentes $$a^k \equiv a^{k \pmod{\phi(n)}} \pmod n$$

Demostración

Teorema: Sea $p$ un primo y $a$ un entero tal que $\gcd(a, p) = 1$. Sea $k$ un entero no negativo. Entonces $a^k \equiv a^{k \pmod{p-1}} \pmod p$.

Demostración:

1. Algoritmo de la División: Por el algoritmo de la división, puedes dividir el exponente $k$ entre $(p-1)$. Existen enteros únicos $q$ (cociente) y $r$ (residuo) tales que: $$k = q(p-1) + r$$ donde $0 \le r < p-1$. Nota que, por definición, $r = k \pmod{p-1}$.

2. Expansión de Potencias: Sustituye esta expresión de $k$ en la potencia $a^k$: $$a^k = a^{q(p-1) + r}$$ Usando las leyes de los exponentes, puedes escribir esto como: $$a^k = (a^{p-1})^q \cdot a^r$$

3. Aplicación del Pequeño Teorema de Fermat: Como $p$ es primo y $\gcd(a, p) = 1$, el Pequeño Teorema de Fermat garantiza que: $$a^{p-1} \equiv 1 \pmod p$$

4. Sustitución y Simplificación: Trabajando módulo $p$, sustituye $1$ en lugar de $a^{p-1}$ en la ecuación del Paso 2: $$a^k \equiv (1)^q \cdot a^r \pmod p$$ $$a^k \equiv 1 \cdot a^r \pmod p$$ $$a^k \equiv a^r \pmod p$$

5. Conclusión: Como $r = k \pmod{p-1}$, queda demostrado que: $$a^k \equiv a^{k \pmod{p-1}} \pmod p$$

   $\square$