La aritmética modular explicada
Todo el mundo hace ya aritmética modular: 10 horas después de las 8 son las 6, y el día después del domingo es el lunes. Resulta que contar volviendo a empezar en 0 después de n pasos tiene su propia aritmética completa, con reglas, sorpresas y un lugar central en la teoría de números y en la criptografía que protege internet.
Restos y congruencia
Divide a entre n y quédate solo con el resto: eso es a mod n, un número de 0 a n − 1. 26 mod 7 = 5, porque 26 = 3 × 7 + 5. Los números con el mismo resto se comportan igual mod n, por eso los llamamos congruentes: 26 ≡ 5 ≡ −2 (mod 7). Carl Friedrich Gauss introdujo esta notación en sus Disquisitiones Arithmeticae de 1801, y convirtió las antiguas observaciones de Fermat y Euler en una aritmética propia. En un reloj con n posiciones, cada número entero cae en su resto; las vueltas completas se olvidan.
Sumar, restar y multiplicar
Las tres operaciones ordinarias funcionan como siempre, y puedes reducir mod n cuando quieras: el resto de una suma es el resto de la suma de los restos, y lo mismo vale para restas y productos. Para hallar la última cifra de 37 × 48, multiplica solo las últimas cifras: 7 × 8 = 56, así que termina en 6. Esto es lo que hace que la aritmética modular sea tan útil para los ordenadores: por grandes que sean los números, los valores intermedios nunca superan n².
La división necesita un inverso
La división es la excepción. 2 × 3 ≡ 2 × 8 (mod 10), ya que ambos son 6 mod 10, pero 3 y 8 son distintos, así que no se puede simplemente cancelar el 2. Dividir entre a significa multiplicar por su inverso, el número x con a × x ≡ 1, que existe exactamente cuando a y n no tienen ningún factor común. El algoritmo de Euclides extendido lo encuentra: realiza los pasos de división de Euclides para el máximo común divisor y lleva la cuenta de un multiplicador en cada paso, de modo que, cuando el resto llega a 1, el multiplicador es el inverso. Cuando n es primo, todo número excepto 0 tiene inverso, y la división siempre funciona.
Potencias, Fermat y Euler
Las potencias se repiten. Toma las potencias de 3 mod 7: 3, 2, 6, 4, 5, 1 y luego otra vez 3. La longitud de ese ciclo es el orden de 3. En 1640, Pierre de Fermat observó que, para un primo p, a^(p − 1) ≡ 1 (mod p) siempre que p no divida a a, de modo que todo orden divide a p − 1. Leonhard Euler lo demostró y lo extendió a cualquier n, sustituyendo p − 1 por la cantidad de valores coprimos con n. Las potencias enormes se calculan con cuadrados repetidos: a, a², a⁴, a⁸ …, cada una el cuadrado de la anterior, reducida mod n, y luego se multiplican según las cifras binarias del exponente.
Dígitos de control y calendarios
La aritmética modular detecta errores. La última cifra de un ISBN-10 se elige de modo que una suma ponderada de las diez cifras sea múltiplo de 11, así que se detecta cualquier cifra errónea aislada y cualquier intercambio de dos cifras vecinas. Los números de tarjeta bancaria usan la comprobación de Luhn mod 10, y los IBAN una comprobación mod 97. Los calendarios funcionan mod 7: el día de la semana de cualquier fecha se puede calcular con unos pocos restos, y así funcionan los calendarios perpetuos y la regla del día del juicio final.
Criptografía
La criptografía moderna se basa en potencias modulares que son fáciles de calcular y difíciles de deshacer. En el intercambio de claves de Diffie–Hellman de 1976, dos personas acuerdan un secreto compartido a través de una línea abierta intercambiando potencias módulo un primo grande. RSA, publicado en 1977 por Rivest, Shamir y Adleman, cifra un mensaje m como m^e mod n, donde n es el producto de dos primos grandes, y descifra con un segundo exponente d que solo puede calcular quien conoce los dos primos. En el ejemplo de manual, n = 3233 = 61 × 53, e = 17 y d = 413: 65 se convierte en 2790, y 2790 vuelve a ser 65.
Explóralo
Abre el reloj modular para calcular a mod n, sumas, restas, productos, potencias, inversos y cocientes mod n, con números de hasta 30 cifras. Cada resultado viene con sus pasos: la división con resto, las potencias de los cuadrados repetidos o la tabla del algoritmo de Euclides extendido. El reloj dibuja cómo se llega al resultado, desde la espiral de una suma hasta el ciclo de las potencias, y para n pequeños la tabla de la operación muestra todos los resultados a la vez.
Preguntas frecuentes
¿Qué significa el símbolo ≡?
a ≡ b (mod n) indica que a y b dejan el mismo resto al dividirlos entre n o, lo que es equivalente, que n divide a a − b. 38 ≡ 2 (mod 12), porque 38 − 2 = 36 es múltiplo de 12.
¿Es mod lo mismo que el operador % en programación?
Para números positivos, sí. Para números negativos, muchos lenguajes, como C, Java y JavaScript, devuelven un resto negativo: allí −7 % 3 da −1, mientras que −7 mod 3 = 2. El operador % de Python sigue la convención matemática para n positivo.
¿Qué es el orden de un número mod n?
El menor k > 0 con a^k ≡ 1 (mod n). Solo existe cuando a y n no tienen ningún factor común. El orden de 2 mod 7 es 3, porque 2³ = 8 ≡ 1, y el orden de 3 mod 7 es 6, así que las potencias de 3 recorren todos los restos distintos de cero: 3 es una raíz primitiva mod 7.
¿Quién inventó la aritmética modular?
Los restos se usaban mucho antes, por ejemplo en el teorema chino del resto, de entre los siglos III y V, y por Fermat y Euler. Gauss la convirtió en una aritmética sistemática, con la notación de las congruencias, en 1801.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Abrir el reloj modular