Congruencia কী?

Ejemplo 6.19 (La prueba del nueve)

La compatibilidad con $+$ y $\times$ es un método de comprobación tan viejo como el comercio. Como $10 \equiv 1 \pmod 9$, todo entero es congruente módulo $9$ con la suma de sus cifras (se demuestra en el Ejercicio 6.2). Para comprobar la afirmación $1234 \times 567 = 699\,678$: las sumas de cifras dan $1234 \equiv 1$ y $567 \equiv 18 \equiv 0 \pmod 9$, luego el producto debe ser $\equiv 1 \times 0 = 0$; y, en efecto, $6 + 9 + 9 + 6 + 7 + 8 = 45 \equiv 0$. La comprobación pasa (y el producto es de hecho correcto). Si alguien hubiese dado $699\,478$, la suma de cifras $43 \equiv 7 \not\equiv 0$ lo delataría al instante. El test es de un solo sentido — caza el error salvo que el propio error sea múltiplo de $9$ —, que es exactamente la lección de los seudoprimos del Ejemplo 6.24 en miniatura: las comprobaciones por congruencias refutan, no certifican.

Ejemplo 6.21 (Invertir $7$ módulo $26$)

Como $\gcd(7, 26) = 1$, la clase de $7$ es invertible módulo $26$. Euclides extendido:

y después hacia atrás:

Por tanto $7 \times (-11) \equiv 1 \pmod{26}$, es decir, $7^{-1} \equiv -11 \equiv 15 \pmod{26}$; comprobación: $7 \times 15 = 105 = 4 \times 26 + 1$. Con el inverso en la mano, cualquier congruencia $7x \equiv c \pmod{26}$ se resuelve con una multiplicación: $x \equiv 15c$. Esta inversión mecánica es el caballo de batalla de la aritmética modular — y de los protocolos de clave pública mencionados en el Observación 6.27, donde los módulos tienen cientos de cifras pero el algoritmo es exactamente este.

Ejemplo 6.22 (Cuando el coeficiente no es invertible)

Resuélvase $12x \equiv 8 \pmod{20}$. Aquí $\gcd(12, 20) = 4$, así que $12$ no es invertible módulo $20$ — pero la ecuación sigue siendo tratable. La congruencia dice que $20 \mid 12x - 8$; dividiendo toda la relación por $4$ (divisor de los tres ingredientes), equivale a $5 \mid 3x - 2$, es decir,

Ahora $\gcd(3, 5) = 1$ y $3^{-1} \equiv 2 \pmod 5$ ($3 \times 2 = 6 \equiv 1$), luego $x \equiv 4 \pmod 5$: las soluciones son $x \equiv 4, 9, 14, 19 \pmod{20}$ — cuatro clases módulo $20$, tantas como el mcd. (Si el miembro derecho no hubiese sido divisible por $4$, por ejemplo $12x \equiv 6 \pmod{20}$, no habría ninguna solución: el miembro izquierdo es siempre $\equiv 0 \pmod 4$.) Forma general: $ax \equiv b \pmod n$ tiene solución si y solo si $\gcd(a, n) \mid b$, y entonces tiene exactamente $\gcd(a, n)$ clases de soluciones — divídase todo por el mcd e inviértase.