Lección 3.4: Aplicaciones: últimas cifras — Espinoza Olimpiadas

La última cifra como residuo módulo 10

La última cifra decimal de un entero $n$ es exactamente $n \pmod{10}$ . Así que calcular la última cifra de $7^{2025}$ es calcular $7^{2025} \pmod{10}$ .

La idea clave es que las potencias de cualquier entero módulo $m$ son eventualmente periódicas: como solo hay $m$ residuos posibles, la sucesión $a^1, a^2, a^3, \ldots$ (módulo $m$ ) debe repetir un valor y, desde ahí, ser periódica. Esta periodicidad se detecta encontrando el período de la sucesión de potencias.

Para la última cifra, basta observar las potencias módulo $10$ de cada dígito del $0$ al $9$ . La mayoría tienen períodos cortos: por ejemplo, las potencias de $7$ módulo $10$ siguen el patrón $7, 9, 3, 1, 7, 9, 3, 1, \ldots$ con período $4$ .

7^1 \equiv 7,\; 7^2 \equiv 9,\; 7^3 \equiv 3,\; 7^4 \equiv 1 \pmod{10}

El período de $a^n \pmod m$ y el Pequeño Teorema de Fermat

Para un primo $p$ que no divide a $a$ , el Pequeño Teorema de Fermat garantiza $a^{p-1} \equiv 1 \pmod p$ . Esto implica que el período de la sucesión $a^n \pmod p$ divide a $p-1$ . No necesariamente es exactamente $p-1$ ; puede ser cualquier divisor.

Para módulo $10 = 2 \cdot 5$ : si $\gcd(a, 10) = 1$ , por el Teorema de Euler $a^{\phi(10)} = a^4 \equiv 1 \pmod{10}$ . Así que el período divide a $4$ . Esto explica por qué los patrones de última cifra de enteros terminados en $1, 3, 7, 9$ tienen período dividor de $4$ .

Para números terminados en $2, 4, 5, 6, 8$ hay que analizar por separado, pero los patrones también se estabilizan rápido. Por ejemplo $5^n$ siempre termina en $5$ , y $6^n$ siempre termina en $6$ .

Últimas dos cifras: residuo módulo 100

Las últimas dos cifras de $n$ son $n \pmod{100}$ . Como $100 = 4 \cdot 25$ y $\gcd(4,25)=1$ , es conveniente calcular $n \pmod 4$ y $n \pmod{25}$ por separado y combinar.

Por el Teorema de Euler, si $\gcd(a, 100) = 1$ entonces $a^{\phi(100)} = a^{40} \equiv 1 \pmod{100}$ . Así que para hallar $a^n \pmod{100}$ , basta calcular $n \pmod{40}$ y reducir el exponente.

Ejemplo: hallar las últimas dos cifras de $3^{200}$ . Necesitamos $3^{200} \pmod{100}$ . Como $\phi(100)=40$ , $3^{40} \equiv 1 \pmod{100}$ . Ahora $200 = 5 \cdot 40$ , así que $3^{200} = (3^{40})^5 \equiv 1^5 = 1 \pmod{100}$ . Las últimas dos cifras son $01$ .

a^{\phi(m)} \equiv 1 \pmod{m} \quad (\gcd(a,m)=1)

Estrategia general para potencias en olimpiadas

El método estándar para calcular $a^n \pmod m$ en un problema de olimpiada tiene tres pasos: (1) encontrar el período $T$ de $a^k \pmod m$ (usualmente $T \mid \phi(m)$ o $T \mid p-1$ para $p$ primo), (2) reducir el exponente: $a^n \equiv a^{n \bmod T} \pmod m$ , (3) calcular la potencia reducida por exponenciación rápida si es necesario.

Una advertencia: el paso (2) requiere cuidado cuando $T \mid n$ exactamente, pues $n \bmod T = 0$ pero $a^0 = 1 \not\equiv a^T$ . En ese caso el resultado es $a^T \equiv 1 \pmod m$ (si $T$ es el período exacto).

En problemas de última cifra no olvides verificar si $\gcd(a,10) > 1$ : si $a$ es par o múltiplo de $5$ el análisis es directo (las potencias altas de $2$ terminan en $2, 4, 8, 6, 2, 4, 8, 6, \ldots$ ). Con práctica, este flujo se vuelve automático.

Aplicaciones: últimas cifras

Objetivo de la lección

La última cifra como residuo módulo 10

El período de $a^n \pmod m$ y el Pequeño Teorema de Fermat

Últimas dos cifras: residuo módulo 100

Estrategia general para potencias en olimpiadas

Problemas del Capítulo 3 — con solución