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 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 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 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:

  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 Zm:

Aritmética en Zm

Definición

En Zm podemos 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:

  1. [a] + [b] = [a+b]
  2. [a] . [b] = [a.b]

Propiedades

  1. Son operaciones cerradas, conmutativas y asociativas
  2. Cumplen la propiedad distributiva
  3. Tienen elemento neutro. [0] es el elemento neutro para ( Zm , + ) y [1] es el elemento neutro para ( Zm , . )
  4. En el caso de ( Zm , + ) existe el elemento opuesto: -[a] = [-a]
  5. Propiedad cancelativa para ( Zm , . ) : si [a].[c] = [b].[c] en Zm, entonces [a] = [b] en Z(m/mcd (m,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:

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 12. Si queremos, por ejemplo, hallar el inverso del [5], tenemos que mediante Euclides:

12= 5.2 + 2

5= 2.2 + 1

2= 1.2

Luego recorriendo el camino inverso:

1= 5 - 2.2 = 5 - 2(12 - 5.2)= 5 - (2.12 - 5.4)= 5.5 -2.12 ⇒ [5] es el inverso módulo 12 de [5].

Las operaciones en aritmética en Zm

Aparte de la suma y el producto, pueden definirse operaciones derivadas como la resta ([a]-[b] consiste en sumar a [a] el opuesto de [b]) o como la exponenciación modular ([c]n = [cn] siendo n un entero positivo.)

Respecto a la división módulo m, se definiría [a]/[b] como el producto del dividendo [a] por el inverso del divisor [b]. Es decir, [a] / [b] = [a].[b]-1. Como ya se ha visto antes, en general no todos los elementos en Zm tienen inverso. Por lo tanto no estará definida la división en Zm salvo para los casos en los que mcd (b,m) = 1

Nota: Para mayor comodidad, a partir de ahora cuando se hable de aritmética en Zm, prescindiremos de la notación con clases de equivalencia y usaremos los representantes 0 ,1, 2, ... m-1 para referirnos a las clases de residuos [0]m, [1]m, [2]m... Así pues en Z11 escribiremos 7 + 5 = 1 en lugar de [7] + [5] = [1]. También con la expresión 7 + 5 = 1 estaremos indicando que 7 + 5 ≡ 1 (mod 11).

Esta notación simplificada es la que se utilizará en el applet de ejemplo que viene a continuación.

Las tablas de las 4 operaciones en aritmética modular

Correr aplicación Aplicación de ejemplo: Operaciones en aritmética modular

La exponenciación en aritmética modular

En aritmética módulo m la exponenciación modular es menos costosa de realizar que en la aritmética entera. Nótese que a.b mod m = [ (a mod m) (b mod m)] mod m, y que por grande que sea el exponente, nunca es necesario multiplicar por enteros mayores que m.

Además hay un método que nos permite ahorrar pasos de cálculo.La forma más obvia para calcular por ejemplo, 1226 (mod 23) es multiplicar por 12 un total de 25 veces, reduciendo módulo 23 tras cada multiplicación. Pero un método más eficiente que solo necesita seis multiplicaciones está a nuestra mano si nos damos cuenta de lo siguiente:

122=144=6 (mod 23)
124=62=36=13 (mod23)
128=132=169=8 (mod 23)
1216=82=64=18 (mod 23)

Con esto hemos hecho cuatro cuadrados, y como podemos descomponer el exponente en potencias de 2, así 26=16+8+2, y podemos reescribir el cálculo anterior como:

1226=12(16+8+2)
=1216*128*122
=18*8*6=864= 13 (mod 23)

Nuestro algoritmo consiste pues en descomponer el exponente como potencias de 2, es decir, escribirlo en base 2 y multiplicar sucesivos cuadrados del entero base de la exponenciación por cada dígito binario del exponente que sea un "1". En el ejemplo anterior, el exponente es 26= (11010)2

Este applet nos muestra este algoritmo para calcular an mod m de esta forma más rápida:

Correr aplicación Aplicación de ejemplo: La exponenciación modular hecha fácil

Anterior Arriba Siguiente