La aritmética modular fue desarrollada sistemáticamente por Carl Friedrich Gauss en su obra Disquisitiones Arithmeticae (1801), aunque conceptos similares ya habían sido utilizados por matemáticos anteriores. Gauss introdujo la notación $a \equiv b \pmod{m}$ que seguimos utilizando hoy en día. Esta rama de las matemáticas ha demostrado ser fundamental en áreas como la teoría de números, criptografía y álgebra abstracta.
La aritmética modular es un sistema de aritmética para enteros donde los números "se envuelven" después de alcanzar cierto valor llamado módulo. Es como un reloj: después de las 12 horas, volvemos a 1.
El módulo $m$ debe ser un número natural mayor que 1:
En un reloj de 12 horas, $7 + 8 = 15$ se convierte en $7 + 8 \equiv 3 \pmod{12}$.
Esto se debe a que $15 - 3 = 12$, y 12 es divisible por 12.
Los números se distribuyen en 5 posiciones (0, 1, 2, 3, 4).
La aritmética modular está íntimamente relacionada con la división de enteros. Cuando dividimos un número $a$ entre $m$, obtenemos:
En esta ecuación:
Por lo tanto, $a \equiv r \pmod{m}$, ya que $a - r = m \cdot q$ es divisible por $m$.
Para $a = 17$ y $m = 5$:
Por lo tanto, $17 \equiv 2 \pmod{5}$.
Todo número es congruente consigo mismo.
La congruencia funciona en ambas direcciones.
Las congruencias se pueden encadenar.
La suma modular conserva la propiedad de congruencia. Podemos sumar los restos módulo $m$ de los números en lugar de los números completos.
Al igual que con la suma, podemos multiplicar los restos módulo $m$ de los números en lugar de los números completos.
En la multiplicación modular, podemos cancelar factores comunes solo si el factor que cancelamos es coprimo con el módulo. Es decir:
Si $\gcd(c, m) \neq 1$, la cancelación no es válida y puede llevar a resultados incorrectos.
Para calcular potencias grandes módulo $m$, podemos reducir la base módulo $m$ antes de realizar la exponenciación, lo que simplifica enormemente el cálculo.
Nota: En lugar de calcular $11^4 = 14641$ y luego dividir por 7, podemos calcular $4^4 = 256$ que es mucho más manejable.
El inverso multiplicativo de $a$ módulo $m$ es un entero $a^{-1}$ tal que $a \cdot a^{-1} \equiv 1 \pmod{m}$. Este inverso existe si y solo si $\gcd(a, m) = 1$. Se puede encontrar usando el Algoritmo de Euclides Extendido, que halla enteros $x$ e $y$ para la identidad de Bézout: $ax + my = \gcd(a,m)$. Si el $\gcd$ es 1, entonces $ax \equiv 1 \pmod{m}$, y $x$ es el inverso.
Una ecuación lineal de congruencia tiene la forma $ax \equiv b \pmod{m}$. El objetivo es encontrar todos los valores de $x$ que satisfacen la ecuación.
La ecuación $ax \equiv b \pmod{m}$ tiene solución si y solo si $d = \gcd(a, m)$ divide a $b$. Si esta condición se cumple, existen exactamente $d$ soluciones incongruentes módulo $m$.