Aplicaciones en olimpiadas

El flujo estándar: "reduce el exponente"

La mayoría de los problemas de olimpiada regional que involucran $a^n \pmod p$ siguen este flujo: (1) identificar el primo $p$ del problema, (2) verificar que $p \nmid a$, (3) calcular $r = n \bmod (p-1)$, (4) calcular $a^r \pmod p$ por exponenciación directa o por observación del patrón.

El paso (3) puede requerir a su vez calcular $n \pmod{p-1}$, que a veces involucra otro primo. Por ejemplo, calcular $2^{2025} \pmod{13}$: $p = 13$, $p - 1 = 12$. Necesitamos $2025 \pmod{12}$. Como $2025 = 168 \cdot 12 + 9$, se tiene $2^{2025} \equiv 2^9 = 512 \equiv 512 - 39 \cdot 13 = 512 - 507 = 5 \pmod{13}$.

La clave es automatizar este flujo hasta que sea reflejo: "¿potencia grande módulo primo? Fermat, reduce el exponente".

Divisibilidades usando $a^p \equiv a \pmod p$

La versión $a^p \equiv a \pmod p$ —válida para todo entero $a$— es especialmente útil para demostrar que ciertas expresiones son siempre divisibles por un primo dado.

Ejemplo clásico: demostrar que $p \mid a^p - a$ para todo primo $p$ y todo entero $a$. Esto es exactamente $a^p \equiv a \pmod p$, que es la reformulación del teorema. En particular, $p \mid n^p - n$ para todo entero $n$.

Problema: demostrar que $42 \mid n^7 - n$ para todo entero $n$. Factorizamos: $42 = 2 \cdot 3 \cdot 7$. Por el teorema, $2 \mid n^2 - n \mid n^7 - n$, $3 \mid n^3 - n \mid n^7 - n$, $7 \mid n^7 - n$. Como $2$, $3$, $7$ son primos distintos que dividen a $n^7 - n$, también $42 \mid n^7 - n$. La verificación de la divisibilidad intermedia ($n^2 - n \mid n^7 - n$ etc.) se hace con la factorización $n^7 - n = n(n-1)(n+1)(n^2+n+1)(n^2-n+1)$ o directamente por Fermat.

Últimas cifras de potencias con exponente primo

Calcular la última cifra de $3^{2026}$. Necesitamos $3^{2026} \pmod{10}$. Como $10 = 2 \cdot 5$, calculamos módulo $2$ y módulo $5$ por separado.

Módulo $2$: $3 \equiv 1 \pmod 2$, así $3^{2026} \equiv 1 \pmod 2$.

Módulo $5$: por Fermat ($p = 5$, $5 \nmid 3$), $3^4 \equiv 1 \pmod 5$. Como $2026 = 506 \cdot 4 + 2$, se tiene $3^{2026} \equiv 3^2 = 9 \equiv 4 \pmod 5$.

Combinando: buscamos $x$ con $x \equiv 1 \pmod 2$ y $x \equiv 4 \pmod 5$. La solución es $x \equiv 4 \pmod{10}$ (pues $4$ es impar — no, $4$ es par). Ajustamos: $x = 4$ no funciona ($4$ es par). El siguiente en la clase $4 \pmod 5$ es $9$, que es impar. Así $3^{2026}$ termina en $9$.

Problemas con "¿es divisible por $p$?"

Un tipo frecuente en la ONEM regional pide determinar si una suma como $1^{p-1} + 2^{p-1} + \cdots + (p-1)^{p-1}$ es divisible por $p$.

Por el Pequeño Teorema de Fermat, cada sumando $k^{p-1} \equiv 1 \pmod p$ para $k = 1, 2, \ldots, p-1$. Hay $p - 1$ sumandos, cada uno congruente a $1$. La suma es $\equiv p - 1 \equiv -1 \pmod p$. Conclusión: la suma NO es divisible por $p$; de hecho deja residuo $p - 1$.

Variante: ¿es $1^{p-1} + 2^{p-1} + \cdots + (p-1)^{p-1} + 1$ divisible por $p$? Ahora la suma es $-1 + 1 = 0 \pmod p$. Sí es divisible. Este pequeño ajuste cambia completamente la respuesta.

La lección metodológica: en problemas con sumas de potencias módulo un primo, Fermat suele convertir cada potencia en $1$ (o en $0$ si la base es múltiplo de $p$) y reduce el problema a contar términos.

El orden de un elemento y divisores de $p-1$

El orden de $a$ módulo $p$ (con $p \nmid a$) es el menor entero positivo $d$ tal que $a^d \equiv 1 \pmod p$. El Pequeño Teorema de Fermat implica que $d \mid p - 1$.

Demostración: como $a^{p-1} \equiv 1$ y $a^d \equiv 1$, si $p - 1 = dq + r$ con $0 \le r < d$, entonces $1 \equiv a^{p-1} = (a^d)^q \cdot a^r \equiv a^r$. Por minimalidad de $d$, $r = 0$, es decir $d \mid p - 1$.

Esto es útil para encontrar el período exacto de una base: en lugar de probar todos los enteros, solo hay que probar los divisores de $p - 1$. Por ejemplo, para encontrar el período de $2$ módulo $7$: los divisores de $6$ son $1, 2, 3, 6$. Calculamos $2^1 = 2$, $2^2 = 4$, $2^3 = 8 \equiv 1 \pmod 7$. El período es $3$.