Congruencias y aritmética modular

La relación de congruencia

Si hoy es lunes, dentro de $15$ días será martes, y dentro de $1000$ días será domingo: para saberlo no hace falta contar los días uno por uno, porque basta el resto de dividir el número de días entre $7$. Del mismo modo, $5$ horas después de las $9$ son las $2$ en un reloj de $12$ horas, y la última cifra de un producto depende solo de las últimas cifras de los factores. En los tres casos se calcula con restos y se olvida el cociente. La clase sobre divisibilidad y división con resto repartió los enteros en clases según el resto que dejan al dividirlos entre un natural, y demostró que el resto de una suma, de un producto y de una potencia depende solo de los restos de los datos. Esta clase da a esas observaciones un lenguaje propio, el de las congruencias, que Gauss introdujo en 1801 en sus Disquisitiones Arithmeticae, y lo convierte en un instrumento de cálculo. Como en esa clase, los enteros se usan anticipados, con las reglas de su aritmética y de su orden que se fundamentan en la clase sobre los números enteros.

Definición (congruencia). Sea $n$ un natural. Dos enteros $a$ y $b$ son congruentes módulo $n$ si $n$ divide a su diferencia $a - b$. Se escribe $a \equiv b \pmod{n}$ y se lee «$a$ es congruente con $b$ módulo $n$»; el natural $n$ se llama módulo de la congruencia.

Así, $17 \equiv 2 \pmod{5}$, porque $17 - 2 = 15$; $-3 \equiv 9 \pmod{4}$, porque $-3 - 9 = -12$; y un entero es par exactamente cuando es congruente con $0$ módulo $2$. Que $a$ sea múltiplo de $n$ se escribe ahora $a \equiv 0 \pmod{n}$. Con el módulo $1$ todos los enteros son congruentes entre sí, porque $1$ divide a todo entero; ese caso carece de interés, y en los ejemplos el módulo será al menos $2$. El signo $\equiv$, de tres trazos, recuerda al de la igualdad porque, como se verá, la congruencia se comporta en casi todo como ella; la excepción, la división, ocupará la sección sobre los inversos.

La definición por la diferencia es la más cómoda para demostrar, pero la intuición de los ejemplos iniciales es la del resto. La proposición siguiente asegura que ambas dicen lo mismo; su contenido se observó ya, en otra forma, en la clase sobre la divisibilidad, al fundamentar los criterios de divisibilidad, y aquí se demuestra con todos sus pasos.

En particular, todo entero es congruente módulo $n$ con su resto, que es uno de los $n$ enteros $0, 1, \ldots, n - 1$, y con uno solo de ellos, porque dos de esos enteros son sus propios restos y, si son distintos, dejan restos distintos. Calcular módulo $n$ consiste en reemplazar cada número por un representante cómodo de su columna: el resto, o a veces un número negativo pequeño, como $-1$ en lugar de $n - 1$.