La herencia de Euclides (3) El anillo Zm

Recordábamos en la entrada anterior la formación del anillo Z_m mediante clases de restos hasta formar el conjunto {0, 1, 2, … m-1}. Repasa estas páginas si lo deseas:

http://es.wikipedia.org/wiki/Aritm%C3%A9tica_modular
http://hojamat.es/sindecimales/congruencias/teoria/teorcong.htm
http://mathworld.wolfram.com/ModularArithmetic.html

A este conjunto Z_m se le puede dotar de la suma y el producto módulo m que lo convierten en un anillo conmutativo con unidad, que es el resto 1. Esto lo tienes en

http://personales.unican.es/ruizvc/algebra/anillos1.pdf
http://en.wikipedia.org/wiki/Ring_(mathematics)
http://hojamat.es/sindecimales/congruencias/teoria/teorcong.htm#residuales

En realidad, bastaría afirmar que Z_m es el anillo cíclico de m elementos. Busca en la Red ese concepto, que es muy sencillo. Por esta estructura cíclica se pensó en llamarles anillos por primera vez.

En los anillos con unidad son importantes los elementos inversibles. De ellos trataremos aquí.

Un elemento A de Z_m es inversible si existe otro elemento X de Z_m tal que A*Xº1 (mod m) Según vimos en la entrada anterior, esta ecuación tiene solución única siempre que A sea primo con el modulo m. Luego los restos primos con m son inversibles.

Por el contrario, si A y m tienen un divisor común, para que la ecuación tuviese solución debería ser divisor también de 1, lo que es imposible. Si el elemento A tiene divisores comunes con m, entonces A no es inversible.

Llamamos divisor de cero en un anillo a aquel elemento A que multiplicado por cierto elemento no nulo C del anillo, da un producto nulo: A*Cº0. En este caso en el que A tiene factores comunes con m, es un divisor de cero, porque si D=MCD(A,m), tendremos que A=A’*D y m=m’*D. Multiplicando A por m’ (que es no nulo) resulta Am’=A’D*m/D=A’m, que es congruente con cero, luego A*m’º0 (mod m) y por tanto divisor de cero.

Los divisores de cero no son inversibles, porque si A fuera inversible y divisor de cero, se daría una igualdad del tipo A*Cº0 con C distinto de cero, pero multiplicando por el inverso resultaría:
A^-1*A*C=C=A^-1*0 lo que daría C=0 en contra de lo supuesto.

Así que:

 Si el elemento A es primo con el módulo m, entonces es inversible, es decir, que existe algún otro elemento B tal que A*B=B*Aº1. En entradas anteriores vimos cómo encontrarlo mediante el algoritmo extendido de Euclides.

 Si el elemento A no es primo con m, es un divisor de cero, y por tanto no inversible.

Grupo de inversibles

El producto de dos inversibles A y B también lo es, y su inverso es B^-1*A^-1, ya que

 (B^-1*A^-1)*A*BºB^-1*(A^-1*A)*BºB^-1*1*Bº1

Como el 1 es inversible trivialmente y el inverso también, tenemos que los inversibles forman grupo abeliano, llamado grupo de las unidades Z*_m


Como es conocido, la función indicatriz de Euler cuenta los números menores que m y primos con él, por tanto, el cardinal del grupo Z*_m coincide con la indicatriz o función j(x) de Euler.

Si m es primo, todos los elementos son inversibles y Z_m se convierte en un cuerpo, pero yo creo que eso ya lo sabías.

La hoja que estamos usando en esta serie de entradas también nos da el grupo Z*_m de unidades de Z_m. Nos seguimos basando en el algoritmo de Euclides extendido.

Para cada elemento de Z_m se va llamando a la rutina euclides(X,m) (de ahí la ventaja de tenerla implementada como una rutina en Basic), mediante la cual se encuentra el MCD(X,m). Si es igual a 1, se escribe el inverso junto al elemento. En la imagen puedes ver el desarrollo para m=12, y nos da como elementos inversibles 1, 5, 7 y 11.

Contando los inversibles se encuentra la indicatriz de Euler, a la que volveremos próximamente.

Finalmente, a la derecha del esquema se construye el grupo multiplicativo de unidades. Observa que, como era de esperar, todos los productos pertenecen al conjunto {1, 5, 7, 11}

Con esta hoja es fácil comprender el teorema de Euler. Observa, por ejemplo, la fila que corresponde al valor 7:{7, 11, 1, 5} Esto quiere decir que 7*1º7, 7*5º11, 7*7º1 y 7*11º5. Imagina que multiplicamos las cuatro congruencias miembro a miembro:

7*1*7*5*7*7*7*11º7*11*1*5   Simplificamos entre 7*11*1*5  (porque son inversibles, si no, no se podría) y queda

7*7*7*7 º1, es decir 7⁴º1. Pero 4 es la función de Euler de 12 y de ahí la comprobación del teorema:

7 ^j(12) º1 (mod 12)

Esto no es una demostración, pero si repites lo mismo con valores generales p y m con p inversible, es fácil demostrar que p ^j(m) º1 (mod m)

Orden de un elemento

Dado un elemento inversible a, llamaremos orden de ese elemento al mínimo número entero tal que a^rº1.

Según el teorema citado, ese valor existe y puede ser j(m). Si es menor, ha de ser un divisor suyo. En efecto, supongamos que j(m) no fuera múltiplo del orden r. Entonces efectuando la división entera entre ambos quedaría j(m)=qr+s, con s<r. Aplicamos esa potencia al elemento a y obtendríamos
1ºa^j(m) ºa^qr+sºa^qr*a^sº a^s , luego a^sº1 en contra del carácter mínimo de r.

Así que el orden ha de ser un divisor de la función j(m)

Hemos incorporado a la hoja el cálculo del orden de los elementos inversibles, pero sería un buen ejercicio que los comprobaras usando la tabla de multiplicar. En la imagen puedes consultar el orden de los elementos en el caso de m=10. Observa que los cuatro son divisores de la indicatriz j(10)=4