Aritmética Modular
La aritmética modular es un sistema aritmético para enteros donde los números "dan la vuelta" al alcanzar un módulo, como las horas en un reloj.
Formula
a \bmod n = \text{remainder when } a \text{ is divided by } n
Definition
La aritmética modular es la aritmética del reloj: cuando llegas al módulo (como el $12$ en un reloj), vuelves a cero, y "$17 \bmod 5$" pregunta cuál es el residuo cuando $17$ se divide entre $5$. Dos enteros $a$ y $b$ son congruentes ($a \equiv b \pmod{n}$) si $n$ divide a $(a - b)$; los enteros módulo $n$ forman un anillo $\mathbb{Z}_n = \{0, 1, \ldots, n-1\}$ bajo esta aritmética de residuos, y si $n$ es primo, $\mathbb{Z}_n$ es un cuerpo (cuerpo de Galois $GF(p)$). El Teorema Chino del Resto establece que si $\gcd(m,n) = 1$, entonces $\mathbb{Z}_{mn} \cong \mathbb{Z}_m \times \mathbb{Z}_n$, y el Pequeño Teorema de Fermat da $a^{p-1} \equiv 1 \pmod{p}$ para $p$ primo y $a$ no divisible entre $p$.
Example
$17 \bmod 5 = 2$ (ya que $17 = 3 \times 5 + 2$); en un reloj, $10$ horas después de las $7$ en punto son las $5$ en punto ($17 \bmod 12 = 5$). La aritmética también funciona módulo $n$: $7 + 8 \equiv 3 \pmod{12}$ y $5 \times 7 \equiv 11 \pmod{12}$; en $\mathbb{Z}_7$ (primo), todo elemento distinto de cero tiene un inverso multiplicativo. El cifrado RSA se basa en esto: elige primos $p, q$, define $n=pq$, cifra con $c = m^e \bmod n$ y descifra con $m = c^d \bmod n$ donde $ed \equiv 1 \pmod{(p-1)(q-1)}$, con la seguridad descansando en la dificultad de factorizar $n$.
Key Insight
La aritmética modular aparece en todas partes: los días de la semana (mod 7), los ciclos AM/PM (mod 12/24), y los dígitos de verificación en códigos de barras y tarjetas de crédito, convirtiendo un conjunto infinito (los enteros) en un anillo finito que permite aplicar resultados de teoría de números a estructuras finitas en criptografía y teoría de códigos. La estructura de $\mathbb{Z}_n^*$ (las unidades módulo $n$) sustenta no solo a RSA sino a toda la teoría de la criptografía de curva elíptica y la prueba de primalidad AKS, haciendo de la aritmética modular un fundamento de la seguridad informática moderna.