Los pseudoprimos

Definición de pseudoprimo 

La idea de número pseudoprimo surge de los grandes teoremas de la Aritmética Modular

(Ver mi publicación http://www.hojamat.es/sindecimales/congruencias/teoria/teorcong.pdf):

Podemos comenzar por el de Euler: Si llamamos j(m) a la indicatriz de Euler de m, se cumplirá que

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

para todo a primo con m. (Teorema de Euler)

Si m es primo, la igualdad anterior se puede expresar como

a^m-1 =1 (mod m)

 (Pequeño Teorema de Fermat)

El recíproco no es cierto. Si para un a primo con m se cumple

a^m-1=1 (mod m), entonces m no tiene que ser necesariamente primo. A estos números compuestos que cumplen el teorema les llamaremos pseudoprimos de Fermat (hay otras clases de pseudoprimos). Este carácter dependerá del valor de la base a.

 

Identificación de pseudoprimos

No es nada complicado identificar un pseudoprimo respecto a una base dada. Las operaciones son sencillas, pero pueden alcanzar números muy grandes, por lo que tendremos que usar técnicas de Aritmética Modular en algunos casos, para abreviar cálculos y datos.

La primera operación es la de obtener el resto de una potencia respecto a un módulo, lo que llamamos resto potencial. En nuestra web figura una hoja de cálculo de hace años, muy simple, que los calcula para datos no muy grandes

http://www.hojamat.es/sindecimales/congruencias/herramientas/hoja/potenciales.xls

La teoría sobre restos potenciales también la puedes consultar en nuestro documento

http://www.hojamat.es/sindecimales/congruencias/teoria/teorcong.pdf

Aquí partiremos de una función que actuará sobre tres datos:

• ·       Base de la potencia b
• ·       Exponente p
• ·       Módulo m

Sobre ellos actuará la función RESTOPOT para Excel y LibreOffice Calc, que irá construyendo la potencia mediante multiplicaciones, pero convirtiendo cada resultado en resto módulo m, con lo que no se disparará la magnitud de los datos. Este es su listado:

Función RESTOPOT

Public Function restopot(b, p, n)

Dim r, m, i

 

r = b Mod n ‘Resto de la base respecto a m

m = 1

For i = 1 To p ‘Se construye la potencia con restos

m = m * r Mod n ‘m irá recorriendo los restos potenciales

Next i

restopot = m

End Function

 Por ejemplo, el resto de 3^26 respecto al módulo 7 sería RESTOPOT(3;26;7)=2, como puedes comprobar en la hoja potenciales.xls presentada más arriba:

 

Con esta función podemos averiguar si a^m-1 =1 (mod m)  y si m es compuesto, con lo que tendría el carácter de pseudoprimo.

Contando con la función RESTOPOT es fácil exigir que se cumplan las condiciones para ser pseudoprimo en una base dada.

 

Public Function espseudo(m, b) As Boolean

If Not esprimo(m) And mcd(m, b) = 1 And restopot(b, m - 1, m) = 1 Then espseudo = True Else espseudo = False

End Function

Nos limitamos a exigir que

• ·       Sea compuesto
• ·       Primo con la base
• ·       El resto potencial b^m-1 respecto a m sea 1

Con esta función y un bucle de búsqueda podemos reproducir muchas sucesiones de pseudoprimos ya publicadas en OEIS. Por ejemplo, para b=23 obtenemos esta lista:

Pseudoprimos en base 23

22, 33, 91, 154, 165, 169, 265, 341, 385, 451, 481,…

La puedes comprobar en http://oeis.org/A020151

En base 11

Obtenemos: 10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257

(Ver http://oeis.org/A020139)

 

Versión en PARI

Si deseas estudiar números mayores contando con la mayor velocidad de proceso de PARI, puedes usar este código debidamente adaptado a tus datos (está construido para base 23 y búsqueda hasta el 4000):

rpm(b,p,n)={my(r,m,i);r=b%n;m=1;for(i=1,p,m=(m*r)%n);m}

espseudo(m,b)=!isprime(m)&&gcd(m,b)==1&&rpm(b,m-1,m)==1

for(k=2,4000,if(espseudo(k,23),print1(k,", ")))

Lo hemos adaptado a base 17 y cota 20000, obteniendo:

4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187, 4912, 5365, 5662, 5833, 6601, 6697, 7171, 8481, 8911, 10585, 11476, 12403, 12673, 13333, 13833, 15805, 15841, 16705, 19345, 19729,…

Coinciden con los pseudoprimos publicados en http://oeis.org/A020145

 

Números de Carmichael

Si un número es pseudoprimo con base todos los números coprimos con él, se llama “de Carmichel”.

Los primeros los tienes en https://oeis.org/A002997:

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633,…

Bastará recorrer los números coprimos con uno de ellos y comprobar que es pseudoprimo con todos ellos.

Hay criterios más sencillos, que puedes consultar en

https://en.wikipedia.org/wiki/Carmichael_number.

 

Números de Sarrus o Poulet

Estos son los pseudoprimos en base 2, también llamados números de Sarrus, Poulet o simplemente psudoprimos, sin especificar el módulo.

El primer pseudoprimo módulo 2 es el 341, porque es compuesto (341=11*31) y cumple que

2³⁴⁰ =1 (mod 341)

Esta condición se verifica fácilmente, ya que 2¹⁰=1024=3*341+1 presenta resto 1 respecto al módulo 341, por lo que todas sus potencias, entre ellas 2³⁴⁰ también tendrán ese mismo resto.

El segundo pseudoprimo módulo 2 es 561, que es compuesto (561=3*11*17) y se verifica que

2⁵⁶⁰ =1 (mod 561)

La sucesión de números de Poulet la tienes en http://oeis.org/A001567

341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585, 11305, 12801, 13741, 13747, 13981, 14491, 15709, 15841, 16705, 18705, 18721, 19951, 23001, 23377, 25761, 29341...

Aquí nos hemos limitado a presentar conceptos básicos y facilitar la búsqueda de pseudoprimos. Se podría extender más su estudio, pero superaría los objetivos de este blog.

 

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.

Propiedades de los restos cuadráticos

Usaremos en los desarrollos el símbolo de Legendre ya explicado en la entrada anterior, Recuerda que la actual entrada es parte de un ciclo de tres.

El criterio de Euler da lugar a propiedades interesantes de los restos cuadráticos respecto a ciertos tipos de primos. Los vemos:

 -1 es un resto para todos los primos del tipo 4N+1 y no resto para los del tipo 4n+3

Es una consecuencia del criterio de Euler, pues (p-1)/2 sería par en el primer caso, e impar en el segundo, luego al elevar -1 a esa cantidad producirá un 1 (ser resto) para p=4N+1 y -1 (no resto) en el otro caso.

Esto quiere decir que la ecuación x² + 1 º 0 (mod p) tiene solución para p=4N+1 y no la tiene en el segundo caso. Podemos expresarlo también como que 1 posee una raíz cuadrada entre las clases de restos módulo p

Podemos diseñar un pequeño esquema con la hoja de cálculo que usamos en esta serie:

 En la celda del 11 hemos escrito =RESTOCUAD(-1;61). Como este módulo es del tipo 4N+1, obtenemos la solución 11, ya que 11*11 módulo 61 es igual a 60, es decir, la clase de restos -1
Si hubiéramos usado módulo 11, que es del tipo 4N+3. Obtendríamos un cero, que es la señal de que -1 no es resto cuadrático:

Esta propiedad se puede expresar así:

2 es resto cuadrático para todos los primos del tipo 8N+1 y 8N+7, y no resto para los demás

También podemos, en nuestra hoja de cálculo, crear un esquema para comprobar esta propiedad siguiendo la estructura que usamos en la anterior.

Vemos que 11 no pertenece al tipo 8N+1 ni al 8N+7, y para el 2 no devuelve raíz cuadrada (el cero es una señal)

Sin embargo, al usar el módulo 31, que es del tipo 8N+7, el 2 presenta raíz cuadrada 8, y es resto cuadrático.

No es sencilla la demostración. Tienes una en Fundamentos de la Teoría de los números de Vinogradov.

Encontrarás propiedades similares para el -3 y el 5 en el documento de Rafael Parra “Restos cuadráticos y Ley de reciprocidad cuadrática”(http://www.hojamat.es/parra/restocuad.pdf). Las puedes comprobar con el esquema propuesto, sustituyendo el 2 por otros valores.

Ley de reciprocidad cuadrática

La propiedad más importante de estos restos es la ley de reciprocidad cuadrática, enunciada y demostrada por Gauss en 1801 en su libro Disquisitones Arithmeticae. Con palabras la podemos expresar así:

Dados dos primos impares p y q, si ambos pertenecen al tipo 4k+3, entonces p es resto cuadrático módulo q si y sólo si q no lo es de p. Si alguno de los primos pertenece al tipo 4k+1 entonces o bien ambos son restos uno del otro, o bien ninguno lo es.

Expresada así o de forma similar la propiedad resulta oscura. Sin embargo su significado queda claro con el uso de los símbolos de Legendre. En ese caso la propiedad se reduce a esta identidad:

Así se explica mejor: Si uno de los dos, p o q, es del tipo 4k+1, el exponente del -1 será par y el segundo miembro valdrá 1, con los que los símbolos del primero serán ambos iguales a 1 (restos recíprocos) o bien -1 (ninguno es resto).

Si ambos son del tipo 4k+3 el exponente será impar, el segundo miembro -1 y los símbolos tendrán signo opuesto: Si uno de los primos es resto del otro, no se dará la reciprocidad.

En textos y documentos varios dispones de ejercicios sencillos que muestran la utilidad de esta propiedad. Nosotros la hemos incluido en nuestra hoja de cálculo (http://www.hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm#restocuad)

Al escribir los dos primos la hoja analiza si son del tipo 4N+3 o 4N+1, calcula después los restos y comprueba la propiedad.

Como se trabaja con valores 1 y -1, algunos manuales expresan esta propiedad mediante esta otra identidad equivalente:

Así se ve mejor cómo calcular un valor de (p/q) si se conoce el de (q/p). Como hemos afirmado más arriba, no entra dentro de los objetivos de esta entrada pasar a ese tipo de cálculos.

Restos cuadráticos - Criterio de Euler

En la entrada anterior iniciamos el estudio de los restos cuadráticos respecto a un módulo. Descubrimos un procedimiento algo lento para encontrar los restos y los no restos. En esta otra entrada simplificaremos algo el proceso y aprenderemos nuevos conceptos. Se aconseja leer previamente dicha entrada.

El recorrer todos los restos desde 1 hasta (p-1)/2 puede hacerse muy pesado en el caso de valores muy grandes. Euler descubrió un criterio que nos ayuda a distinguir los restos de los no restos con un solo cálculo. Es este:

Si a es un resto cuadrático respecto a p (primo e impar) se cumple

Y si no lo es

Es una consecuencia del Teorema de Fermat:

Luego, como p-1 es par, podemos escribir

De esta congruencia deducimos que uno de los paréntesis es congruente con cero, pero ambos no pueden serlo, porque entonces su diferencia, 2, cumpliría 2º0 y eso es imposible para p primo impar.

De hecho, si a es resto cuadrático, el que se cumple es el segundo, ya que si existe un x tal que x²ºa (mod p) entonces a^(p-1)/2ºx^p-1º1 (mod p) de nuevo por el Teorema de Fermat.

Como sólo se puede cumplir una congruencia, si a  es no resto cuadrático, cumplirá la otra, con el -1.

Este criterio es bastante directo, para saber si un valor es resto cuadrático. Por ejemplo, ¿Es el 14 resto cuadrático respecto al 23?

14^(23-1)/2=14¹¹ Calculamos el resto de este último por potencias sucesivas: 14¹º14 (mod 23), 14²º12 (mod 23) 14⁴º12*12º6 (mod 23) 14⁸º6*6º13 (mod 23), luego 14¹¹º13*12*14º-1 (mod 23), luego no es resto cuadrático.

La herramienta de hoja de cálculo que proponemos, en su tercera hoja, te realiza los cálculos la aplicación de este criterio:

Es conveniente que lo intentes sin hoja de cálculo para practicar. Puedes usar la exponenciación modular (http://hojaynumeros.blogspot.com.es/2012/03/de-la-multiplicacion-rusa-la.html). La usaremos en el siguiente ejemplo:

¿Es resto cuadrático el número 70 respecto al módulo 101?

El módulo 101 es primo e impar, luego podemos usar el criterio de Euler. Bastará elevar 70 a (101-1)/2=50.

Sabemos que 50=32+16+2, luego vamos calculando: 70¹º-31 (mod 101), : 70²º31*31º-49 (mod 101), 70⁴º49*49º-23 (mod 101), 70⁸º23*23º24 (mod 101), 70¹⁶º24*24º-30 (mod 101), 70³²º30*30º-9 (mod 101), y ahora construimos el 50:

70⁵⁰º70³²70¹⁶70²º-9*30*49º1 (mod 101), luego según el criterio, 70 sí es resto cuadrático. Si lo compruebas con la herramienta que proponemos descubrirás que su raíz cuadrada es 26.

La aplicación de este criterio nos lleva a propiedades muy interesantes.

La primera es tan elemental que no tenemos que justificarla:

El producto de dos restos o de dos no-restos siempre da un resto, y el de resto con no resto produce un no-resto. Es decir, poseen estructura alternada, por lo que es fácil representar los restos mediante el signo + y los no restos con el -, y así poder usar la regla de los signos. Se razona fácilmente a partir del criterio de Euler.

Consecuencia inmediata:

El conjunto de restos cuadráticos forma un grupo multiplicativo en Zp

Por ejemplo, si m=11, los restos son 1, 3, 4, 5 y 9 y los no restos 2, 6,7, 8 y 10 (o bien -1, -3, -4, -5 y -9). Los restos forman un grupo, como se puede verificar fácilmente.

En la segunda hoja de la herramienta que ofrecemos dispones de una calculadora para comprobar las afirmaciones anteriores.

En particular puedes estudiar que si llamamos C al grupo de los restos cuadráticos, las clases laterales tipo a*C tienen cardinal (p-1)/2 y que por tanto el índice de C respecto a Zp es 2. Vemos una de esas clases. Multiplica el elemento 6 de Z11, por todos los elementos de C, en este caso 1, 3, 4, 5, 9: 6*1º6 (mod 11), 6*3º7 (mod 11), 6*4º2 (mod 11), 6*5º8 (mod 11), 6*9º10 (mod 11). Han resultado valores distintos, luego el cardinal de 6*C es (11-1)/2=5

Símbolo de Legendre

Esta estructura como grupo multiplicativo se expresa muy bien mediante el símbolo de Legendre (por comodidad tipográfica lo escribiremos como (m/p), con los dos números en línea, como hace Apostol).

Llamamos Símbolo de Legendre a una función que asigna a cada par de valores m y p, este último primo e impar, los siguientes valores:

(m/p)=1 si m es resto cuadrático respecto a p
(m/p)=-1 si m es no-resto cuadrático respecto a p
(m/p)=0 en el caso particular en el que m sea múltiplo de p.

En realidad, si recordamos el criterio de Euler, podemos usar una fórmula directa para encontrar el valor de un símbolo de Legendre:

Según lo explicado anteriormente, es fácil ver que esta función es multiplicativa:

Esto tiene una consecuencia práctica, y es que se pueden eliminar cuadrados al calcular el símbolo de un número compuesto.

Nótese que el valor del símbolo de Legendre es una propiedad de las clases de restos y no de los números concretos, por lo que es fácil entender que si aºb (mod p). entonces (a/p)=(b(p)