Aritmética Modular — El Reloj Matemático

Modulo 5 · Teoría de Números

Congruencias: La Idea

Si hoy es miércoles, ¿qué día será dentro de 100 días? No necesitas contar uno a uno: $100 = 14 \times 7 + 2$ . Será viernes. ¡Eso es aritmética modular!

a \equiv b \pmod{m} \iff m \mid (a - b)

Leemos: "a es congruente con b módulo m". Significa que $a$ y $b$ dejan el mismo residuo al dividir entre $m$ .

Reloj Modular

Visualiza $23 \pmod{7}$ como un reloj

Módulo

m

= 7

Valor

n

= 23

$23 \equiv 2 \pmod{7}$

Misma clase: 2, 9, 16, 23, 30, 37...

Concepto Clave

"La aritmética modular convierte un problema con números enormes en un problema con números pequeños. Eso es su poder."

Operaciones Modulares

Suma

(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m

Producto

(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m

Potencia

a^n \bmod m = (a \bmod m)^n \bmod m

⚠️ NO se puede dividir directamente

$ac \equiv bc \pmod{m}$ no implica $a \equiv b \pmod{m}$ siempre. Solo funciona si $\gcd(c, m) = 1$ .

🔑 ¿Cómo se "divide" en aritmética modular?

Usando el inverso modular: el número $a^{-1}$ tal que $a \cdot a^{-1} \equiv 1 \pmod{m}$ . Existe si y solo si $\gcd(a, m) = 1$ .

Ejemplo: ¿Cuánto es $3^{-1} \pmod{7}$ ?

Busco $b$ tal que $3b \equiv 1 \pmod{7}$ . Probando: $3 \times 5 = 15 = 2 \times 7 + 1 \equiv 1$ . ✓

Por tanto $3^{-1} \equiv 5 \pmod{7}$ . Para calcular $\frac{2}{3} \pmod{7}$ : $2 \times 5 = 10 \equiv 3$ .

💡 El Algoritmo de Euclides Extendido (Módulo 6) calcula el inverso modular eficientemente.

Tabla de Operaciones mod 5

m=5

+	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

Concepto Clave

"Puedes sumar, restar y multiplicar módulo m sin problemas. Para 'dividir' por c, multiplica por su inverso modular c⁻¹ (que existe solo si gcd(c,m) = 1)."

Problemas de Olimpiada

Problema 1

Último dígito de potencias

¿Cuál es el último dígito de $7^{2023}$ ?

Ver Solución

Últimos dígitos de las potencias de 7: $7^1=7, 7^2=9, 7^3=3, 7^4=1, 7^5=7,\ldots$

Ciclo de longitud 4. Como $2023 = 4 \times 505 + 3$ :

7^{2023} \equiv 7^3 \equiv 3 \pmod{10}

. Último dígito: 3.

Problema 2

Residuo de un factorial

¿Cuál es el residuo de $100!$ al dividir entre 7?

Ver Solución

$100!$ contiene al factor 7 (y 14, 21, ..., 98).

Como $7 \mid 100!$ , el residuo es simplemente:

100! \equiv 0 \pmod{7}

💡 Para cualquier primo $p \leq n$ , siempre $p \mid n!$ .