Aritmética modular — matemáticas del reloj, mod y congruencia

La aritmética modular consiste en trabajar con los residuos después de dividir entre un entero positivo fijo llamado módulo. Si dos números dejan el mismo residuo, se comportan igual en ese sistema modular, por eso también se le llama matemáticas del reloj.

En un reloj de $12$ horas, las $13$ en punto caen en la $1$, y $29$ horas caen en el mismo lugar que $5$ horas. Ese ciclo repetitivo es la intuición detrás de la aritmética modular.

Qué significa mod en aritmética modular

Para un entero $a$ y un entero positivo $n$, la expresión $a \bmod n$ significa el residuo cuando $a$ se divide entre $n$.

Ejemplo:

$$29 \bmod 12 = 5$$

porque

$$29 = 12 \cdot 2 + 5$$

El módulo es $12$, así que sumar o restar $12$ no cambia la posición en el ciclo.

Qué significa la congruencia módulo $n$

La congruencia es la forma formal de decir que dos enteros se comportan igual módulo $n$.

$$a \equiv b \pmod n$$

significa que $a$ y $b$ dejan el mismo residuo al dividirse entre $n$. Una prueba equivalente es

$$n \mid (a-b)$$

que significa: "$n$ divide a $a-b$".

Entonces,

$$29 \equiv 5 \pmod{12}$$

porque $29 - 5 = 24$, y $12$ divide a $24$.

Esta distinción importa:

• $29 \bmod 12 = 5$ es una afirmación sobre el residuo.
• $29 \equiv 5 \pmod{12}$ es una afirmación de congruencia.

Están relacionadas, pero no son intercambiables.

Ejemplo resuelto: $29$ horas después de las $8$

Supón que ahora son las $8$ en punto y quieres saber qué hora será $29$ horas después en un reloj de $12$ horas.

Primero reduce $29$ módulo $12$:

$$29 \bmod 12 = 5$$

Así que sumar $29$ horas tiene el mismo efecto que sumar $5$ horas:

$$8 + 29 \equiv 8 + 5 \pmod{12}$$

Luego,

$$8 + 29 \equiv 13 \equiv 1 \pmod{12}$$

Así que el reloj marca la $1$ en punto.

El paso clave es la reducción. En módulo $12$, sustituir $29$ por $5$ mantiene la misma respuesta y hace la cuenta más fácil.

Por qué reducir primero facilita los problemas

Los números grandes suelen ser más fáciles de manejar después de sustituirlos por un número congruente más pequeño.

Por ejemplo, módulo $7$,

$$100 \equiv 2 \pmod 7$$

porque $100 - 2 = 98$ es divisible entre $7$. Si el problema solo se interesa por los valores módulo $7$, puedes trabajar con $2$ en lugar de $100$.

Errores comunes

Confundir igualdad con congruencia

$29 \equiv 5 \pmod{12}$ no significa que $29 = 5$. Significa que pertenecen a la misma clase de residuos módulo $12$.

Olvidar que el módulo importa

$17 \equiv 5 \pmod{12}$ es verdadero, pero $17 \equiv 5 \pmod{10}$ es falso. La congruencia siempre está ligada a un módulo específico.

Tratar mod como si fuera una división ordinaria

$29 \bmod 12$ es el residuo $5$, no el cociente $2$ ni la fracción $29/12$.

Suponer que % en software siempre sigue la misma convención matemática

Para números positivos, % en los lenguajes de programación suele coincidir con la idea de residuo que los estudiantes aprenden primero. Con números negativos, las convenciones pueden variar, así que el resultado puede no coincidir con el menor residuo no negativo que se usa en muchos cursos de matemáticas.

Dónde se usa la aritmética modular

La aritmética modular aparece siempre que los valores se repiten en ciclos: relojes, días de la semana, sistemas de dígitos de control, hashing y muchas partes de la teoría de números.

También aparece en criptografía, pero la idea básica sigue siendo la misma: los números se agrupan por sus residuos, y los números congruentes pueden tratarse como equivalentes dentro de ese sistema.

Prueba un problema parecido

¿Qué día de la semana será $100$ días después de un lunes? Como los días se repiten módulo $7$, empieza reduciendo $100$ módulo $7$ antes de responder.

Si quieres otro caso para comparar, prueba tu propia versión en GPAI Solver y observa si reducir primero hace el trabajo más corto.