La aritmética modular es aritmética sobre un círculo. Dos números son congruentes módulo n si difieren en un múltiplo de n. Un reloj hace aritmética mod 12: 10 horas después de las 5 son las 3, no las 15. Esta idea sencilla sustenta toda la criptografía moderna, las funciones hash, los códigos correctores de errores y gran parte de la teoría de números.
Cada fila y columna contiene {0,1,2,3,4} exactamente una vez. Los cinco elementos forman un grupo cerrado bajo la suma mod 5. Rojo: sumas que dan la vuelta (≥5).
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
La aritmética modular define la congruencia: a es congruente con b módulo n si n divide a a-b. Gauss la sistematizó en 1801. Sustenta toda la criptografía moderna de clave pública: el cifrado RSA se basa en el Pequeño Teorema de Fermat, que establece que a^(p-1) es congruente con 1 mod p para cualquier primo p que no divida a a. Las funciones hash usan operaciones modulares para mapear entradas grandes a salidas de tamaño fijo. Los enteros módulo n forman un anillo completo, y cuando n es primo, un cuerpo finito.