Grupos de potencias en Zn (1) - Gaussiano de un elemento.

Índice o gaussiano de un resto en Z_n

Iniciamos hoy el desarrollo de toda una teoría perteneciente a la Aritmética Modular, la del orden, índice o gaussiano de un elemento, subgrupos engendrados y raíces primitivas.

Teoría previa

Resumimos brevemente la teoría previa que es conveniente conocer antes de seguir esta serie de entradas:

Comenzamos con la estructura Z_m formada por los restos posibles al dividir un número entre m. Ya sabes que este conjunto es la base de la Aritmética Modular (o del reloj)

Puedes repasar las páginas

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

Este conjunto Z_m con la suma y la multiplicación forma un anillo cíclico de m elementos. Por esta estructura cíclica se pensó en llamarles anillos por primera vez. Es un anillo con unidad, por lo que puede contener 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). Esta ecuación se sabe que 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. Si 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 (http://hojaynumeros.blogspot.com.es/2012/06/la-herencia-de-euclides-1-el-algoritmo.html).
•  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 (por ser finito y cíclico) para la multiplicación, 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(m).
Se cumple el llamado Teorema de Euler

 a^j(m) º1 (mod m)

para todo a primo con m o unidad.

Orden multiplicativo, índice o gaussiano de un elemento

Dado un elemento inversible a, llamaremos orden (o índice o gaussiano) de ese elemento al mínimo número entero tal que a^rº1. Según el teorema anterior, ese valor existe y puede ser j(m) y todos sus múltiplos. 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). Toda potencia que sea igual a 1 tendrá un exponente múltiplo de ese orden. Hay muchas formas de representar el orden o gaussiano. Aquí por comodidad tipográfica representaremos el gaussiano de N respecto al módulo M como G(N,M)
Podíamos habernos ahorrado el razonamiento anterior recordando el Teorema de Lagrange para grupos, que afirma que el orden de un subgrupo H es divisor del orden del grupo G. En este caso este último es j(m) y como las potencias de a forman un grupo monógeno, su orden será divisor de j(m).

Vemos algunos ejemplos:

Orden de 5 módulo 8: Como 5 es primo con 8 y j(8)=4, el orden podrá ser 2 o 4: 5^2=25º1 (8, luego el orden de 5 con módulo 8 es 2, o G(5,8)=2

Orden del 3 respecto al 7: j(7)=6, luego el orden podrá ser 2, 3 o 6. Probamos: 3^2=9º2 (7, 3^3=27º1 (7, 3^6=729º1 (7,  luego el orden o gaussiano de 3 es 6, G(3,7)=6

Estudio con hoja de cálculo

Deseamos desarrollar este tema con calma y en varias entradas. Así que nos pararemos un poco, con la ayuda de una hoja de cálculo:

http://www.hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm#gaussiano

Distinguiremos, en principio, tres niveles de complejidad en el descubrimiento del gaussiano de un número.

NIVEL 1

La hoja funciona sólo con las fórmulas de celdas, sin macros. Para ello basta escribir el número N y el módulo M, y calcular en columna las potencias de N en el grupo de las unidades Z*m. En la hoja hemos incluido el cálculo del MCD(N,M), que ha de ser 1 y, en caso contrario, se avisa del error.
En la imagen hemos escrito dos números no primos entre sí y la hoja nos avisa:

Simultáneamente, en las columnas del NIVEL 1, se construyen las potencias para ver cuál de ellas es igual a 1, con lo que obtendremos el gaussiano de N. A continuación reproducimos el cálculo correspondiente a 5 módulo 13:

A simple vista se descubre que el gaussiano de 5 módulo 13 es 4, porque es el mínimo exponente al que hay que elevar 5 para obtener resto 1 módulo 13.

Si te interesa cómo se construyen estas columnas, revisa la hoja, y estudia especialmente las fórmulas de las potencias, que son del tipo =SI(C15<=$G$5;RESIDUO($B$13*D14;$G$5);" ").

Podemos interpretarlas como “si el exponente no llega al módulo, multiplicamos la anterior potencia por N y calculamos el residuo”

De esta forma puedes descubrir el gaussiano por simple recorrido columna abajo hasta encontrar el primer 1. Como verás en próximas entradas, las potencias resultantes son periódicas, y su periodo es el orden del número, en este caso, 4.

NIVEL 2

Podemos simplificar las columnas si sólo probamos con los divisores de j(m) . Esto ya requiere un poco de programación, ya que la hoja no puede encontrar los datos sólo con celdas y fórmulas. Hemos creado una subrutina y un botón para descubrir el gaussiano con menos pasos. Si te interesa la programación puedes investigar en el código Visual Basic. Lo que hace es calcular la indicatriz j(m)  y recorrer sus divisores para encontrar el exponente que se convierte en gaussiano.
En la imagen están contenidas las columnas correspondientes a 7 módulo 29:

La indicatriz de 29 es 28, porque es primo. En la hoja se recorren los divisores de 28, lo que simplifica el esquema. Vemos que el primer 1 aparece en el exponente 7, luego ese será el gaussiano de 7.

NIVEL 3

Es muy útil para nuestros estudios posteriores disponer del gaussiano en forma de función que tenga como parámetros un número y un módulo y nos devuelva el orden de ese número (o cero si no es primo con el módulo)

En la parte derecha de la hoja hemos utilizado esa función para encontrar rápidamente el gaussiano de un número, en el caso de la imagen, de 7 módulo 29.

Su sintaxis  es FGAUSSIANO(NÚMERO;MÓDULO), en el ejemplo, FGAUSSIANO(7;29)

Está implementado para números pequeños. Para otros mayores sería preferible usar la descomposición factorial. La versión que insertamos a continuación no es demasiado eficiente, pero es sencilla de entender. Quizás no puedas reproducirla, por carecer de algunas funciones, pero lo importante es que entiendas su estructura.

Public Function fgaussiano(n, m)
Dim f, i, p, e
f = 0 ‘se comienza declarando nula la función, por si no son coprimos
If mcd(n, m) = 1 Then ‘son coprimos
p = n ‘inicio de las potencias del número
i = 1 ‘contador
e = euler(m) ‘encontramos la phi de Euler
While i <= e And f = 0 ‘nos detenemos cuando encontremos potencia 1
p = p Mod m ‘encontramos el residuo de la potencia
If p = 1 Then f = i ‘se encontró el orden f
p = p * n ‘siguiente potencia
i = i + 1
Wend
End If
fgaussiano = f ‘se recoge el valor de f
End Function

Gaussiano de las potencias de un resto

Supongamos que un resto a tiene como gaussiano t, es decir g(a)=t. Es fácil demostrar que el gaussiano de una potencia de a, sea por ejemplo a^k equivale a

Por ejemplo, G(4,29)=14 y si elevamos el 4 a la sexta se tendrá G(4^6,29)=14/MCD(6,14)=14/2=7
Se puede razonar así: t divide a MCM(k,t), luego se cumplirá que a^MCM(k,t) º1, por ser t el menor exponente con esa propiedad. Efectuamos unos cambios en la expresión:

a^MCM(k,t)= (a^k)^MCM(k,t)/k=(a^k)^t/MCD(k,t)º1,

luego t/MCD(k,t) puede ser el gaussiano de a^k. Sólo falta demostrar que es el más pequeño con esa propiedad. En efecto, si (a^k)^mº1, será a^kmº1, con lo que km será múltiplo de t, pero como también es múltiplo de k, lo será del MCM(k,t), luego m>= MCM(k,t)/k=t/MCD(k,t), luego esta expresión t/MCD(k,t) es la menor con esta propiedad, lo que la convierte en el gaussiano de ak.

En esta tabla tienes un ejemplo de lo demostrado. El resto 4 tiene un gaussiano igual a 14 respecto al módulo 29, luego el gaussiano de sus potencias será un divisor de 14, precisamente el MCD de 14 y el exponente. Estúdialo bien:

Observamos 6 potencias con el mismo gaussiano 14, que se corresponden con los exponentes primos con 14, que son 6, porque j(14)=6

Otras seis potencias tienen gaussiano igual a 7. Se trata de los números pares, en los que MCD(2N,14)=2, y por la fórmula anterior su gaussiano será 14/2=7

Por último, la potencia de exponente 7 presenta un gaussiano igual a 14/7=2.

Hemos descubierto que en el grupo monógeno engendrado por las potencias de un elemento de Zm no tienen que poseer el mismo valor del gaussiano, pero eso era de esperar, porque ocurre lo mismo en todo el grupo Zm.

Volveremos a este tema en la siguiente entrada.