Definición de congruencia
Dado m ∈ Z , m> 1, se dice que a, b ∈ Z son congruentes módulo msi y sólo si m|(a-b). Se denota esta relación como a ≡ b (mod m). mes el módulo de la congruencia.
Es importante darse cuenta de que si m divide a a-b, esto supone que ambos a y b tienen el mismo resto al ser divididos por el módulom.
Ejemplos: 23≡2 mod 7 (porque 23=3.7 + 2), y -6≡1 mod 7 (porque -6= -7.1 +1)
La relación de congruencia como equivalencia. El conjunto de residuos.
La relación de congruencia módulo m es una relación de equivalencia para todo m ∈ Z. Es decir, cumple las propiedades reflexiva, simétrica y transitiva. Como en toda relación de equivalencia, podemos definir el conjunto cociente de las clases de equivalencia originadas por la relación de congruencia. En este caso la relación clasifica a cualquier entero a según el resto obtenido al dividirlo por el módulo m.
Llamaremos Zm al conjunto cociente de Z respecto de la relación de congruencia módulo m. A la clase de equivalencia de un elemento a ∈Z se la denota por [a]m o simplemente [a].
Para todo a∈Z se tiene que [a] = [r] en Zm, donde r es el resto de dividir a entre m.Por lo tanto, el conjunto Zm es finito y tiene melementos: Zm = { [0]m, [1]m, ... , [m-1]m}, donde la clase [i]mrepresenta al conjunto de todos los enteros que son congruentes coni mod m. A este conjunto cociente se le conoce como el conjunto de restos o residuos (módulo m)
Ejemplo: siguiendo con el ejemplo anterior, está claro que en Z7, el número entero 9, el 16 y el 23 pertenecen todos a la clase [2], y que el entero -6, el 1 y el 8 pertenecen a la clase [1]
Compatibilidad de la relación de congruencia con la suma y el producto
Sean m ∈ N y a, b, c, d ∈ Z tales que a ≡ b (mod m) y c ≡ d (modm). Entonces se cumple que:
- a + c ≡ b + d (mod m)
- a . c ≡ b . d (mod m)
Consecuentemente, el resto de la suma es congruente con la suma de restos, y el resto del producto es congruente con el producto de restos. Además podremos sumar y multiplicar clases de equivalencia (residuos) porque es indiferente el representante que se elija de cada clase a la hora de operar: el resultante de la operación siempre será un representante de la misma clase resultado.
Vamos ahora a definir la aritmética módulo m o aritmética en Zm:
