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.