Congruencia modular

La idea es la del reloj: a las 15 h y a las 3 h la manecilla está en el mismo sitio, porque \(15\equiv3\pmod{12}\). Todo entero es congruente módulo \(m\) con exactamente un residuo entre 0 y \(m-1\), llamado \(a\bmod m\). Por eso \(17\equiv5\pmod6\) y \(-7\equiv3\pmod5\): el residuo nunca es negativo. La congruencia es reflexiva, simétrica y transitiva, así que parte los enteros en \(m\) clases de equivalencia.

Lo útil es que la congruencia respeta las operaciones: si \(a\equiv b\) y \(c\equiv d\pmod m\), entonces \(a+c\equiv b+d\), \(a-c\equiv b-d\) y \(ac\equiv bd\). Así se pueden reducir los números antes de operar: \(2^{10}\bmod7\) se obtiene de \(2^3\equiv1\), sin calcular 1024. Con ello se hallan últimas cifras, se demuestra que un cuadrado deja residuo 0 o 1 módulo 4 y se justifican los criterios de divisibilidad entre 3 y 9.

La división es la excepción: de \(ac\equiv bc\) no se puede concluir \(a\equiv b\) (en módulo 6, \(4\cdot1\equiv4\cdot4\)). Solo se cancela \(c\) cuando \(\gcd(c,m)=1\), y entonces \(c\) tiene un inverso módulo \(m\) que se calcula con el algoritmo de Euclides extendido. Un error común es confundir la congruencia \(\equiv\) con la igualdad: \(a\equiv b\pmod m\) afirma una propiedad de la diferencia, no que los números sean iguales.