Grupos de potencias en Zn (4) - Índices modulares

Índices modulares

En la entrada anterior estudiamos las raíces primitivas, elementos del grupo multiplicativo Z*_n de las unidades en Z_n (números coprimos con n), tales que su gaussiano es máximo y coincidente con j(n). Estas raíces, mediante sus potencias, engendran todo Z*_n, luego un elemento inversible cualquiera coincidirá con una potencia de la raíz primitiva. El exponente comprendido entre 0 y j(n)-1 que logra esta coincidencia recibe el nombre de índice del elemento respecto a la raíz primitiva. También es llamado logaritmo discreto.

Es decir; si a es una raíz primitiva y b un elemento inversible, existe un exponente k en el intervalo (0, j(n)-1) tal que a^kºb, y a ese exponente le llamaremos índice de b respecto a la raiz a.

Por ejemplo, el módulo 7 posee dos raíces primitivas. La raíz 3 engendra mediante potencias todos los elementos desde 1 a 6 (por ser 7 primo son todos inversibles), 3⁰º1, 3¹º3, 3²º2, 3³º6, 3⁴º4 y 3⁵º5. Cada uno de los exponentes es el índice de ese elemento.

La función índice que asigna a cada elemento inversible el exponente de la menor potencia de la raíz primitiva que lo engendra la podemos representar por ind_a(b) o simplemente ind(b) si se conoce la raíz. También podemos representarlo como un logaritmo, que en este caso recibe el nombre de logaritmo discreto. En el ejemplo anterior ind₃(6)=3, ind₃(4), ind₃(4)=4,…Si existe una raíz primitiva, todos los elementos inversibles de Z_m tendrán definido el índice.

Al ser un exponente, las propiedades del índice o logaritmo discreto son previsibles (supongamos módulo m):

El cálculo de los índices en grupos complejos no es fácil, aunque se han creado muchos algoritmos eficientes, y por eso los índices son usados en algunos sistemas criptográficos.

Aquí nos limitaremos, como siempre, a casos sencillos con los que aprender los conceptos. Hemos creado en nuestra hoja GAUSSIANO

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

un confeccionador automático de tablas de índices para un módulo dado. Sólo tienes que escribir dicho módulo, y pulsar un botón para que aparezca la tabla, si es que existen raíces primitivas. Aquí tienes la del módulo 54:

En columna aparecen los elementos inversibles de Z₅₄, que hay 18, porque  j(54)=18. En la fila superior tenemos las raíces primitivas, que por ser 54 de la forma 2p^k (2*3³), existen con seguridad, y son 6, ya que j(j(54))=6. Con ella podemos encontrar el índice de cualquier inversible. Por ejemplo, el índice de 37 respecto a 23 es 12, lo que indica que 23¹²=37.

Ecuaciones potenciales

Las tablas de índices nos pueden servir para resolver la ecuación

El comportamiento de los índices como logaritmos nos permite transformar esta ecuación en otra lineal, eligiendo cualquier raíz primitiva b y aplicando índices en ambos miembros respecto a ella.

Según la teoría de las ecuaciones lineales en Z_m, si llamamos d al MCD(n, j(m)), el índice de a ha de ser múltiplo de d para que exista solución. En ese caso basta despejar el índice de x y buscar después el valor de x en las tablas. Podíamos haber automatizado todo el proceso, pero parece que se aprende más de esta forma.

Ejemplo: Resolver x⁶º37 (mod 54

En primer lugar encontramos que j(54)=18 (ver tabla y párrafos anteriores), luego d=MCD(6,18)=6. En la tabla citada buscamos el índice de 37 respecto a la raíz primitiva 5 y encontramos que es 12. Por tanto, como 12 es múltiplo de 6, deberá existir una solución (en realidad, según las propiedades de las ecuaciones lineales, deberían aparecer 6). Tomamos índices respecto al 5:

6*ind₅(x)ºind₅(37) (mod 54 º12

ind₅(x)º12/6=2.

Buscamos en la tabla qué inversible tiene índice 2 respecto a la raíz primitiva 5, y nos resulta 25. Comprobamos:

25¹º25; 25²º25*25º31; 25³º25*31º19; 25⁴º25*19º43; 25⁵º25*43º49; 25⁶º25*49º37

Así comprobamos que 25 es una solución de la ecuación propuesta. Pero hemos asegurado que existen otras cinco soluciones, que se pueden leer en la tabla si hubiéramos usado otra raíz primitiva. Son estas: 13, 43, 31, 7 y 49. Esto completa el conjunto de seis soluciones de la ecuación propuesta.
Otras ecuaciones de ese tipo no tienen solución. Por ejemplo:

x⁷º12 (mod 49

Formamos la tabla de índices módulo 49 y vemos que ind₃(12)=11, que j(49)=42 y MCD(7,42)=7, pero 11 no es múltiplo de 7, luego no existe solución. Hemos creado una tabla con las séptimas potencias de los inversibles de Z*₄₉ y sólo nos resultan seis resultados posibles: {1, 30, 31, 18, 19, 48}, y el 12 no está entre ellos.

El ejemplo anterior nos da una pista para descubrir si un resto dado es cúbico, bicuadrado o de otro orden en un módulo dado. Por ejemplo, ¿es resto bicuadrado 15 en módulo 22? Planteamos a⁴º15 (mod 22 y analizamos:

Formamos la tabla de índices módulo 22

j(22)=10 y MCD(4,10)=2, luego ind(15) ha de ser múltiplo de 2. Según la tabla, se cumple para cualquier raíz primitiva, luego sí es un resto bicuadrado. Podemos encontrar su raíz cuarta:
4ind(a)=2, luego ind(a)=2/4 (mod 22 = 6

El 3 posee índice 6, y cumple 3⁴º15 (mod 22, luego existe la raíz bicuadrada de 15, y este valor 15 es resto bicuadrado (sólo hemos investigado una posibilidad, pero con una basta).

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 Z_n  (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 a^gº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*₁₄ = {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*₁₄, 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: 3⁰º1, 3¹º3, 3²º9, 3³º13, 3⁴º11 y 3⁵º5. Igualmente, 5⁰º1, 5¹º5, 5²º11, 5³º13, 5⁴º9 y 5⁵º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, p^k y 2p^k, 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  2p^k  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 p₁, p₂, p₃,…(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 a^gº1 (mod m. Además, como los cocientes j(m)/p_i 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 2^110/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.

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

Subgrupos cíclicos en Zm*

Según la entrada anterior, todo elemento a perteneciente a Z_m* (conjunto de inversibles del grupo multiplicativo Z_m) posee  un orden o gaussiano g(a), que es el mínimo número entero tal que a^gº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 Z_m* estos grupos tendrán el mismo orden que el elemento que los genera, es decir g(a). En efecto, las potencias a⁰, a¹, a²,…a^g(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 a^g(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 5⁰º1 (mod 13, 5¹º, (mod 13, 5²º12º-1 (mod 13 y 5³º8º-5 (mod 13 formarán un subgrupo de Z₁₃. 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 Z_m* 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 Z₂₉ 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 Z₂₉* 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 Z₂₉*

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 a^k+tg(a)=a^k*a^tg(a)=a^k*1=a^k

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 Z₂₈*  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 Z_n*  encuentre el subgrupo que engendra mediante sus potencias. En la siguiente entrada estudiaremos los elementos que engendran todo Z_n* (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 Z₁₃*.

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  Z_n* 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 a^k 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 5²=11 es la potencia positiva más pequeña que pertenece al subgrupo. Igualmente, el 3 es el indicador respecto a {13, 1}.

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.

Ciclos(3) Números de Stirling de primera especie

Vimos en la entrada anterior que toda permutación sobre el conjunto {1,2,3,…,n} se puede descomponer en k ciclos, y van desde la identidad, que comprende n ciclos, hasta las permutaciones cíclicas, que se reducen a un solo ciclo.

Si fijamos el número k, podremos plantearnos cuántas permutaciones se pueden descomponer exactamente en k ciclos. Por ejemplo, en el conjunto {1,2,3,4,5}, las permutaciones formadas por dos ciclos son (escribimos sólo los conjuntos invariantes en los ciclos):

(1,2,3,4)(5), (1,2,3,5)(4), (1,2,4,5)(3), (1,3,4,5)(2), (2,3,4,5)(1),
(1,2,3)(4,5), (1,2,4)(3,5), (1,3,4)(2,5), (2,3,4)(1,5), (1,2,5)(3,4), (1,3,5)(2,4), (2,3,5)(1,4),
(1,4,5)(2,3), (2,4,5)(1,3), (1,3,5)(1,2)

Resultan en total 15 configuraciones, pero cada conjunto de cuatro elementos equivale a seis ciclos (permutaciones circulares, factorial de n-1=3). Así, (1,2,3,4) contiene en realidad los ciclos (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3)(1,4,3,2) y cada conjunto de tres equivale a dos ciclos (y los de dos, a uno solo), luego tendremos:

S(5,2)=5*6+10*2=50

Al número de permutaciones de n elementos que están formadas por k ciclos le llamaremos número de Stirling de primera especie sin signo, y lo representaremos por S(n,k). Así, el cálculo anterior se puede expresar como S(5,2)=50

Es evidente que S(n,n)=1, pues sólo la identidad contiene n ciclos, y que S(n,1)=(n-1)!, pues representaría a las permutaciones circulares. Además, S(n,0)=0, valor adoptado por definición. Piensa también por qué S(n,n-1)=Cn,2 (número combinatorio).

El resto de números de Stirling se obtiene mediante la fórmula de recurrencia

S(n+1,k)=S(n,k-1)+nS(n,k)

En efecto, si añadimos un elemento nuevo a una configuración en ciclos, puede ocurrir que ese elemento sea un invariante, que forme ciclo consigo mismo. En ese caso puede estar acompañado de S(n,k-1) formas distintas de distribución en ciclos. Por el contrario, si el nuevo lo deseamos integrar en los ciclos ya existentes, lo podemos incluir ocupando n lugares distintos, luego formará nS(n,k) configuraciones diferentes.

Lo entenderás mejor con un ejemplo. Formemos todas las distribuciones de 4 elementos en 3 ciclos:

(1)(2,3)(4), (2)(1,3)(4), (3)(1,2)(4)
(1,4)(2)(3), (1)(2,4)(3), (1)(2)(3,4)

En total resultan 6. En la primera fila hemos añadido el 4 como elemento invariante, añadido a las tres configuraciones de 3 elementos en dos ciclos S(3,2) y en la segunda lo hemos integrado en los ciclos existentes, que sólo tienen una posibilidad, (1)(2)(3) (S(3,1)) y podemos insertarlo en 3 posiciones distintas, luego resultan 3S(3,3). En resumen:

S(4,3)=S(3,2)+3S(3,3)

Esto nos da una posibilidad de calcular estos números. Por convenio se les da valor cero cuando el número de ciclos es cero. En la imagen tienes la tabla conseguida en hoja de cálculo con stirling.xls y stirling.ods (los puedes descargar desde
http://hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#nume)

Comprueba en ella alguna generación por recurrencia. Por ejemplo, 274=50*5+24, 1624=225*6+274

También es elemental la propiedad de que la suma de números de Stirling para un n dado es n!, pues abarcan todas las posibilidades. Comprueba este hecho sumando todos los números de una misma fila en la tabla de la imagen.

Observa que cada fila posee un solo máximo, como ocurre, por ejemplo con los números combinatorios, sólo que aquí no está necesariamente en el punto medio.

Función generatriz

La función generatriz de estos números (con signo), para un n dado es

F_n(x)=x(x-1)(x-2)(x-3)…(x-n+1)=x⁽ⁿ

Con ella resultan los números con signo y prescindiendo de S(n,0). Observa que se trata de una potencia factorial, o factorial de grado n de x. Los números de Stirling con signo obedecen la misma fórmula de recurrencia, pero restando el segundo término. Esto es claro si consideras el desarrollo de

F_n+1(x)=x(x-1)(x-2)(x-3)…(x-n+1)(x-n)= F_n(x)(x-n)

Piensa en un grado cualquiera del desarrollo y lo comprenderás.

Lo podemos comprobar con PARI, por ejemplo en el caso n=6

{print(taylor(x*(x-1)*(x-2)*(x-3)*(x-4)*(x-5),x,7))}

Resultado: -120*x + 274*x^2 - 225*x^3 + 85*x^4 - 15*x^5 + x^6 + O(x^7)

En la imagen puedes estudiar la comprobación con wxMaxima:

Como ves, los ordena en sentido inverso.

Una interpretación sencilla de este desarrollo es el considerar los números de Stirling (salvo el caso de índice cero) como los coeficientes mediante los que una potencia factorial x⁽ⁿ se descompone como combinación lineal de potencias ordinarias x^k de x.

Ciclos (2) – Descomposición en ciclos

Algunas permutaciones dejan invariantes unos elementos, y a otros los van transformando cíclicamente hasta volver al primero. Así, la permutación (1,3,4,2,5,6) deja invariantes 1, 5 y 6, mientras 3 se transforma en 4, este en 2 y el 2 tiene como imagen el 3. A este tipo de permutaciones las llamaremos ciclos. Omitimos definiciones formales, porque aquí nuestro interés es práctico y de aprendizaje de las hojas de cálculo.

Llamaremos ciclo a una permutación que deja invariantes algunos elementos y somete a una rotaciones completas a los restantes. 

Representaremos un ciclo mediante los elementos que se van transformando uno en otro, omitiendo los invariantes. Así, (3,4,2) representaría a la anterior permutación. Podemos someter a los elementos 3,4,2 a una rotación en el orden y representarían el mismo ciclo: (3,4,2) = (4,2,3) = (2,3,4), pero otro tipo de alteración del orden, como (3,2,4) ya representaría un ciclo distinto. Si aplicamos reiteradamente un ciclo, cada elemento irá pasando por todas las posiciones posibles e, inversamente, por una posición dada irán pasando ordenadamente todos los elementos.

Un mismo ciclo se puede representar comenzando con cualquiera de sus elementos si se respeta el orden circular.

Un ciclo de un elemento representa un elemento invariante, y el de dos, una transposición entre dos elementos. Si el ciclo abarca la permutación completa, a esta la llamaremos cíclica.

La propiedad más importante de los ciclos es que toda permutación se puede descomponer en ciclos disjuntos de forma única salvo el orden. Según esto, la del ejemplo podemos representarla como (1,3,4,2,5,6)=(3,4,2)(1)(5)(6). Se suelen ordenar los ciclos por su magnitud, de mayor a menor.

¿Cómo descomponer una permutación en ciclos?

El procedimiento puede ser el siguiente:

Elegimos el elemento 1, y aplicamos la permutación de forma reiterada hasta que la imagen vuelva a ser 1. Como el conjunto es finito, esto se acabará logrando, con lo que ya tendremos el primer ciclo de la descomposición. Buscamos después el siguiente elemento que no pertenezca al ciclo conseguido (si hemos acabado es que la permutación estudiada se reduce a un solo ciclo, es cíclica) y efectuamos la misma operación para obtener el segundo ciclo, y así sucesivamente hasta agotar el conjunto.
Por ejemplo, la permutación (4, 2, 6, 7, 8, 9, 10, 11, 3, 1, 5) nos llevaría al siguiente proceso:
Comenzamos con el 1. Las sucesivas imágenes serían: 1 – 4 – 7 – 10 – 1. Ya tendríamos el primer ciclo (4, 7, 10, 1).

Buscamos el siguiente elemento no estudiado aún: el 2, que se transforma en sí mismo. El siguiente ciclo es, pues, (2)

Siguiente elemento libre: 3, que engendra: 3 – 6 – 9 – 3, formando el ciclo (3, 6, 9)

Por último, con 5 logramos (5, 8, 11)

Hemos terminado: (4, 2, 6, 7, 8, 9, 10, 11, 3, 1, 5) = (4, 7, 10,1) (3, 6, 9) (5, 8, 11) (2)

Como cada ciclo opera sobre elementos disjuntos, esta descomposición es un producto en S_n (ver entrada anterior del blog), en el que los ciclos son permutables y por tanto, no influye el orden.
En este proceso los ciclos que se formen serán disjuntos, pues si dos de ellos tuvieran un elemento común, al aplicar el ciclo sobre él reiteradamente se incluirían todos los elementos, y los ciclos serían en realidad uno solo.

El número de ciclos en que se descompone una permutación varía entre 1, si ella misma es cíclica, hasta n, si se trata de la permutación identidad.

Podemos conseguir que una hoja de cálculo haga lo mismo:

Lo hemos implementado en Excel y Apache OpenOffice (http://hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#ciclos)

Observa que ha creado una fila en la que va tomando nota de los ciclos a los que pertenece cada elemento, y después ha escrito debajo la composición de cada ciclo. Es una tarea un poco larga, por lo que sólo explicaremos los fundamentos, remitiendo después a la hoja ya confeccionada.

Proceso para encontrar los ciclos:

1) Se crean unas memorias que contendrán la información de los ciclos que se van ocupando. Al principio se inician todas a cero.

2) En cada paso del proceso se busca el primer elemento cuyo número de ciclo es 0. Se aumenta en una unidad el número del ciclo, que, por tanto, comenzará en 1. Con un procedimiento similar al usado en la anterior entrada, se aplica reiteradamente la permutación hasta completar el ciclo.

Este paso se da mientras exista un elemento con número de ciclo 0. Para cada elemento, se irá escribiendo en la hoja a qué ciclo pertenece.

3) Localizados los ciclos, se van buscando los elementos de cada uno y se escriben en filas distintas debajo del esquema. Esta parte es más informática que matemática, y la podemos omitir.

Generación aleatoria

Como la hoja de cálculo ofrecida no tiene más objetivo que el de explicar el concepto, se ha añadido la posibilidad de generar aleatoriamente una permutación para comprender mejor la descomposición en ciclos.

Orden de un ciclo

No es difícil entender que el orden de un ciclo es su longitud, ya que los elementos invariantes seguirán siéndolo aunque reiteremos y los cíclicos se irán recorriendo uno por uno y se llegará al primero cuando se recorra toda la longitud:

El orden de un ciclo coincide con su longitud

También es sencillo entender que si una permutación se descompone en ciclos, su orden será el MCM de las longitudes de los mismos.

Así, el orden de (1)(2, 3, 7)(4, 5)(6) será 6, el mcm(1, 3, 2, 1)

En la misma hoja se puede estudiar el orden de los ciclos y el de la permutación total

El orden de los ciclos aparece en la parte izquierda de los mismos

El orden total, MCM de los de los ciclos lo tendrás en la parte derecha

Transposiciones

Llamaremos transposición a un ciclo de orden 2. Todo ciclo, y en consecuencia toda permutación, se puede descomponer en transposiciones. Se comprende sólo con estudiar este desarrollo:

(a, b, c, d, e)=(a, e)(a, d)(a, c)(a, b)

Esta descomposición no es única.

Algunos cálculos

Permutaciones circulares  o cíclicas

Puede ocurrir que una permutación sea en sí misma un ciclo. La llamaremos cíclica o circular. Dentro del grupo simétrico Sn el número de permutaciones cíclicas equivale a (n-1)! Es algo muy conocido y se justifica porque para inventarte una permutación de este tipo en primer lugar has de ordenar todos los elementos, lo que puedes realizar de n! formas diferentes y una vez elegida una, esta representa n circulares idénticas, porque tienes n formas de elegir el primer elemento, luego el número es n!/n=(n-1)!
Permutaciones de n elementos que son ciclos de orden k

Deberemos elegir k elementos para el ciclo y dejar los restantes n-k fijos. El elegirlos nos supone Cn,k formas y dentro de los elegidos, (k-1)! ciclos posibles, luego el número total de ciclos de orden k será

Permutaciones reducidas

Son aquellas que no dejan fijo ningún elemento, las que en la descomposición en ciclos ninguno de ellos tiene orden 1. Son las conocidas como desarreglos (o desbarajustes) Los puedes estudiar en http://hojamat.es/sindecimales/combinatoria/teoria/teorcomb.pdf

En esa dirección hemos explicado su fórmula

Ciclos (1) Grupo simétrico

Solemos considerar las permutaciones como las distintas ordenaciones de un conjunto. Existe otro punto de vista alternativo, que es muy fructífero, y es considerarlas como  aplicaciones biyectivas del conjunto en sí mismo. Así, la permutación S=(3,2,1,4) se puede considerar derivada de (1,2,3,4) (orden principal) mediante la aplicación S(1)=3, S(2)=2, S(3)=1 y S(4)=4. Así la interpretaremos aquí.

Como la naturaleza de los elementos no influye en la teoría, imaginaremos que se trabaja siempre sobre el conjunto {1,2,3,4,…,n} y que una permutación como S=(5,1,3,2,…) se interpreta: S(1)=5, S(2)=1, S(3)=3, S(4)=2,…La escribimos así, como un conjunto de imágenes, por comodidad de escritura, pero te la puedes imaginar con los orígenes sobre ellas formando una matriz de dos filas, con lo que cae cada imagen debajo del origen

Las permutaciones se pueden componer como todas las aplicaciones, usando una de ellas  y después la otra sobre las imágenes de la primera. No es fácil verlo en este caso, por lo que usaremos un ejemplo:
Sean G=(4,2,5,3,1) y H=(1,4,3,5,2), o escribiendo orígenes:

G:

H:

La composición H*G (escribiendo de derecha a izquierda) se formaría así (hay que estar atentos):

H*G(1)=H(G(1))=H(4)=5   H*G(2)=H(G(2))=H(2)=4   H*G(3)=H(G(3))=H(5)=2
H*G(4)=H(G(4))=H(3)=3   H*G(5)=H(G(5))=H(1)=1, con lo que resultaría
H*G=(5,4,2,3,1)  Como ves, no es nada intuitivo.

Es fácil demostrar que las n! permutaciones forman grupo para esta composición, siendo la identidad E=(1,2,3,4,…, n) y el inverso la permutación que convierte las imágenes en orígenes. A este grupo lo llamaremos Grupo simétrico para {1,2,3,…, n} y lo representaremos como S_n.

¿Te apetecería comprobar composiciones de permutaciones con hoja de cálculo? Te damos unas ideas:

Puedes escribir en filas distintas, una debajo de la otra, las dos permutaciones G y H (en la imagen, filas 12 y 16) y después la composición de ambas (fila 20), que es la única que contendrá fórmulas. El resto de la hoja sólo contiene datos.

Es muy interesante estudiar qué fórmula podemos implementar en la fila 20 de la imagen. Explicaremos la primera celda, B20, y después bastará extenderla al resto de la fila. La fórmula adecuada es:

=ÍNDICE($B16:$J16;1;B12)

La función ÍNDICE elige en una lista el elemento que presenta un número de orden. En este caso la lista es la permutación H. De ahí que hayamos usado el rango $B16:$J16. Después hay que indicar la fila del rango. Como solo hay una fila, hemos escrito un 1. El siguiente parámetro es el número de orden, y aquí va a residir el truco: Hemos de elegir en H el elemento que ocupe el lugar que indica G en la misma columna. Insistimos en que esto, al principio, no es fácil. Hemos escrito en la fórmula “B12”, que es la primera imagen de G, un 6, luego deberemos ir a H y buscar el sexto elemento, un 8, y por eso en la celda B20 aparece ese 8.

Como puede que te siga costando, te ofrecemos esta hoja en la dirección

http://hojamat.es/blog/compopermu.zip

Como el grupo simétrico opera sobre un conjunto finito (cardinal n!), la aplicación reiterada de una sustitución consigo misma (potencia de la permutación) llevará a la repetición de resultados, es decir, a que dos potencias distintas sean equivalentes:

P^m=Pⁿ

Si suponemos, por ejemplo que m<n, entonces esa igualdad, si le aplicamos la permutación inversa para simplicar, se convertiría en

P^n-m=P^k=E (identidad)

Toda permutación, aplicada un número determinado de veces, se convierte en la identidad.

El número mínimo para el que eso ocurre recibe el nombre de orden de la permutación. En los ejemplos de arriba, el orden de G es 4, y el de H es 3. Compruébalo. Esta idea nos servirá en lo que sigue.

Una propuesta: En la imagen se ha compuesto G consigo misma, y el conjunto total parece haberse dividido en tres subconjuntos, cada uno de los cuales parece que va “a su aire”, sin mezclarse con los otros. ¿Cuáles son?

En otra entrada los relacionaremos con los ciclos. Te puedes adelantar en su estudio.

Retículos en el conjunto de divisores (2)

Esta entrada es la segunda parte de nuestra participación en la Edición 4.1231 del Carnaval de Matemáticas cuyo anfitrión es Matemáticas Interactivas y Manipulativas.

Estudiamos en la entrada anterior el retículo de los divisores de N. Ahora buscaremos subretículos del mismo.

El retículo de los libres de cuadrados

Lo presentaremos con un ejemplo. Imaginemos todos los divisores de 1800 que son libres de cuadrados, es decir, que sus factores primos están todos elevados a la unidad. Es claro que cualquier divisor de ellos lo será también del radical de de 1800, que es 30 (contiene los mismos factores primos, pero elevados a la unidad). Por tanto, esto nos remite al caso general: es retículo el conjunto de divisores de un número libre de cuadrados (ver entrada anterior).

En el caso de 1800 son estos: {30, 15, 10, 6, 5, 3, 2, 1} Todos presentan los primos 2, 3 o 5 elevados a la unidad. El mayor, 30, es el radical de 1800. Como es libre de cuadrados, sus divisores formarán un retículo.

La imagen te lo explica perfectamente. Cada par de elementos tiene un supremo y un ínfimo. Todo el conjunto posee un máximo, que es 30 y un mínimo 1.

En este retículo todo elemento a posee un complemento a’, formado por los factores primos que no son divisores de a. Es claro que el supremo de a y a’ es 30 y el ínfimo 1. Por tener esta propiedad este retículo es complementado.

Hemos descubierto que en el conjunto de divisores de un número cualquiera, los libres de cuadrados forman un subretículo, que coincide con los divisores del radical de N. Este retículo es complementado.

Por ejemplo, en el número 4900, el subretículo de los libres de cuadrados está formado por el conjunto {70, 35, 14, 10, 7, 5, 2, 1 }

¿Qué ocurre con los que no son libres de cuadrados?

Un divisor no libre de cuadrados admite a su vez otro divisor suyo que sí lo sea. 90 no está libre de cuadrados, pues equivale a 2*3²*5, pero admite como divisor el 15 que sí es libre de cuadrados. Es un conjunto que no es sub_semirretículo para la relación de ser divisor. En el caso de 1800 es este: {1800, 900, 600, 450, 360, 300, 225, 200, 180, 150, 120, 100, 90, 75, 72, 60, 50, 45, 40, 36, 25, 24, 20, 18,  12,  9, 8,   4}

Si cambiamos la relación de “ser divisor” por la de “ser múltiplo”, la idea se invierte: Cualquier múltiplo de un divisor no libre de cuadrados tampoco lo será, y lo convierte en un sup_semirretículo para la relación de “ser divisor”. Así que en el conjunto de los divisores no libres de cuadrados todo par de ellos posee un supremo que pertenece al conjunto, pero quizás no exista el ínfimo. Con un ejemplo lo verás: 1800=MCM(450,24) es el supremo de ambos, y está en el conjunto. Sin embargo 6=MCD(450,24) no lo está.

Caso de los pares e impares

Con los divisores pares e impares de un número ocurre algo parecido. Lo resumimos rápidamente:

Los divisores de un número impar han de ser también impares
Los múltiplos de un número par han de ser pares.

Así que si clasificamos los divisores de un número en pares e impares, veremos que ambos conjuntos serán un retículo. Observa el caso de 840:

Pares: {840, 420, 280, 210, 168, 140, 120, 84, 70, 60, 56, 42, 40, 30, 28, 24, 20, 14, 12, 10, 8, 6, 4, 2}
Impares:{105, 35, 21, 15, 7, 5, 3, 1}

En efecto, los impares forman retículo, porque 105 es el mayor divisor impar, (http://hojaynumeros.blogspot.com.es/2012/12/volvemos-visitar-al-mayor-divisor-impar.html) obtenido eliminando del 840 todas las potencias de 2 y quedándonos con todos los factores impares de 840. Por tanto, los demás divisores impares lo serán también de 105, y es fácil ver que forman un sup_semirretículo.

Hacia abajo es mucho más fácil razonarlo: todo divisor de un impar es también impar, lo que nos lleva a que sea un sub_semirretículo, y por tanto, un retículo. Esto es válido para cualquier número que no sea potencia de 2, ya que entonces el conjunto de divisores impares se reduciría a 1.

Los pares también forman retículo. Sólo se pueden considerar si N es par, como es evidente. El MCD de dos pares también será par, con un ínfimo en el 2. El MCM también lo será con mayor razón, con supremo N, que hemos supuesto que es par. También forman retículo.

Si el mayor divisor par propio, o el mayor divisor impar propio son libres de cuadrados, sus retículos correspondientes serán complementados. Un ejemplo de este tipo, el factorial de 5, 120, es libre de cuadrados, luego también lo serán su mayor divisor par 60 y el mayor impar 15, que dan lugar a los retículos {120, 60, 40, 30, 24, 20, 12, 10, 8, 6, 4, 2} y {15, 5, 3, 1} respectivamente.

Te puedes distraer buscando el complemento de cada uno de los elementos, tanto en los subretículos como en el retículo total.

Múltiplos de uno de los factores primos

Considera los divisores de N que son múltiplos de uno de los factores primos. Por ejemplo, en el conjunto de divisores de 3850: {3850, 1925, 770, 550, 385, 350, 275, 175, 154, 110, 77, 70, 55, 50, 35, 25, 22, 14, 11, 10, 7, 5, 2, 1} podemos seleccionar los que son múltiplos de 11: {3850, 1925, 770, 550, 385, 275, 154, 110, 77, 55, 22, 11}. Es un retículo, porque si 11 divide a dos elementos del conjunto, también divide a su MCD, luego éste también pertenece al conjunto. Su MCM también será múltiplo de 11 y divisor de 3850, luego será también elemento del conjunto. Su máximo es el número N, 3850, y el mínimo 11.

¿Qué ocurre con los que no son múltiplos de ese factor primo?

En el ejemplo serían {350, 175, 70, 50, 35, 25, 14, 10, 7, 5, 2, 1}, pero esos son los divisores de 350, que forman retículo (razónalo) y coinciden en número con los del anterior. Es más, podemos establecer una correspondencia biyectiva entre los múltiplos de 11 y los que no lo son:

3850   350
1925   175
770      70
550      50
385      35
275      25
154      14
110      10
77          7
55          5
22          2
11          1

En este diagrama, al que hemos suprimido líneas, se ve bien la correspondencia:

En realidad, estamos ante un isomorfismo de retículos, porque cualquier MCD o MCM del primero, al multiplicar por 11 se convierte en el MCD o MCM en el segundo. Razónalo.

Esto ha sido casual, porque hemos elegido 11, que está elevado a la unidad. Retrocede al caso de pares e impares que estudiamos antes y comprobarás que no se da ese isomorfismo.

¿Se dará siempre que el factor primo esté elevado a la unidad? 

Lo vemos:

Si el numero N contiene a p con exponente 1 en su descomposición en factores primos, sus divisores se dividirán en dos subconjuntos, A, los que contienen a p, es decir tienen la forma p*q, y B, los que no lo contienen. Pero si piensas un momento el factor q que hemos usado, recorrerá B mientras p*q recorre A.

En este caso se da un isomorfismo entre los divisores múltiplos de p y los que no lo son. La expresión e este isomorfismo es F(x)=p*x, con x elemento de A y F(x) elemento de B
Así que el caso de 3850 no era una excepción.

Caso en el que el factor primo está elevado a un exponente mayor

Lo intentamos con los múltiplos de 5 en ese mismo ejemplo del 3850:
{3850, 1925, 770, 550, 385, 350, 275, 175, 110, 70, 55, 50, 35, 25, 10,  5}
Y los que no lo son
{154, 77, 70, 22, 14, 11, 7, 2, 1}

Vemos que hay la mitad de elementos, porque 5 está al cuadrado. Si eligiéramos el conjunto de los múltiplos de 25 y el de los de 5 que no lo son de 25 nos resultarían tres conjuntos con el mismo cardinal

No múltiplos de 5: {154, 77, 70, 22, 14, 11, 7, 2, 1}
Múltiplos de 5 pero no de 25: {770,  385, 110, 70, 55, 35,  10,  5}
Múltiplos de 25: {3850, 1925, 550, 350, 275, 175, 50, 25}

Es fácil ver que los tres son retículos isomorfos. Intenta una generalización.

Múltiplos de cualquier divisor dado

¿Formarán también retículo los múltiplos de un divisor dado? Un ejemplo: entre los divisores de 600 seleccionar los que son múltiplos de 15

Todos los divisores de 600 son: {600, 300, 200, 150, 120, 100, 75, 60, 50, 40, 30, 25, 24, 20, 15, 12, 10, 8, 6, 5, 4, 3, 2, 1}

Los que son múltiplos de 15:{600, 300, 150, 120, 75, 60, 30, 15} y los que no lo son
{200, 100, 50, 40, 25, 24, 20, 12, 10, 8, 6, 5, 4, 3, 2, 1}

Es claro que en el primero el MCD y el MCM de dos múltiplos de 15 también lo es. El segundo no es retículo, porque no contiene el MCM(3,5)=15.

Los múltiplos de cualquier divisor de N constituyen un retículo, pero los que no lo son no tienen que serlo.