Damos vueltas a los triangulares cuadrados (1) Generación.

Generación de la sucesión

Dos entradas del blog de John D. Cook (http://www.johndcook.com/blog/2015/08/20/when-is-a-triangle-a-square/ y siguiente) me han animado a volver a tomar el tipo de entrada al que llamé “dar vueltas” a un tema o concepto. Lo haré sobre estos números:

0, 1, 36, 1225, 41616, 1413721, 48024900, 1631432881,… (http://oeis.org/A001110)

Evidentemente,  tienen en común el ser triangulares y cuadrados a la vez. Puedes leer un desarrollo sencillo y claro en este documento:

http://www2.caminos.upm.es/Departamentos/matematicas/revistapm/revista_impresa/vol_IV_num_1/jue_mat_num_triang.pdf

Me he dado cuenta de que es un concepto sencillo pero que da lugar a bastantes reflexiones, algoritmos y repasos de teoría.

Nosotros seguiremos en parte este documento para iniciar el tema.

Búsqueda de números triangulares cuadrados

Un número triangular tiene por fórmula n(n+1)/2 y un cuadrado m². Aquellos números que participen de las dos características tendrán que cumplir la igualdad

De esta igualdad deducimos esta otra mucho más práctica:

O bien

Con cambio de variable se convierte en una ecuación de Pell:

Esta ecuación la tenemos muy estudiada

http://hojamat.es/parra/pell.pdf (documento de Rafael Parra)

http://hojaynumeros.blogspot.com.es/2010/02/ecuacion-de-pell.html

Disponemos además de una hoja de cálculo para ayudar a resolverla:

http://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#pell

Usamos esta herramienta para el coeficiente 8 y el segundo miembro 1 y nos dan las primeras soluciones:

(1,0) (3,1) (17,6) (99,35) (577,204) (3363,1189) (19601,6930) (114243, 40391),…

Por recurrencia:

Según la teoría de la ecuación de Pell, las soluciones aparecen con las recurrencias (en este caso) x_n=3*x_n-1+8*y_n-1  y_n=3*y_n-1+1*x_n-1. Por ejemplo, 99=3*17+8*6, 35=3*6+1*17.

Ahora sólo nos queda elevar al cuadrado las soluciones de y (que equivalen a la variable m de la primera igualdad que planteamos) y nos resultarán los triangulares cuadrados:

0²0, 1²=1, 6²=36, 35²=1225, 204²=41616, 1189²=1413721,…

Primer algoritmo

El estudio que acabamos de desarrollar nos da una pista para la generación de términos triangulares cuadrados: Iniciamos dos variables X=1, Y=0, y en  cada paso del algoritmo convertimos X en 3X+8Y y la Y en 3Y+X. Terminado el cálculo presentamos el valor de Y² como siguiente triangular cuadrado. En el Basic de las hojas de cálculo quedaría así:

Sub triangcuad()
Dim x, y, x1, y1, i, t, fila

x = 1: y = 0 ‘Valores de inicio
fila = 3 ‘Fila inicial
Cells(fila, 4).Value = 0 ‘El primer valor es un cero
For i = 1 To 8 ‘Calculamos sólo ocho
x1 = 3 * x + 8 * y ‘Iteración para x
y1 = 3 * y + x ‘Iteración para y
x = x1
y = y1
t = y * y ‘Número triangular cuadrado
fila = fila + 1
Cells(fila, 4).Value = t ‘Se presenta el resultado
Next i
End Sub

Obtendríamos:

El que el último se nos ofrezca en coma flotante nos da idea de las limitaciones de la hoja para cálculos con enteros de muchas cifras. Si acudimos a PARI no nos encontraremos con esas limitaciones. Prueba este código:

{x=1;y=0;print(0);while(x<10^10,x1=3*x+8*y;y1=3*y+x;x=x1;y=y1;t=y^2;print(t))}

En pocos segundos te presenta los triangulares cuadrados menores que 10^10.

Relación de recurrencia con una sola variable

Por la naturaleza de su definición podemos esperar que estos números sigan una relación de recurrencia de segundo orden. Para encontrar su expresión, que será del tipo

A_n=aA_n-1+bA_n-2+c usaremos los valores iniciales 0, 1, 36, 1225, 41616 para plantear:

36=a*1+b*0+c
1225=a*36+b*1+c
41616=a*1225+b*36+c

Resolvemos

1189=35a+b
40391=1189a+35b

1224=36a y a=34, b=-1 y c=2

Según los cálculos anteriores, la relación de recurrencia será

A_n=34A_n-1-A_n-2+2

Es la misma que propone John D. Cook en su blog.

En este blog no olvidamos la hoja de cálculo. Intenta una resolución como la de la imagen usando cálculo matricial:

A partir de esta escritura matricial del sistema de ecuaciones, creamos debajo la matriz inversa de los coeficientes con MINVERSA, y a su derecha su producto por los términos independientes con MMULT:

Conseguimos así la misma solución 34, -1, 2

Segundo algoritmo

La relación de recurrencia nos permite un segundo algoritmo para encontrar los triangulares cuadrados. El que describimos a continuación presenta los nueve primeros (después existen problemas de coma flotante)

Sub triancuad1()
Dim m, n, p, k, fila
m = 0: n = 1 ‘Valores iniciales
fila = 3
Cells(1, 3).Value = m ‘presenta los dos primeros términos
Cells(2, 3).Value = n
For k = 1 To 7
p = 34 * n - m + 2 ‘relación de recurrencia
Cells(fila, 3).Value = p: fila = fila + 1 ‘presenta los siguientes términos
m = n: n = p ‘cada término se convierte en el anterior
Next k
End Sub

Los términos rellenarán una columna de hoja de cálculo:

Siguiendo nuestra costumbre, lo traducimos a PARI para conseguir más términos:

{x=0;y=1;print(0);print(1);for (k=1, 20, z=34*y-x+2;print(z);x=y;y=z)}

No resistimos la tentación, al igual que propone J.C. Cook, de intentar una versión recursiva en forma de función. Funciona muy bien en hoja de cálculo:

Public Function ftriangcuad(n)
If n < 2 Then
ftriangcuad = n
Else
ftriangcuad = 34 * ftriangcuad(n - 1) - ftriangcuad(n - 2) + 2
End If
End Function

No necesita explicación. La tabla siguiente se forma con gran rapidez de cálculo:

Fórmula directa

Si lees el capítulo sobre sucesiones recurrentes en nuestra publicación Sucesiones (http://www.hojamat.es/publicaciones/sucesiones.pdf) entenderás que a partir de la fórmula de recurrencia es posible encontrar la expresión directa de cada término (fórmula del término general).  Sólo insertamos la captura de pantalla de nuestra hoja de cálculo Recurrencias
(http://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#recurre2) en la parte homogénea de la recurrencia:

Con un ligero retoque y la interpretación de los decimales llegamos a la propuesta por John D. Cook:

El uso de la raíz cuadrada de 2 le quita utilidad en nuestro trabajo, por lo que intentaremos prescindir de ella. Para ver la influencia del formato de coma flotante, la implementamos en hoja de cálculo, y el resultado es similar al de los algoritmos anteriores:

Función generatriz

Para quien no lo sepa, diremos que la función generatriz de una sucesión, si se desarrolla como una serie de potencias, poseerá como coeficientes de esas potencias de x los términos de la sucesión.

En el caso de los números triangulares cuadrados la función generatriz es

 (ver http://oeis.org/A001110)

 Con  esta sencilla orden de PARI podemos comprobar su desarrollo.

print(taylor(x*(1+x)/((1-x)*(1-34*x+x^2)),x,20))

Tercer algoritmo

Finalizamos la entrada con la presentación de un algoritmo de los que llamamos “ingenuos”, que no usan la teoría para simplificar los cálculos, pero sí la fuerza bruta de la velocidad de proceso. En este caso obligaremos a los números naturales a ir creciendo hasta alcanzar un cuadrado, y después a la inversa, que los cuadrados avancen hasta alcanzar un triangular. Cuando se llegue a una igualdad se imprime el resultado. A pesar de su simplicidad, no resulta lento. Es éste:

Sub triancuad2()
Dim i, j, m, n, k, fila
m = 3: n = 4: i = 2: j = 3 ‘Se inician las variables
k = 10 ^ 7
fila = 3
Cells(fila, 3).Value = 1: fila = fila + 1
While m < k ‘Busca soluciones menores que k
While m <= n ‘Los triangulares crecen
If m = n Then Cells(fila, 3).Value = m: fila = fila + 1 ‘Hay igualdad
i = i + 1: m = m + i
Wend
While n <= m ‘Los cuadrados crecen
If m = n Then Cells(fila, 3).Value = m: fila = fila + 1 ‘Hay igualdad
j = j + 2: n = n + j
Wend
Wend
End Sub

Dejamos a los lectores el estudio de  por qué funciona este algoritmo para descubrir los triangulares cuadrados. Como los anteriores, llega a los mismos resultados, en este caso  hasta 10^7.

Sucesión de Recamán

Estudiamos hoy una original sucesión que Bernardo Recamán Santos envió a N. J. A. Sloane en 1991 para su colección, y que desde entonces ha originado múltiples desarrollos, incluso musicales (ver https://www.youtube.com/watch?v=h3qEigSSuF0).

Su definición es la siguiente (versión con a₁=1):

a₁=1
a_n = a_n-1 – n, si este valor es positivo y no figura ya en la sucesión
a_n = a_n-1 + n, en caso contrario.

Sus primeros términos son: 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 25, 43, 62, 42, 63, 41, 18, 42, 17, 43, 16, 44, 15, 45, 14, 46, 79, 113, 78, 114, 77, 39, 78, 38, 79, 37, 80, 36, 81, 35, 82, 34, 83, 33, 84, 32, 85, 31, 86, 30, 87, 29, 88, 28, 89, 27, 90, 26, 91, 157,… (existe otra versión que comienza en 0, idéntica a esta en todo lo demás http://oeis.org/A005132)

El punto clave, y que nos permitirá estudiar su programación con hoja de cálculo es el de no figura ya en la sucesión, pues esto obliga a mantener en memoria un registro de los valores anteriores ¿Cómo solucionarlo en una hoja de cálculo? Intentaremos varias posibilidades.

Desarrollo de la sucesión mediante celdas

Las celdas de una hoja sirven de memoria en cualquier proceso, por lo que comenzaremos el estudio por ahí. En la imagen verás la formación de la sucesión de Recaman en la columna E, junto a otra auxiliar D que hemos añadido por simple comodidad:

La columna D contiene, simplemente, la diferencia a_n-1 – n, que se obtiene con las expresiones =E2-FILA(),=E3-FILA(),=E4-FILA(),…aprovechando la función FILA, que aquí representará el valor de n en la definición. Por eso hemos creado la sucesión a partir de la primera fila. Si ese valor en la columna D es positivo y no ha salido ya, será el valor del siguiente término de la sucesión. Por eso no extrañará que algunos de estos valores figuren en la columna E que estudiaremos a continuación.
En dicha columna E hemos construido una fórmula un poco compleja. Esta es la correspondiente a la celda E3:

=SI(Y(D3>0;CONTAR.SI(E$1:E2;D3)=0);D3;FILA()+E2)

Recuerda que D3 contiene a_n-1 – n, que en este caso sería  a₂ – 2.

La fórmula comienza con un SI, puesto que la definición se basa en una alternativa. Después una Y, ya que existen dos condiciones: una que D3 sea positiva, y otra que no figure ya en la columna E. La primera se resuelve con D3>0 y la segunda con CONTAR.SI(E$1:E2;D3)=0. Usamos CONTAR.SI para ver si D3 ha salido ya. Si el CONTAR da cero, es que no ha salido, y se admite. Observa que se busca desde la primera celda E$1 (referencia absoluta) hasta la anterior E2.

Si ambas condiciones se cumplen, la función SI devuelve D3, como era de esperar, y, en caso contrario, FILA()+E2, es decir, a_n-1 + n.

Rellenando esta fórmula hacia abajo obtendremos la sucesión hasta el término que deseemos. Lo hemos efectuado hasta 2000 términos, para crear un gráfico similar al que figura en las publicaciones que tratan esta sucesión, en este caso de tipo lineal:

Llaman la atención en el mismo las fuertes oscilaciones que se producen en algunos intervalos, en los que los términos sufren incrementos alternativamente positivos y negativos, como en este:

En este tramo, las diferencias positivas decrecen de uno en uno y las negativas de tres en tres.
Si hubiésemos usado un gráfico de dispersión entre n y a_n obtendríamos

Pertenencia de todos los enteros positivos

N. J. A. Sloane conjeturó que cualquier entero positivo terminará apareciendo en la sucesión, y de hecho, estas son las posiciones en las que figuran los primeros términos: 1, 4, 2, 131, 129, 3, 5, 16, 14, 12, 10, 8, 6, 31, 29, 27, 25, 23, 99734, 7, 9, 11, 13, 15, 17, 64, 62, 60, 58, 56,… https://oeis.org/A057167

Nosotros podemos construir esta sucesión con la función COINCIDIR. Observa la imagen:

Se han reproducido los valores de las posiciones de 1, 2, 3,… salvo la del 19, que al ser 99734 excedía nuestro ámbito de estudio. Como uno de los objetivos de este documento es el aprendizaje de las técnicas de la hoja de cálculo, reproducimos la fórmula usada. La columna F contiene los primeros números naturales, y recuerda que E contiene la sucesión. Bastará, pues, usar la función COINCIDIR, para ver si el número dado figura o no en la sucesión, y en qué posición, que es lo que nos devuelve esa función COINCIDIR. Por ejemplo, para el 5 usamos esta fórmula: =COINCIDIR(F5;E$1:E$2000;0). En ella F5 es el valor 5 y E$1:E$2000 el rango de búsqueda (hemos llegado a 2000 elementos). El 0 final indica que buscamos valores exactos, y la función nos devuelve 129, que es la posición en la que aparece el 5, como puedes ver en este recorte de la tabla:

En ella también aparece el 131, número de orden del 4.

Si hubiéramos creado una tabla de muchos más términos terminaríamos por encontrar en ella todos los números naturales. Eso es lo que conjetura Sloane.

Función RECAMAN(n)

El desarrollo anterior puede ser más o menos interesante, pero, como hemos procedido en casos parecidos, sería muy útil obtener un valor de la sucesión por cálculo directo (en realidad, en su interior sería recursivo), de forma que dado un número de orden, existiera una función que nos devolviera el término correspondiente de la sucesión de Recaman. Esto choca con el mismo inconveniente que en el caso del cálculo progresivo, y es el almacenamiento de los valores anteriores. Esa función debería contener un vector o tabla que memorizara dichos valores. En el Basic de las hojas de cálculo no existe un dimensionamiento dinámico de un vector en función de n, por lo que no sería práctico. Por ello hemos pensado almacenar los valores previos en un string o cadena de caracteres, que crece dinámicamente sin problemas.

La función cuya codificación presentamos ahora almacena los valores previos de la sucesión en el string prev$, pero para que no se den ambigüedades, rodea cada número de dos almohadillas #, es decir, almacenamos un 12 como #12#, para evitar que se confunda con 112, que sería #112# en nuestro sistema. Es un truco que nos evitará muchos problemas. También deberemos suprimir el espacio en blanco que las hojas añaden a los números, pues, si no, el 12 se podría codificar como # 12# y no ser detectado. Este cambio lo efectuará la función AJUSTA, que es la siguiente (quien no tenga interés en esto puede pasar a la función principal):

Public Function ajusta(a$) As String
If Mid(a$, 1, 1) = " " Then a$ = Right$(a$, Len(a$) - 1)
ajusta = "#" + a$ + "#"
End Function

Disponiendo de esta función auxiliar ya podemos describir la función RECAMAN(n). Es esta:

Public Function recaman(n)
Dim prev$, sd$
Dim d, ant, reca, i

prev$ = " #1# "
ant = 1   ‘Inicia los valores de la sucesión de Recaman

If n = 1 Then
reca = 1 ‘Caso en el que n=1
Else

For i = 2 To n
d = ant – i ‘Calculamos la diferencia a_n-1 – n

If d > 0 Then
sd$ = ajusta(Str$(d)) ‘Si la diferencia es positiva, vemos si ya figura en la sucesión
If InStr(prev$, sd$) = 0 Then ‘Usamos InStr para ver si la diferencia figura en el string
reca = d ‘Si no está, la admitimos como nuevo valor
Else
reca = ant + i ‘Si ya figura en la sucesión, usamos la definición alternativa
End If
Else
reca = ant + i ‘Si es negativa, también usamos la definición alternativa
End If

sd$ = Str$(reca) ‘Incorporamos el nuevo término al string que los recuerda
prev = prev + ajusta(sd$)
ant = reca
Next i

End If
recaman = reca
End Function

Copia, si así lo deseas, estas dos funciones en tu hoja de cálculo, y así podrás jugar un poco con esta sucesión. Por ejemplo, puedes descubrir estas curiosidades o ampliarlas:

Elementos repetidos

El primer caso de términos repetidos en la sucesión de Recaman es el 42, que aparece en el índice 20 y en el 24: recaman(20)=recaman(24)=42. Dado un término, no es difícil encontrar el siguiente con el mismo valor. Hemos señalado que el primer repetido es el 42, en los lugares 20 y 24 Dado otro valor, ¿existirá otro con el mismo valor?¿cuál será la siguiente aparición?
Esta cuestión y otras parecidas podemos resolverla con esta función:

Public Function sig_recaman(indi)
Dim v, j, v1

v = recaman(indi)
j = indi
v1 = 0
While v <> v1
j = j + 1
v1 = recaman(j)
Wend
sig_recaman = j
End Function

En ella, dado un número de orden, se busca la siguiente aparición del término correspondiente a ese número de orden. Se le incluye un tope de 10^4  para evitar el bloqueo de la función. Como esta última situación es la más frecuente, sólo destacaremos los casos contenidos en http://oeis.org/A064284
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1,…

En ellos se descubre que repeticiones hay pocas, y casi siempre de sólo dos elementos. Con nuestra función sig_recaman se pueden comprobar algunas:

Recaman(20)=recaman(24)=42

Otros casos tardan mucho en aparecer y no merece la pena seguir por este camino.

Términos iguales a su número de orden

También existen muy pocos. Se puede plantear que recaman(n)=n y ver qué pasa. Sólo encontraremos recaman(1)=1, recaman(1520)=1520, recaman(9317)=9317 y alguno más. Los demás, si existen, sobrepasan nuestra capacidad de cálculo, ya que pertenecerían a esta sucesión

http://oeis.org/A064568

3, 11, 21, 39, 76, 248, 844, 1520, 2752, 9317, 17223, 31221, 57071, 99741, 589932, 58056875, en los que el término es múltiplo del número de orden.

El mismo caso, pero con una unidad de diferencia

¿Pueden ser n y recaman(n) número consecutivos en cualquiera de los dos sentidos?
Podemos plantear la condición ABS(RECAMAN(N)-N)=1 y hemos encontrado recaman(2)=3 y recaman(10)=11. Entre los números menores que 3000 no hay más.

A continuación incluimos la tabla de los números N menores que 1000 cuya diferencia con RECAMAN(N) es menor que 10

Una vez que tienes a tu disposición la función RECAMAN puedes emprender tus propias búsquedas.

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.

Formas de ser un número equilibrado (3)

Equilibrados como media de números semejantes

Esta es la última entrada de la temporada 2014-15. Al igual que en años anteriores, nos tomaremos dos meses de descanso y preparación de material. Volveremos en septiembre si seguimos con fuerzas y aparecen nuevos temas, que cada vez son más difíciles de encontrar. 

Saludos a todas/os

Existen números equilibrados que son media entre el anterior y el posterior de la misma clase. Así, un número primo es equilibrado si es promedio de sus dos primos contiguos. Por ejemplo, 257 es media de su anterior 251 y el posterior 263, que por cierto también es primo equilibrado. Los tres primos componentes de la terna formarán, pues, una progresión aritmética.

Los primos equilibrados los tienes en http://oeis.org/A006562

5, 53, 157, 173, 211, 257, 263, 373, 563, 593, 607, 653, 733, 947, 977, …

Si dispones de las funciones ESPRIMO, PRIMANT y PRIMPROX (las puedes encontrar en http://www.hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#global ), es fácil encontrarlos. Por ejemplo, con esta función:

Public Function equiprimo(n)
If esprimo(n) And n = (primprox(n) + primant(n)) / 2 Then equiprimo = True Else equiprimo = False
End Function

Con ella es fácil reproducir la lista:

Las diferencias, salvo en el 5, son múltiplos de 6. La razón es que a partir del 5 todos los primos son del tipo 6n+1 o 6n+5. En las ternas que se forman tienen que ser todos del mismo tipo, ya que si el primero es 6n+1 y el segundo 6m+5, el tercero tendría el tipo 6m+5+(6k+4)=6h+3, no primo. Igualmente, si el primero es tipo 6n+5 y el segundo 6m+1, el tercero sería 6m+1+(6h+2). Lo puedes ver con Z₆: Si el primero tuviera resto 1 y el último resto 5, el promedio presentaría resto 3 y no sería primo. Igual con los otros casos. Una consecuencia curiosa de esto es la sucesión publicada en http://oeis.org/A101597, que cuenta el número de compuestos comprendidos entre el primo equilibrado y sus contiguos, y es claro que todos los elementos tienen el valor 5, 11, 17,…es decir, un múltiplo de 6 menos 1.

Se ha conjeturado que existen infinitos primos equilibrados.

Otros números equilibrados

Con cuadrados

Ningún cuadrado como tal puede ser equilibrado, ya que (n+1)²-n²=2n+1 y n²-(n-1)²=2n-1. Igual le ocurre a los triangulares, ya que, por definición, la diferencia entre el triangular de orden n y su anterior es precisamente n, y con su posterior, n+1. No busques equilibrados entre números poligonales o procedentes de valores numéricos de polinomios.

Así que tendremos que ir visitando otros tipos de números hasta dar con aquellos que presenten elementos equilibrados.

Libres de cuadrados

Este tipo de números sí admite equilibrados. Los tienes en http://oeis.org/A245289

2, 6, 14, 17, 19, 22, 26, 30, 34, 38, 42, 53, 55, 58, 66, 70, 78, 86, 89, 91, 94, 102, 106, 110, 114, 130, 138, 142, 158, 161, 163, 166, 170, 178, 182, 186, 194, 197, 199, 202, 210, 214, 218, 222, 230, 233, 235, 238,…

Los hemos reproducido con hoja de cálculo, incorporando sus factores primos, y nos ha llamado la atención que en la terna de libres de cuadrados consecutivos figuran muchos primos, lo que hace que el M.C.D. de los integrantes de la terna sea frecuentemente un 1.

Hemos buscado factores comunes en muchas ternas, hasta 10^8, y sólo hemos encontrado el 2. No parece que tengan en común los factores 3, 5 o 7. Si aparece este caso, será para números muy grandes. Con PARI hemos obtenido listados de ternas con M.C.D. igual a 2, pero no para valores mayores. No tenemos respuesta para la cuestión de si terminarán apareciendo.

Semiprimos equilibrados

También se pueden encontrar ternas de semiprimos consecutivos que formen progresión aritmética, con lo que el central de la terna sería un semiprimo equilibrado. Son estos:

34, 86, 94, 122, 142, 185, 194, 202, 214, 218, 262, 289, 302, 314, 321, 358, 371, 394, 407, 413, 415, 422, 446, 471, 489, 493, 497, 517, 535, 562, 581, 586, 626, 634, 669, 687, 698, 734, 785, 791, 815, 838, 842, 922, 982, 989, 1042, 1057, 1079, 1135, 1138,… http://oeis.org/A213025

Podemos investigar aquí también qué factores comunes tienen estas ternas de semiprimos. Hemos encontrado ternas con el factor 2 en común:

En ellas los otros factores que acompañan al 2 son ternas de primos equilibrados.

Esfénicos equilibrados

Existen esfénicos (productos de tres primos distintos) que son equilibrados, es decir, que forman ternas en progresión aritmética con el anterior y el posterior esfénico. Forman esta sucesión:

186, 370, 406, 418, 518, 582, 602, 710, 786, 814, 826, 830, 942, 978, 994, 1010, 1034, 1070, 1162, 1310, 1374, 1394, 1570, 1630, 1686, 1758, 1886, 1978, 2014, 2114, 2158, 2270, 2274, 2278, 2294, 2438, 2510, 2534, 2570, 2630, 2666, 2690, 2774, 2778, 2782, 2806, …

Entre ellos figura el año 2014, que ya se comentó en su día que formaba una terna de esfénicos con el 2013 y el 2015.

Los hemos publicado en http://oeis.org/A258276
(Aprobada y pendiente de publicación)
Siguiendo con la idea de estudiar el MCD de los tres elementos de la terna, aquí encontramos una gran variedad de números primos como resultado, entre ellos 705, 710 y 715 con factor común 5, o  3311, 3322 y 3333 con el 11. Al tener tres factores es más fácil obtener estos resultados.

Podríamos estudiar la misma cuestión con números formados por el producto de cuatro primos distintos, y también encontraríamos equilibrados:

1518, 1554, 2190, 2590, 3354, 4710, 4970, 5810, 7566, 8170, 10506, 11110, 11346, 12194, 12610, 13706, 14098, 15690, 16874, 17574, 18538, 18734, 19830, …

No hemos querido seguir para no cansar a los lectores. Si estudias el código PARI que hemos usado puedes proseguir el estudio en esa dirección, cambiando el 4 por 5, 6 o 7.

is4prim(n)=if(n>0,omega(n)==4&&bigomega(n)==4,0)
next4prim(n)={local(k=n+1);while(!is4prim(k),k+=1);k}
prec4prim(n)={local(k=n-1);while(!is4prim(k)&&k>0,k-=1);k}
{for(i=1,10^4,if(is4prim(i)&&2*i== next4prim(i)+ prec4prim(i),print(i)))}