Entender la aritmética modular de forma intuitiva (La matemática del reloj y por qué mandan los restos)

Son las nueve y un vuelo sale en cinco horas. Nadie mira la esfera del reloj y responde "las catorce". Dices las dos, y lo has hecho sin pensar, porque en la esfera de un reloj no hay ningún catorce. Las horas dan la vuelta al llegar a las doce y empiezan otra vez. Llevas haciendo aritmética modular desde que aprendiste a leer la hora; solo que nunca conociste la notación.

Eso es todo el tema. Elige un número en el que dar la vuelta, olvida cada vuelta completa y quédate solo con dónde aterrizas. Lo que hace que merezca un artículo es que este único hábito, quedarse solo con el resto, resuelve problemas que de frente parecen imposibles: la última cifra de un número de setenta dígitos, si un número enorme es divisible por 9, por qué el número de una tarjeta de crédito es válido o no, y cómo se puede revolver un mensaje para que solo lo desenrede el destinatario previsto.

Este artículo es la imagen: qué es de verdad un resto, por qué se te permite reducir antes de calcular, qué pasa con los negativos y con las potencias, y de dónde sale la única dificultad honesta, la división.

Un resto es dónde aterrizas, no lo que sobra

La definición estándar dice que $a \bmod n$ es el resto de dividir $a$ entre $n$. Es correcta y es también la razón de que el tema parezca una tarea pesada, porque "resto" suena a la chatarra que queda después de una división, algo accesorio.

Mejor imagen: una pista circular con $n$ marcas, numeradas del $0$ al $n-1$. Para hallar $a \bmod n$, sal del $0$ y camina $a$ pasos por la pista. Donde te detienes es la respuesta. Caminar 17 pasos por una pista de 5 marcas te lleva tres vueltas completas (15 pasos) y 2 pasos más, así que te detienes en la marca 2. De ahí que $17 \bmod 5 = 2$. Las vueltas completas son el cociente; donde aterrizas es el resto.

Esta imagen hace dos cosas que la definición no hace. Obliga al resto a caer siempre en el rango de $0$ a $n-1$, porque esas son las únicas marcas. Y explica por qué dos números pueden ser "el mismo" módulo $n$ aun siendo disparatadamente distintos: $2$, $17$, $102$ y $5{,}000{,}002$ se detienen todos en la marca 2 de una pista de 5 marcas. Difieren en vueltas, y la pista no recuerda las vueltas.

Los matemáticos escriben esa idea como una congruencia:

$$17 \equiv 2 \pmod{5}$$

Léelo como "17 aterriza donde aterriza el 2, en la pista de 5". La triple barra no es un signo de igualdad, porque 17 y 2 no son iguales. Dice que son intercambiables para cualquier pregunta que solo se interese por la posición en la pista. La versión precisa: $a \equiv b \pmod{n}$ significa que $n$ divide a $a - b$, que no es más que decir que los dos números difieren en un número entero de vueltas.

Sumar y multiplicar solo se fijan en dónde estás

Este es el hecho que convierte la aritmética modular en una herramienta y no en una curiosidad. Si vas a sumar dos números y después hallar el resto, puedes hallar primero los restos, sumarlos y reducir otra vez. La respuesta es idéntica. Lo mismo vale para la resta y para la multiplicación.

En la pista resulta evidente. Sumar 17 significa caminar 17 pasos, que son tres vueltas más 2. Las tres vueltas te devuelven al punto de partida y no cambian nada, así que sumar 17 tiene exactamente el mismo efecto que sumar 2. Las vueltas escondidas dentro de un número son peso muerto, y siguen siendo peso muerto a través de la suma y a través de la multiplicación, porque un múltiplo de $n$ por cualquier cosa sigue siendo un múltiplo de $n$.

Escrito del todo, con $a = qn + r$ y $b = pn + s$:

$$ab = (qn + r)(pn + s) = n(qpn + qs + rp) + rs$$

Todo lo que hay en el primer paréntesis son vueltas. Solo sobrevive $rs$, así que $ab \bmod n$ es $rs \bmod n$. Los restos llevan toda la información que la pregunta necesita.

Por eso el consejo del tema de aritmética de Math Zen dice que reduzcas paso a paso en lugar de calcular el valor completo. Supón que quieres $123 \times 456 \bmod 7$. Podrías multiplicar hasta 56,088 y hacer una división larga por 7. O puedes fijarte en que $123 = 119 + 4$, así que $123 \equiv 4$, y $456 = 455 + 1$, así que $456 \equiv 1$, y la respuesta es $4 \times 1 = 4$. Dos reducciones pequeñas sustituyen una multiplicación de cuatro cifras. El hábito es: nunca dejes que un número crezca más allá de $n$ si solo te importa su resto.

Los números negativos caminan en el otro sentido

La imagen de la pista también resuelve el caso que hace tropezar a casi todo el mundo. ¿Cuánto es $-3 \bmod 5$?

Camina 3 pasos hacia atrás desde el 0 en una pista de 5 marcas. Pasas por el 4, luego por el 3, y aterrizas en el 2. Así que $-3 \equiv 2 \pmod{5}$. Un número negativo no es más que un paseo en el sentido contrario, la misma idea que en Entender los números negativos de forma intuitiva, y el resto sigue siendo dónde aterrizas, sigue estando entre $0$ y $n-1$.

El atajo: suma vueltas hasta que el número sea positivo. $-3 + 5 = 2$. Para $-14 \bmod 5$, suma 15 (tres vueltas) y obtienes 1. Las calculadoras y los lenguajes de programación no se ponen de acuerdo sobre los restos negativos, y algunos devuelven $-4$ para $-14 \bmod 5$, así que en un examen da siempre la respuesta como la marca no negativa de la pista, y comprueba la convención de tu calculadora antes de fiarte de ella.

La resta es la misma historia. $3 - 8 \pmod{5}$ es $-5$, que es exactamente una vuelta hacia atrás, así que la respuesta es 0. O reduce primero: $8 \equiv 3$, así que $3 - 3 = 0$.

La última cifra de una potencia enorme

Este es el problema que convence a la gente de que el tema vale la pena, y es una consecuencia directa de la regla de reducir primero.

La última cifra de un número es el número módulo 10, porque las decenas, las centenas y todo lo que está por encima son múltiplos de 10 y aterrizan de vuelta en el 0 en una pista de 10 marcas. Así que "cuál es la última cifra de $7^{100}$" es la pregunta "cuánto es $7^{100} \bmod 10$", y nunca tienes que calcular $7^{100}$.

En su lugar, mira a las potencias de 7 caminar por la pista de 10, reduciendo cada vez:

• $7^1 = 7$
• $7^2 = 49 \equiv 9$
• $7^3 \equiv 9 \times 7 = 63 \equiv 3$
• $7^4 \equiv 3 \times 7 = 21 \equiv 1$
• $7^5 \equiv 1 \times 7 = 7$

En cuanto llegas al 1, el ciclo vuelve a empezar: 7, 9, 3, 1, 7, 9, 3, 1, con periodo 4. Como $100 = 4 \times 25$, la potencia centésima se sitúa al final de un ciclo completo, en el mismo lugar que $7^4$, y su última cifra es 1.

Toda base tiene un ciclo módulo 10, y la mayoría son cortos. Las potencias de 2 recorren 2, 4, 8, 6. Las de 3 recorren 3, 9, 7, 1. Las de 5 y las de 6 no se mueven nunca. El método es siempre el mismo: halla la longitud del ciclo reduciendo a medida que avanzas, divide el exponente entre la longitud del ciclo, y el resto de esa división te dice en qué punto del ciclo estás. Es la idea de los exponentes como multiplicación repetida, ejecutada en una pista circular en lugar de en una recta.

Por qué funciona la regla de la suma de cifras para el 9

Todo el mundo aprende que un número es divisible por 9 si sus cifras suman un múltiplo de 9, y casi nadie aprende por qué. La aritmética modular lo convierte en un argumento de una línea.

Diez es una vuelta más uno en la pista de 9: $10 \equiv 1 \pmod{9}$. Entonces $100 = 10 \times 10 \equiv 1 \times 1 = 1$, y toda potencia de 10 es congruente con 1 también. Así que un número como $4{,}527 = 4 \times 1000 + 5 \times 100 + 2 \times 10 + 7$ es congruente con $4 + 5 + 2 + 7 = 18 \pmod{9}$, y 18 es $0$ en la pista de 9, así que 4,527 es divisible por 9. La suma de cifras no es un truco. Es el propio número, visto módulo 9.

La regla del 3 funciona por la misma razón, porque $10 \equiv 1 \pmod{3}$ también. La del 11 viene de $10 \equiv -1 \pmod{11}$, que hace que las potencias de 10 alternen entre $1$ y $-1$ y da la suma alternada de cifras. Todas las reglas de divisibilidad que te dijeron que memorizaras son un solo hecho, "reduce las potencias de 10", aplicado a pistas distintas.

Dígitos de control: aritmética modular en tu cartera

Todo ISBN, todo número de tarjeta de crédito y todo código de barras termina con una cifra cuyo único trabajo es ser un resto.

La última cifra de un ISBN de 13 dígitos se elige para que una suma ponderada de las trece cifras, con pesos que alternan 1 y 3, sea congruente con $0 \pmod{10}$. Teclea mal una sola cifra y la suma aterriza en otro punto de la pista de 10, y el escáner la rechaza. Las tarjetas de crédito usan el algoritmo de Luhn, una ponderación algo más astuta que además detecta la mayoría de los casos en que se intercambian dos cifras contiguas, de nuevo comprobando una suma módulo 10.

Son los parientes humildes de una aplicación mucho mayor. El cifrado moderno se apoya en que elevar un número a una potencia módulo un $n$ muy grande es fácil, mientras que deshacer el proceso sin una clave secreta no lo es. La búsqueda de ciclos que hiciste arriba para $7^{100}$ es la misma operación, escalada a números de cientos de cifras, y la regla de reducir a medida que avanzas es la única razón de que se pueda calcular.

La división es donde la pista se vuelve accidentada

La suma, la resta y la multiplicación se portan en una pista exactamente igual que en la recta numérica. La división no, y aquí es donde el tema se gana su reputación.

En la recta numérica ordinaria, dividir por 4 significa multiplicar por $\tfrac{1}{4}$, el número que, por 4, da 1. En la pista de 12, ¿hay alguna marca que, por 4, aterrice en el 1? Pruébalas todas: $4 \times 1 = 4$, $4 \times 2 = 8$, $4 \times 3 = 12 \equiv 0$, $4 \times 4 = 16 \equiv 4$, y el patrón 4, 8, 0 se repite para siempre. Nunca llega al 1. Así que en la pista de 12 no existe eso de dividir por 4.

La razón es que 4 y 12 comparten un factor. Empieza con un múltiplo de 4, añade o quita vueltas de 12, y sigues teniendo un múltiplo de 4, así que nunca puedes aterrizar una unidad más allá de un múltiplo de 12. Prueba con 5: $5 \times 5 = 25 = 24 + 1 \equiv 1$, así que 5 es su propio inverso en la pista de 12 y dividir por 5 no da problemas. La regla: $a$ tiene inverso módulo $n$ exactamente cuando $a$ y $n$ no comparten ningún factor común aparte del 1.

Esa regla tiene una consecuencia llamativa. Si $n$ es primo, nada de $1$ a $n - 1$ comparte un factor con él, así que toda marca no nula tiene inverso y puedes dividir con libertad. Las pistas primas son las que tienen las cuatro operaciones en funcionamiento, y eso explica en buena parte por qué los primos, cuyo suministro garantiza la infinitud de los números primos, están en el centro de la teoría de números y de la criptografía.

De dónde provienen los errores

La aritmética modular tiene pocas piezas móviles, y los errores son igual de concretos.

El primero es reducir el exponente en lugar de la base. En $7^{100} \bmod 10$, puedes reducir 7 módulo 10 (ya lo está), y puedes reducir el exponente módulo la longitud del ciclo una vez que la conoces, pero no puedes reducir 100 módulo 10 y calcular $7^0$. Los exponentes viven en otra pista, la que tiene el tamaño de la longitud del ciclo, y mezclar las dos pistas es el error más común de este tema.

El segundo es un resto negativo. $-14 \bmod 5$ es 1, no $-4$. La misma posición en la pista, pero solo uno de los dos es el nombre convencional, y las plantillas de respuestas quieren el no negativo.

El tercero es dividir sin comprobar que hay inverso. Cancelar un factor común en los dos lados de una congruencia solo es legal si ese factor no comparte nada con el módulo. De $4 \times 2 \equiv 4 \times 5 \pmod{12}$, que es cierto porque ambos lados son 8, no puedes cancelar el 4 para concluir $2 \equiv 5$, que es falso. Las vueltas que descartas al cancelar tienen que ser vueltas de la pista original.

El cuarto es olvidarse de reducir al final. Obtener $rs = 21$ en una pista de 7 y escribir 21 no está mal, exactamente, pero tampoco es una respuesta. La respuesta es una marca de la pista, y 21 son tres vueltas, así que la marca es 0.

Dónde encaja Math Zen

El tema de aritmética de Math Zen tiene un apartado dedicado a la aritmética modular, y la progresión está construida alrededor del hábito de reducir primero, no alrededor de la notación. Los primeros problemas piden restos y congruencias sencillos con módulos pequeños, hasta que "dónde aterrizo" sea automático. Los bloques intermedios meten negativos y productos, donde la clave es reducir cada factor antes de multiplicar y dar el resto no negativo. Los bloques finales son los problemas de última cifra y de longitud de ciclo, que son los que aparecen en las pruebas de competición y en los exámenes de admisión y que castigan a quien intenta calcular la potencia completa.

Como las sesiones son cortas y los problemas vuelven a intervalos espaciados, como se describe en repetición espaciada para practicar matemáticas, la jugada de buscar el ciclo se convierte en un reflejo en lugar de en un procedimiento que consultas. Casi nadie tiene una laguna de aritmética modular que un capítulo arreglaría. Tienen una imagen, la pista, que nunca se les dibujó, y unas cuarenta repeticiones que nunca se hicieron.

La conclusión

La aritmética modular es aritmética en una pista circular con $n$ marcas. Un resto es dónde aterrizas después de caminar $a$ pasos, las vueltas completas se olvidan, y dos números son congruentes cuando aterrizan en la misma marca. Como las vueltas no aportan nada a las sumas ni a los productos, puedes reducir cada número a su resto antes de sumar o de multiplicar, y este único permiso convierte cálculos imposibles, como la última cifra de $7^{100}$, en ciclos cortos que puedes recorrer a mano. Las reglas de divisibilidad son las potencias de 10 reducidas módulo 9, 3 u 11. Los dígitos de control son restos que pillan las erratas. La división solo funciona cuando el número no comparte ningún factor con la pista, y por eso las pistas primas son especiales.

Cuando un problema modular se atasca, dibuja la pista. Pregunta dónde aterriza cada pieza, reduce a medida que avanzas, y mantén el exponente en su propia pista. La respuesta es una marca entre $0$ y $n - 1$, y la imagen te llevará allí antes que la fórmula.