La aritmética modular permite sumar, restar, multiplicar y elevar potencias manteniendo los resultados dentro de un conjunto finito de residuos. Sus reglas hacen posibles cálculos eficientes en ciclos, validaciones y criptografía.
Una vez que sabemos que dos enteros pueden ser congruentes, podemos operar con sus clases de residuos. La idea práctica es simple: realizar una operación y conservar solamente el resto al dividir por el módulo.
Sin embargo, esta simplicidad tiene una excepción importante: la división modular no funciona como la división ordinaria. Entender qué operaciones siempre son válidas y cuándo existe un inverso evita muchos errores al programar.
Módulo m, cada entero puede reemplazarse por uno de los residuos 0, 1, ..., m - 1. Por ejemplo, módulo 7 podemos reemplazar 31 por 3, porque 31 ≡ 3 (mod 7).
Elegir el residuo canónico facilita la lectura de los cálculos, pero cualquier número congruente sirve como representante de la misma clase.
Para residuos a y b módulo m, las operaciones se definen reduciendo el resultado:
Estas definiciones son consistentes: si cambiamos a o b por números congruentes, el residuo final no cambia. Esa propiedad permite reducir durante el cálculo, no solo al final.
Para sumar módulo m, se suma normalmente y luego se toma el residuo. En un reloj de 12 horas, avanzar 8 horas desde las 7 equivale a calcular 7 + 8 módulo 12.
La suma modular es asociativa y conmutativa, igual que la suma de enteros. El elemento neutro es 0, porque a + 0 ≡ a (mod m).
Restar módulo m equivale a sumar el opuesto aditivo. El opuesto de a es el residuo que, sumado a a, da 0 módulo m.
Todo residuo tiene opuesto aditivo. Por eso la resta siempre está definida en aritmética modular, a diferencia de la división.
La multiplicación modular se calcula multiplicando y reduciendo. Podemos reducir cualquiera de los factores antes de multiplicar.
La segunda cuenta evita multiplicar 31 por 52. Esta reducción temprana es correcta gracias a que las congruencias se preservan al multiplicar.
Si a ≡ r (mod m) y b ≡ s (mod m), entonces a + b ≡ r + s y ab ≡ rs (mod m). En términos de programación, es seguro normalizar cada resultado intermedio.
La técnica es útil cuando los números crecen rápido, como ocurre con productos repetidos, hashes polinómicos o potencias.
function modulo(a, m) {
if (!Number.isInteger(m) || m <= 0) throw new Error("m debe ser positivo");
return ((a % m) + m) % m;
}
function sumarMod(a, b, m) {
return modulo(modulo(a, m) + modulo(b, m), m);
}
function restarMod(a, b, m) {
return modulo(modulo(a, m) - modulo(b, m), m);
}
function multiplicarMod(a, b, m) {
return modulo(modulo(a, m) * modulo(b, m), m);
}
console.log(sumarMod(17, 9, 5)); // 1
console.log(restarMod(2, 5, 7)); // 4
console.log(multiplicarMod(31, 52, 7)); // 2Para enteros pequeños, esta implementación es clara y suficiente. Más adelante veremos por qué los límites de precisión de JavaScript requieren precauciones con valores muy grandes.
Una tabla permite ver que la suma modular siempre permanece dentro del conjunto de residuos.
| + mod 4 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 |
| 1 | 1 | 2 | 3 | 0 |
| 2 | 2 | 3 | 0 | 1 |
| 3 | 3 | 0 | 1 | 2 |
Por ejemplo, la última fila muestra que 3 + 1 ≡ 0 y 3 + 2 ≡ 1 módulo 4. La tabla tiene el mismo comportamiento cíclico que un contador que vuelve a cero.
Una potencia modular es el residuo de una potencia ordinaria. La reducción de cada producto impide que los números intermedios crezcan innecesariamente.
Al haber una cantidad finita de residuos, las potencias forman ciclos o alcanzan patrones repetidos. Esto es una de las razones por las que la aritmética modular es tan útil en algoritmos.
Calcular an multiplicando a por sí mismo n veces requiere n multiplicaciones. La exponenciación por cuadrados usa la representación binaria del exponente y necesita aproximadamente log2(n) iteraciones.
function potenciaMod(base, exponente, m) {
if (!Number.isInteger(exponente) || exponente < 0) {
throw new Error("el exponente debe ser un entero no negativo");
}
let resultado = 1;
let factor = modulo(base, m);
while (exponente > 0) {
if (exponente % 2 === 1) resultado = multiplicarMod(resultado, factor, m);
factor = multiplicarMod(factor, factor, m);
exponente = Math.floor(exponente / 2);
}
return resultado;
}
console.log(potenciaMod(3, 13, 7)); // 3Cada vez que el exponente es impar, se incorpora el factor actual al resultado. Después se eleva el factor al cuadrado y se divide el exponente por 2 usando división entera.
En enteros, dividir entre b significa multiplicar por 1/b. En aritmética modular, una división por b solo tiene sentido si existe un número que multiplicado por b dé 1 módulo m. Ese número se llama inverso multiplicativo de b.
No todos los residuos tienen inverso. Por eso no debemos traducir una división ordinaria a código modular sin verificar esta condición.
Módulo 7, el inverso de 3 es 5, porque 3 · 5 = 15 y 15 ≡ 1 (mod 7). En consecuencia, dividir por 3 módulo 7 equivale a multiplicar por 5.
Cuando el módulo es primo, todos los residuos no nulos tienen inverso. Con módulos compuestos, algunos residuos no lo tienen.
Un entero a tiene inverso módulo m si y solo si su máximo común divisor con m es 1. Se dice entonces que a y m son coprimos.
El algoritmo de Euclides, que veremos en el próximo tema, calcula el máximo común divisor de forma eficiente y permite decidir esta cuestión.
Para módulos pequeños se puede probar cada residuo. Este método ilustra la definición, aunque no es adecuado para módulos enormes.
function inversoPorBusqueda(a, m) {
a = modulo(a, m);
for (let candidato = 1; candidato < m; candidato++) {
if (multiplicarMod(a, candidato, m) === 1) return candidato;
}
return null; // no existe inverso
}
console.log(inversoPorBusqueda(3, 7)); // 5
console.log(inversoPorBusqueda(2, 8)); // nullMás adelante reemplazaremos la búsqueda por el algoritmo extendido de Euclides, que encuentra el inverso con mucha mayor eficiencia cuando existe.
Para resolver ax ≡ b (mod m), si a tiene inverso se multiplica ambos lados por a-1. Por ejemplo, para 3x ≡ 4 (mod 7), usamos que el inverso de 3 es 5.
Si a no tiene inverso, la ecuación puede no tener solución o tener más de una clase de soluciones. Ese caso depende del máximo común divisor entre a y m.
Los residuos módulo m están cerrados bajo suma, resta y multiplicación: al operar dos residuos y reducir, obtenemos otro residuo válido entre 0 y m - 1.
La división no tiene esta garantía: por ejemplo, 1 no puede dividirse por 2 módulo 6, pues 2 no posee inverso. Esta diferencia separa a los módulos compuestos de los casos más simples con módulo primo.
Un hash polinómico combina los valores de los caracteres y reduce cada paso por la capacidad de una tabla. La reducción mantiene el índice dentro de un rango fijo.
function hashSimple(texto, capacidad) {
let hash = 0;
const base = 31;
for (const caracter of texto) {
hash = sumarMod(multiplicarMod(hash, base, capacidad), caracter.charCodeAt(0), capacidad);
}
return hash;
}
console.log(hashSimple("hola", 101)); // un índice entre 0 y 100Este ejemplo sirve para aprender la técnica, no para seguridad. Las funciones hash criptográficas tienen requisitos mucho más estrictos y deben provenir de bibliotecas confiables.
Muchos protocolos y formatos acumulan una suma de bytes y conservan un residuo. Si el emisor y el receptor no obtienen el mismo resultado, saben que hubo una alteración o un error accidental.
Una suma de comprobación simple detecta algunos errores, pero no ofrece protección criptográfica contra modificaciones intencionales. Para seguridad se usan mecanismos diseñados para ese fin.
Los valores Number de JavaScript representan exactamente los enteros solo hasta Number.MAX_SAFE_INTEGER. Si un producto excede ese límite, el resto puede ser incorrecto debido al redondeo de punto flotante.
function moduloBigInt(a, m) {
if (m <= 0n) throw new Error("m debe ser positivo");
return ((a % m) + m) % m;
}
const resultado = moduloBigInt(12345678901234567890n * 9876543210987654321n, 1000000007n);
console.log(resultado);Con BigInt debe usarse el sufijo n y no se pueden mezclar valores Number y BigInt en la misma operación. Es una precaución esencial en criptografía y cálculos de gran tamaño.
Number cuando los productos exceden el rango de enteros seguros.BigInt evita pérdidas de precisión.Las operaciones modulares convierten cálculos potencialmente grandes en procesos sobre un conjunto finito de residuos. En el próximo tema estudiaremos el algoritmo de Euclides, la herramienta clásica para hallar máximos comunes divisores y determinar cuándo existen inversos.