miércoles, 30 de septiembre de 2015

Grupos de potencias en Zn (3) - Raíces primitivas


Raíces primitivas

En las dos entradas anteriores estudiamos el grupo multiplicativo Z*n de las unidades en Zn  (números coprimos con n). Su orden coincide con j(n). Cualquier elemento a de ese grupo engendrará a su vez un subgrupo cíclico < a > mediante sus potencias.

Por el Teorema de Lagrange, el orden de ese subgrupo será un divisor de j(n) y recibe el nombre de gaussiano g de ese elemento. Recordemos que esto implica que agº1 (mod n. También vimos que el número de generadores de < a > coincide con j(n).

En esta entrada estudiaremos las raíces primitivas, que son aquellos elementos que engendran todo Z*n , o lo que es equivalente, aquellos cuyo gaussiano coincide con j(n). Según lo que hemos recordado, el número de esas raíces primitivas puede coincidir con j(j(n)), y de hecho es así si Z*n es cíclico. Usamos la palabra “puede” pues, como ya veremos, no todos los módulos poseen raíces primitivas.

En la tercera hoja de nuestra herramienta  GAUSSIANO

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

podemos descubrir el valor del gaussiano de todos los elementos de Z*n e identificar las raíces primitivas como aquellas cuyo gaussiano sea igual a j(n). Aquí tienes la tabla correspondiente al módulo 14


Explicamos la tabla: El módulo es 14, luego existirán tantos inversibles como indique j(14)=6. En efecto, Z*14 = {1, 3, 5, 9, 11, 13}, conjunto de 6 elementos, como puedes comprobar en la tabla. Ahora bien, las raíces primitivas son generadores de todo Z*14, y su número ha de ser  j(j(14)=  j(6) = 2.

Esto es así porque si una raíz primitiva se eleva a un exponente primo con  j(m), resulta otra raíz primitiva, en virtud de la fórmula que estudiamos en una entrada anterior


En efecto, aparecen las dos raíces primitivas 3 y 5. Recorre sus potencias y comprobarás que engendran todo el grupo: 30º1, 31º3, 32º9, 33º13, 34º11 y 35º5. Igualmente, 50º1, 51º5, 52º11, 53º13, 54º9 y 55º3.

Es fácil comprender entonces que si Z*k admite raíces primitivas tendrá carácter de cíclico, ya que está generado por las potencias de un mismo elemento. Según  esto, en virtud de una propiedad general de estos grupos, Z*k estaría engendrado por cualquier potencia de una raíz primitiva cuyo exponente fuera coprimo con j(k), ya que, en caso contrario engendraría sólo un subgrupo propio de Z*k . Todas esas potencias serían también raíces primitivas, luego su número será j(j(k), como ya comprobamos más arriba. Observa esta tabla y comprueba que todas las raíces primitivas tienen exponentes coprimos con la indicatriz:




El módulo es 19, su indicatriz 18, 2 es una raíz primitiva, con gaussiano 18, y observa hacia abajo que las demás raíces primitivas son potencias del 2 con exponentes coprimos con 18: {1, 5, 7, 11, 13, 17}, seis en total.

Otros módulos no tienen raíces primitivas, como el 30:




Vemos en la tabla que ningún elemento presenta gaussiano máximo 8 (j(30)=8), luego con módulo 30 no existen raíces primitivas. Se puede demostrar (no es simple, es un conjunto de teoremas que puedes consultar en los textos especializados) que sólo poseen raíces primitivas los módulos 2, 4, pk y 2pk, siendo p primo impar y k>=1. El 30=2*3*5 no es de ninguno de estos cuatro tipos, y carece de raíces primitivas. El 14 es del tipo  2pk  y sí tiene raíces primitivas.

Para ayudarte a entender y practicar con esta situación hemos añadido dos rutinas a nuestra hoja GAUSSIANO. Una encuentra la menor raíz primitiva de un módulo m, y te avisa si no existe tal raíz. Se basa en una búsqueda sistemática desde 1 hasta m-1. Este es su código:

Public Function minraiz(m) As Variant
Dim o, g, j, mr

mr = 0: o = sacaprimos(m): g = euler(m) ‘encuentra la indicatriz y los factores primos
If m = 2 Or m = 4 Or (o = 1 And primo(1) <> 2) Or (o = 2 And primo(1) = 2 And expo(1) = 1 And primo(2) <> 2) Then
j = 1 ‘esta parte actúa si el módulo posee la factorización adecuada
While j < m And mr = 0
If fgaussiano(j, m) = g Then mr = j ‘búsqueda de la primera raíz primitiva
j = j + 1
Wend
minraiz = mr
Else
minraiz = "No tiene raíces primitivas" ‘caso en el que el módulo no tiene raíces primitivas
End If
End Function

No tienes que usar ningún botón, porque el resultado aparece automáticamente.

Por ejemplo, con módulo 40=2^3*5 nos devuelve el resultado



40 no pertenece a ninguno de los cuatros tipos de números que poseen raíces primitivas. Sin embargo, con el 98 nos resulta:



Este resultado coincide con el obtenido mediante el botón “Inicio”:

Este módulo de hoja de cálculo no te añade ningún aprendizaje nuevo, pero te lo facilita. El siguiente sí es más conceptual.

Criterio de los factores de la indicatriz

Si buscamos la indicatriz del módulo m, sea j(m), y la descomponemos en factores primos, sean estos p1, p2, p3,…(escritos sin exponentes), un resto a será raíz primitiva si se cumple


Si todas las potencias presentan restos distintos de 1, a será raíz primitiva, y si por el contrario, alguna de las potencias es congruente con 1, ese resto a no será raíz primitiva. La justificación no es muy complicada:

 Si una de las potencias es congruente con 1, el gaussiano de a sería menor que j(m), y no podría ser raíz primitiva. Por el contrario, si ninguna es congruente con 1, sí ha de serlo, ya que, en caso contrario, existiría un divisor propio de j(m), sea g, que sería el gaussiano de a y agº1 (mod m. Además, como los cocientes j(m)/pi son los divisores maximales de  j(m), uno al menos de ellos sería múltiplo o igual al gaussiano, con lo que





en contra de lo supuesto.

El siguiente módulo es una simple curiosidad y comprobación de lo anterior.



La anterior imagen se corresponde con el módulo 242, cuya indicatriz, 110, posee los factores primos 2, 5 y 11. Hemos aplicado el criterio al resto 25, y vemos que no es raíz primitiva, porque la primera potencia 2110/2 es congruente con 1.

Efectivamente, su gaussiano es casualmente ese: 110/2=55.

El siguiente ejemplo es el criterio aplicado al resto 5 respecto al módulo 37



La indicatriz de 37 es 36, con factores 2 y 3. La aplicación del criterio nos da dos potencias congruentes con 36 y 10 respectivamente, luego 5 es una raíz primitiva.

lunes, 21 de septiembre de 2015

Grupos de potencias en Zn (2) - Subgrupos cíclicos.


Subgrupos cíclicos en Zm*

Según la entrada anterior, todo elemento a perteneciente a Zm* (conjunto de inversibles del grupo multiplicativo Zm) posee  un orden o gaussiano g(a), que es el mínimo número entero tal que agº1. Ese orden siempre es divisor de  la indicatriz de Euler de m, j(m), o igual a ella.


Sabemos que las potencias de un mismo elemento a forman siempre un grupo cíclico < a >. En el caso de un elemento de Zm* estos grupos tendrán el mismo orden que el elemento que los genera, es decir g(a). En efecto, las potencias a0, a1, a2,…ag(a)-1 son todas distintas (si dos fueran iguales, al dividirlas resultaría una potencia del elemento igual a la unidad con exponente menor que g(a), en contra de la definición de g(a)). Sus productos pertenecen al conjunto, ya que si sobrepasan ag(a)  al ser este la unidad, se puede eliminar de dicho producto.

Por ejemplo, con módulo 13, el orden o gaussiano de 5 es 4, luego 50º1 (mod 13, 51º, (mod 13, 52º12º-1 (mod 13 y 53º8º-5 (mod 13 formarán un subgrupo de Z13. Lo podemos representar así:

 < 5 > = {1, 5, -1, -5}

Así que el concepto de orden de un elemento coincide aquí con el de orden del grupo cíclico que engendra. Este grupo es el más pequeño que contiene ese elemento. Según la teoría general de grupos cíclicos, será abeliano (conmutativo) y único, para un valor dado del orden.

Según los párrafos anteriores, en un subgrupo de potencias de un elemento de gaussiano g, existen  j(g) elementos con el mismo gaussiano, pero como hemos señalado que este grupo es único para ese valor de g, podremos afirmar:

El conjunto de elementos pertenecientes a Zm* con un gaussiano concreto g tiene un cardinal de  j(g).

Si volvemos al ejemplo concreto del módulo 29 que vimos más arriba, esta sería la descomposición de los elementos de Z29 según su gaussiano. Cada uno de los elementos engendrará un subgrupo de orden idéntico a su gaussiano, y todos los que compartan el mismo valor g de ese gaussiano formarán un subconjunto de j(g) elementos:


Esta tabla es muy útil para repasar lo que hemos explicado hasta ahora:

29 es primo, luego Z29* contendrá 28 elementos inversibles, y poseerán como gaussiano uno de los divisores de 28: 28, 14, 7, 4, 2 y 1. Según lo explicado, cada conjunto de elementos con el mismo gaussiano k tendrá un cardinal de j(k). En la tabla vemos que aparecen 12 elementos con gaussiano 28, y j(28)=12. Luego, tenemos 6 con gaussiano 14 y otros 6 con el valor 7. Finalmente, otros cuatro presentan los gaussianos 4, 2 y 1. Si los sumamos todos, obtenemos 28=j(29), que es el cardinal de Z29*

Con esta tabla hemos comprobado la expresión de 28 en suma de j(28)+j(14)+j(7)+j(4)+ j(2)+j(1), que es un caso de la fórmula general:


Un número entero coincide con la suma de las indicatrices de sus divisores.

Periodicidad de las potencias

Si en lugar de considerar sólo las  potencias de exponente menor que g(a) las estudiamos todas, es evidente que son periódicas, pues ak+tg(a)=ak*atg(a)=ak*1=ak

De paso hemos demostrado que el periodo de las potencias de a es precisamente g(a). Lo puedes comprobar con la hoja de cálculo que usamos en la anterior entrada

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


En la tabla figuran las potencias de 5 respecto al módulo 28. El orden de Z28*  es 12 (j(28)), el orden del 5 respecto a 28 es 6 (divisor de 12), y se produce, como puedes comprobar, una periodicidad de periodo 6.

Además, los integrantes de cada ciclo son los elementos del grupo engendrado por el elemento 5: {5, 25, 13, 9, 17, 1} En la anterior entrada descubrimos que cada elemento de este tipo de grupos tiene un gaussiano diferente, como puedes ver en la siguiente tabla:



Todos los gaussianos son divisores de 12 (j(28)).

Subgrupos generados

Ha quedado claro que las potencias de un elemento no tienen que compartir el mismo gaussiano, luego los subgrupos que vamos a recorrer ahora no tienen por qué coincidir con los conjuntos estudiados más arriba. Lo que sí queda claro es que, dentro del subgrupo engendrado por un elemento, pueden aparecer subgrupos formados a partir de una potencia con un gaussiano menor.
Hemos preparado nuestra hoja GAUSSIANO para que dado un resto en Zn*  encuentre el subgrupo que engendra mediante sus potencias. En la siguiente entrada estudiaremos los elementos que engendran todo Zn* (raíces primitivas), pero ahora los repasaremos todos. Para entenderlo mejor, estudia esta primera tabla que hemos creado, con módulo 13 y resto 11:



En la primera columna figuran las potencias de 11, que como su gaussiano es 12, posee ese número de elementos. Este es G0, el subgrupo creado por las potencias de 11 en Z13*.

Tal como vimos anteriormente, los elementos de ese grupo no han de tener gaussiano 12. De hecho aparecen todos los divisores de 12: 6, 4, 3, 2 y 1. También vimos que las potencias de cada uno de ellos forman subgrupos del principal. Según la teoría de grupos, estos son únicos para cada orden, aunque se engendren con elementos distintos. Compruébalo:

 G6: Grupo de orden 6: {4, 3, 12, 9, 10, 1} Engendrado en la tabla por 4 y 10.
 G4: Grupo de orden 4: {5, 12, 8, 1} con generadores 5 y 8
 G3: Grupo de orden 3: {3, 9, 1} engendrado por 3 y 9.
 G2: Grupo de orden 2: {12, 1} con generador 12.
 GE: Grupo trivial: {1}

Obsérvese que el número de generadores de cada subgrupo coincide con el valor de su indicatriz de Euler. Así tenemos j(6)= j(4)=j(3)=2 y por eso los primeros subgrupos poseen dos generadores. Sin embargo, como j(2)=1, el penúltimo tiene un solo generador.

Como son grupos de potencias, se cumple que si el gaussiano de a es divisor del de b, el grupo engendrado por a es subgrupo del engendrado por b.

Todas las potencias de 11 pertenecen a un grupo, y algunas a varios.

Para construir estas tablas, busca en GAUSSIANO.XLSM la hoja SUBGRUPO ENGENDRADO  y rellena tan sólo el módulo y el elemento dado. El resto lo construye la hoja. Aquí tienes otro ejemplo, con módulo 15 y elemento 7:



Indicador de un elemento

Dado cualquiera de los subgrupos que estamos estudiando, cualquier elemento de  Zn* posee una potencia perteneciente a cada uno de ellos. En efecto, dado un subgrupo S, si un elemento a pertenece a él, bastará elevarlo a 1. Si no pertenece, lo elevamos a n para engendrar la unidad, pero hay casos en los que existen otros enteros positivos k<n tales que ak pertenece a S. Al menor de ellos le llamaremos indicador de a con respecto a S. Hemos visto que puede valer 1 o n. Observa la tabla anterior: el indicador de 5 respecto al subgrupo {11, 9, 1} es 2, porque 52=11 es la potencia positiva más pequeña que pertenece al subgrupo. Igualmente, el 3 es el indicador respecto a {13, 1}.



jueves, 10 de septiembre de 2015

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


Índice o gaussiano de un resto en Zn

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 Zm 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 Zm 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 Zm es inversible si existe otro elemento X de Zm 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:




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

 aj(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 arº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ºaj(m) ºaqr+sºaqr*asºas , luego asº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 ak 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 aMCM(k,t) º1, por ser t el menor exponente con esa propiedad. Efectuamos unos cambios en la expresión:

aMCM(k,t)= (ak)MCM(k,t)/k=(ak)t/MCD(k,t)º1,

luego t/MCD(k,t) puede ser el gaussiano de ak. Sólo falta demostrar que es el más pequeño con esa propiedad. En efecto, si (ak)mº1, será akmº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.