¿Qué son las congruecias en Z+módulo M?

Definición de congruencia

Dado m ∈ Z , m> 1, se dice que a, b ∈ Z son congruentes módulo m si y sólo si m|(a-b). Se denota esta relación como a ≡ b (mod m). m es 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ódulo m.

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 Z_m 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 Z_m, donde r es el resto de dividir a entre m.Por lo tanto, el conjunto Z_m es finito y tiene m elementos: Z_m = { [0]_m, [1]_m, ... , [m-1]_m}, donde la clase [i]_m representa al conjunto de todos los enteros que son congruentes con i 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 Z₇, 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 (mod m). Entonces se cumple que:

1. a + c ≡ b + d (mod m)
2. 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 Z_m: