Congruencias

Congruencias en Z módulo m. La aritmética en Zm
La relación de congruencia
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 elmó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 clasesde 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 res el resto de dividir a entre m.Por lo tanto, el conjunto Zm es finito y tiene m elementos: Zm = { [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 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 (mod m). Entonces se cumple que:
i. a + c ≡ b + d (mod m)
ii. a . c ≡ b . d (mod m)
Consecuentemente, el resto de la suma es congruente con la suma de restos, yel 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:
Definición
En Zmpodemos definir dos operaciones binarias internas:
+ , . : Zm x Zm⇒ Zm
que llamamos suma y producto, y están definidas de la siguiente manera, para cualesquiera a, b ∈ Z:
I. [a] + [b] = [a+b]
II. [a] . [b] = [a.b]
Propiedades
i. Son operaciones cerradas, conmutativas y asociativas
ii. Cumplen la propiedad distributiva
iii. Tienen elemento neutro. [0] es el elemento neutro para ( Zm , + ) y [1]es el elemento neutro para ( Zm , . )
iv. En el caso de ( Zm , + ) existe el elemento opuesto: -[a] = [-a]
v. Propiedad cancelativa para ( Zm , . ) : si [a].[c] = [b].[c] en Zm, entonces [a] = [b] en Z(m/mcd (m,c))
o Un caso especial es cuando mcd (m,c)=1 , ya que entonces se cumple la propiedad cancelativa para el producto en Zm: si [a][c] = [b][c] en Zm ⇒ [a] = [b] en Zm
o Si m es primo,(Zm, .) tendrá la propiedad cancelativa del producto para todo c
Elementos invertibles o unidades de Zm
Se dice que [a] es invertible en Zm si existe un [b] en Zm tal que [a][b]=[1]. Ese elemento [b] será el inverso de [a] en Zm, y se denota como [a]-1.
Proposición:
o [a] es invertible en Zm ,si y sólo si
o existe [b] ∈ Zm tal que [a][b] = [1] en Zm ,si y sólo si
o existen b, k ∈ Z tales que ab+ km = 1 ,si y sólo si
o mcd(a,m)= 1
Si [a] es invertible puede por tanto calcularse su inverso [a]-1 mediante el algoritmo de Euclides. Además se puede asegurar que si existe el inverso de un elemento en módulo m, es único.
Por ejemplo, en Z12 sólo 1, 5, 7 y 11 son primos relativos al módulo 12, por lo tanto sólo [1], [5], [7] y [11] son los enteros que tienen inverso en aritmética módulo...