lunes, 17 de noviembre de 2014

Sucesión de Perrin


En la pasada temporada dedicamos varias entradas a las sucesiones definidas mediante una recurrencia de segundo orden. Ahora comenzaremos una serie sobre las de tercer orden. Entre ellas son muy populares las de Perrin y Padovan. Como en las anteriores, nuestro planteamiento no será teórico, pues ya existe mucho publicado sobre ellas. El objetivo será crear esquemas y cálculos que faciliten  la comprensión de sus propiedades.

Sucesión de Perrin

La teoría fundamental sobre esta serie la puedes consultar en

http://mathworld.wolfram.com/PerrinSequence.html
http://en.wikipedia.org/wiki/Perrin_number

Aquí la describiremos con la ayuda de la herramienta que hemos ofrecido en entradas anteriores, alojada en

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

Definición

Esta sucesión es recursiva de tercer orden homogénea, por lo que necesita tres valores iniciales y que X(n) dependa de los tres valores anteriores X(n-1), X(n-2) y X(n-3) mediante la relación

Xn= A*Xn-1+B*Xn-2+C*Xn-3

En este caso particular sólo depende de los dos últimos, y no de X(n-1). Concretando:

Condiciones iniciales: X0=3   X1=0  X2=2 Ecuación de recurrencia: Xn= Xn-2+Xn-3

Es como una sucesión del tipo Fibonacci pero “con retraso”, pues los que se suman no son los dos anteriores, sino los que están un paso más atrás.

En nuestra hoja de cálculo se define así (segunda hoja del libro):



El primer coeficiente es nulo, que es lo que produce el “retraso”, y debajo tienes los tres valores iniciales.

La sucesión resultante la vemos pulsando el botón correspondiente:


Esta popular sucesión la tienes disponible en http://oeis.org/A001608, donde les llaman números skiponacci, quizás por los saltos o retardos que presentan: 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, 90, 119, 158, 209, 277, 367, 486, 644, 853,…

Ecuación característica

La ecuación característica correspondiente será X3-x-1=0. Con el botón Resolver de esa hoja obtienes las tres soluciones de la ecuación, una real y dos complejas



Coinciden con las soluciones que da WxMaxima



La solución real 1,32471…(aquí sólo aproximada) es el número plástico y, cuyo nombre se eligió como afín al número de oro o el de plata. En estas páginas puedes estudiarlo más a fondo:

http://es.wikipedia.org/wiki/N%C3%BAmero_pl%C3%A1stico
http://revistasuma.es/IMG/pdf/57/055-064.pdf http://cscmates.blogspot.com.es/2010/11/el-numero-de-plastico.html

Recordemos que, como en sucesiones anteriores, todo número de Perrin es combinación lineal de las potencias de las tres soluciones de la ecuación característica, pero las dos complejas tienen módulo menor que la unidad, por lo que sus potencias tenderán a cero en valor absoluto. Por tanto, X(n) se acercará asintóticamente a yn

Se puede construir una tabla doble en la que se observe este acercamiento:



A partir de un cierto orden basta redondear la potencia para obtener el número de Perrin  correspondiente. Lo puedes comprobar en las últimas filas de la tabla.

Función generatriz

Usando procedimientos similares a los que explicamos para las recurrentes de segundo orden, se puede demostrar que la función generatriz es

Puedes comprobar que esta es la F.G. adecuada efectuando este desarrollo en PARI

write("sucesion.txt",taylor((3-x^2)/(1-x^2-x^3),x,20))

Te escribirá en un archivo sucesión.txt su desarrollo, y aparecerán como coeficientes los términos de la sucesión de Perrin:

3 + 2*x^2 + 3*x^3 + 2*x^4 + 5*x^5 + 5*x^6 + 7*x^7 + 10*x^8 + 12*x^9 + 17*x^10 + 22*x^11 + 29*x^12 + 39*x^13 + 51*x^14 + 68*x^15 + 90*x^16 + 119*x^17 + 158*x^18 + 209*x^19 + O(x^20)

Sucesión de Perrin y números primos

La propiedad más conocida de estos números es que si p es primo, p divide a X(p). Por ejemplo, X(11)=22, que es múltiplo de 11. Podemos construir una tabla en la que dividamos X(n) entre n y los cocientes enteros se corresponderán con los números primos:



A pesar de su carácter algo extraño, la propiedad ha sido demostrada para todos los números primos. La contraria no es cierta. X(n) puede ser múltiplo de n sin que este sea primo. A estos términos se les suele llamar pseudoprimos de Perrin (http://oeis.org/A013998):

271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291,…

Otras propiedades

La paridad de X(n) recorre el ciclo {1, 0, 0, 1, 0, 1, 1} Es fácil de ver: las tres primeras vienen determinadas por la definición (en color rojo en la imagen). Las siguientes dependen de dos anteriores. Por tanto, existirá ciclo si se vuelve a repetir el par 1 0, y esto ocurre siete lugares más adelante (color verde):


Para ampliar el tema puedes visitar http://www.mathpages.com/home/kmath345/kmath345.htm en el que se incluye la espiral triangular creada con estos números.


Propiedades matriciales

Estas entradas sobre sucesiones recurrentes también se plantean el objetivo de un mayor conocimiento de las hojas de cálculo. Por eso vamos a aprovechar las propiedades matriciales de la sucesión de Perrin para  repasar este tipo de funciones.

La primera propiedad matricial se resume en la siguiente fórmula para n>2:


Recuerda que la traza es la suma de los elementos de la diagonal principal de una matriz cuadrada.
Para comprobarlo con una hoja de cálculo organizaremos este esquema:


Comenzamos escribiendo a la izquierda la matriz M dos veces, y a la derecha las multiplicamos.
Para ello usaremos la función matricial MMULT, pero como es de tipo matricial deberás seleccionar la matriz de la derecha (debajo del rótulo “Potencia n de M), después escribir una fórmula similar a esta: =MMULT(C3:E5;G3:I5), tomando como rangos los de las matrices de la izquierda. Cuando escribas la fórmula no termines con Intro, sino con la combinación Ctrl+Mayúsc+Intro, para indicar que la fórmula es de tipo matricial. Notarás que lo has escrito bien porque la fórmula se verá entre corchetes.

A la derecha de las matrices puedes incluir la traza de la tercera, que en la imagen te da 2. Después copia la tercera sobre la primera matriz con copia sólo de valores, y te resultará el siguiente número de Perrin, en este caso 3, porque esta propiedad genera la sucesión a partir del tercer término.
Seguirían 2, 5, 5, 7, 10,…

Variante de la anterior expresión

Si en lugar de usar la traza empleamos un producto por la matriz (en vertical) (3, 0, 2), obtenemos tres términos en lugar de uno. La expresión sería ahora:



Bastaría borrar la traza en el anterior esquema y sustituirla por otro nuevo producto matricial con la (3, 0, 2). Lo dejamos como ejercicio. Aquí tienes la generación de los términos 5, 7 y 10






martes, 4 de noviembre de 2014

Comprobar conjeturas con hoja de cálculo. Goldbach.


La formulación más simple de la Conjetura de Goldbach es:

Todo número par mayor que 2 es suma de dos primos

Fue propuesta por Goldbach el 7 de Junio de 1742, en una carta dirigida a Euler.  En realidad, su propuesta se refería a la conjetura ternaria: " Todo número impar es la suma de tres primos" y Euler le respondió con la propuesta binaria que todos conocemos.

Ha sido comprobada hasta números muy grandes, pero no se ha podido demostrar. No obstante, se han logrado resultados provisionales:

Cualquier número par es suma de 6 o menos números primos.(Ramaré 1995)

Todo número par suficientemente grande es suma de un primo y del producto de dos primos.(Chen 1966)

Todo número impar N mayor que 5 es suma de tres primos. (Demostración de la conjetura ternaria a cargo de Vinogradov en 1937).

En esta entrada sólo nos plantearemos, como en toda la serie que vamos desarrollando sobre conjeturas, la comprobación de algunos aspectos de la misma mediante el uso de la hoja de cálculo.

Primer nivel

Comprobaremos la conjetura en tres niveles distintos, según el uso que se haga del lenguaje de macros. En primer lugar lo efectuaremos con las técnicas usuales de las hojas de cálculo. Usaremos la hoja Conjeturas, alojada en la página

http://www.hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#global

(Búscala en la relación de herramientas)

Organizaremos la comprobación según un esquema similar a este:





Escribimos un número par mayor que 2 en una celda. En la imagen es el 612. Después ordenamos los números primos en columna, hasta el límite que queramos. Para ello escribimos el 2, debajo primprox(2) (función implementada en esta hoja, y que encuentra el primo siguiente a uno dado).

Rellenamos hacia abajo y nos resultará la lista de primos.

En una segunda columna escribiremos una fórmula similar a a siguiente, que copiaremos de arriba a abajo:

=SI(Y(F15<=H$11/2;esprimo(H$11-F15));H$11-F15;"")

En ella H11 es la celda donde hemos escrito el 612. En tu caso podrá ser otra. La F15 en nuestro esquema apunta al número primo que tiene a su izquierda. De esa forma, la podemos interpretar así: “Si el primo no llega a la mitad del número par probado (aquí el 612) y su diferencia con él es otro primo, escribo esa diferencia, pero en caso contrario dejo la celda en blanco”.

Es sencillo de entender y funciona escribiendo los pares de primos en los que se descompone el 612. En la imagen 5+607, 11+601, 19+593,…hasta un total de 26 pares. Si no logras ese número, deberás rellenar hacia abajo las dos columnas hasta llegar a la mitad de 612

Este esquema puede aclarar, probando con varios pares, el sentido de la conjetura. También te da confianza en ella, pues no sólo existe un par de primos para cada número par, sino muchos. ¡Pero no se ha probado aún!

Nivel 2

Ya que con el esquema anterior nos han resultado varias descomposiciones en primos para cada número par, podíamos simplificar mucho si lo plasmáramos en una función. En la hoja de cálculo que estamos usando hemos implementado NUMGOLDBACH(N), que devuelve un cero si N no es par y el número de descomposiciones si es par. En el caso del 612 devuelve correctamente 26.



Aquí tienes los primeros resultados. Si la conjetura es cierta, deberán ser todos mayores que 0. Están recogidos en http://oeis.org/A045917

Merece la pena recorrer la codificación de esta función y así entenderás mejor las cuestiones.

Public Function numgoldbach(n)
Dim ng, i

If n <> 2 * Int(n / 2) Then  ‘si es impar devuelve un cero (valor de ng
ng = 0
Else
i = 2: ng = 0
While i <= n / 2  ‘si es par recorre todas las posibles sumas de primos
If esprimo(n - i) Then ng = ng + 1 ‘si el segundo sumando es primo, incrementa el contador ng
i = primprox(i) ‘esta línea asegura que el primer sumando sea primo
Wend
End If
numgoldbach = ng
End Function

Nivel 3

Podemos dejar que sea la hoja de cálculo la que recorra automáticamente los primeros números hasta un tope o hasta que numgoldbach dé un cero. Como lo segundo es imposible para números pequeños (ya está comprobada la conjetura), el resultado final será siempre un cero.

Podíamos usar un esquema similar al siguiente:



Escribimos un tope, pulsamos el botón e irán apareciendo valores de Numgoldbach, ninguno nulo, hasta finalizar la búsqueda. Si uno fuera cero, se interrumpiría el proceso con un solemne mensaje. La programación del botón podría ser similar a esta:

Sub buscagoldbach()
Dim i, g, p

p = ActiveWorkbook.Sheets(1).Cells(5, 3).Value ‘lee el tope
i = 4 ‘inicio búsqueda
g = 1’inicio valor de numgolbach
While g <> 0 And i <= p
i = i + 2 ‘busca de 2 en 2
g = numgoldbach(i)
ActiveWorkbook.Sheets(1).Cells(6, 3).Value = g ‘escribe el valor de g
If g = 0 Then MsgBox ("¡Contraejemplo!") ‘Esto no va a ocurrir
Wend
End Sub

Variantes

Variante ternaria

“Todo número impar mayor que 5 es la suma de tres primos"

No vamos a repetir con ella los tres niveles anteriores. El primer nivel necesitaría un estructura de datos tridimensional, poco intuitiva en una hoja de dos dimensiones. El tercero sería semejante al del primer caso. Así que sólo desarrollaremos un esquema con todas las posibles descomposiciones en tres sumandos primos:








Como en el caso anterior, no vamos a analizar si el número es impar o no. Simplemente hemos programado un botón que lo descompone en esos sumandos de todas las formas posibles (lo haremos con sumandos decrecientes)

Para quien le guste la programación, ahí tiene explicado el algoritmo que hemos usado:

Sub goldbach3()
Dim fila, a, b, c, n

fila = 7
n = ActiveWorkbook.Sheets(1).Cells(fila, 3).Value ‘lee el número, que se encuentra en C7
a = 2 ‘primer sumando primo
While a < n ‘ el primer sumando llega hasta n en lo posible
b = 2
While b < a ‘ el segundo es inferior al primero
c = n - a – b ‘tercer sumando
If esprimo(c) And c <= b Then ‘si el tercer sumando también es primo, se presenta el resultado
fila = fila + 1
ActiveWorkbook.Sheets(1).Cells(fila, 3).Value = a
ActiveWorkbook.Sheets(1).Cells(fila, 4).Value = b
ActiveWorkbook.Sheets(1).Cells(fila, 5).Value = c
End If
b = primprox(b) ‘se incrementa el segundo primo
Wend
a = primprox(a) 'se incrementa el primero
Wend
End Sub 

Como era de esperar, siempre aparecen los tres sumandos primos. Se deja a los lectores el definir una función que cuente las soluciones. Siempre existirá al menos una.

Expresión mediante equidistancia

Un comentario a la entrada http://culturacientifica.com/2013/06/26/la-conjetura-de-goldbach/ me ha dado la idea de organizar una comprobación distinta.

Si la conjetura es cierta, para todo número par 2N, si es la suma de dos primos p y q, con p>q, cumplirán que p+q=2N, o bien que p-N=N-q:

Todo número entero positivo mayor que 4 es equidistante de dos primos

Es fácil ver que es otra formulación distinta de la conjetura de Goldbach. En los párrafos anteriores hemos visto la consecuencia directa. A la inversa, si es cierto que todo N equidista de dos primos, dado un par 2N aplicamos p-N=N-q para cierto par de primos, con lo que 2N=p+q. El exigir que sea mayor que 4 es porque no habría primos inferiores para números menores.

Es muy fácil organizar la comprobación con esta variante. Lo efectuaremos en el Nivel 1, de cálculo manual:



Escribimos la lista de números consecutivos 1, 2, 3,…y los sumamos y restamos con el número dado. Después, en la tercera columna, escribimos una fórmula similar a

=SI(Y(ESPRIMO(D9);ESPRIMO(E9));"SI";"") 

que nos devuelve un “SI” si los equidistantes son primos.

En la imagen, 17=29-12 y 41=29+12.




miércoles, 22 de octubre de 2014

Unión e intersección de conjuntos con Excel


De cuando en cuando publicamos en este blog entradas sobre el funcionamiento de las hojas de cálculo, y en concreto sobre la programación en su Basic. La de hoy es una de ellas, así que si no te interesa el tema no sigas, que no vas a encontrar cuestiones sobre números.

Nos vamos a proponer la obtención de la unión y la intersección de dos conjuntos escritos en la hoja como dos columnas paralelas. Lo desarrollaremos en Excel sólo, para no duplicar las explicaciones, pero el contenido se puede adaptar a OpenOffice o LibreOffice. No se busca aquí la utilidad, sino la posibilidad de superar un reto. Lo que construyamos puede que aparentemente no sirva para nada.

Hemos preparado un esquema en el que a partir de la fila 7 se van escribiendo los conjuntos A y B con lo que deseamos operar. Después, con una simple pulsación de un botón, realizaremos las operaciones deseadas.



Intentamos en primer lugar resolver la cuestión sin el uso de macros, pero resultó un proceso tan complejo y artificioso que renunciamos a ello. Así, todo lo que sigue se basará en el lenguaje VBA de Excel. Como se observa en la imagen, se pueden usar números y también letras y palabras. Sólo hay que tener en cuenta que un espacio en blanco cuenta como un elemento, por lo que el borrado se debe realizar con el botón correspondiente o con la tecla Supr, sin escribir nada.

Otro detalle interesante es que en las operaciones se eliminan los elementos repetidos, logrando con ello una gran limpieza en la presentación. En un segundo paso puedes ordenar los resultados sin son más extensos.



Procedimientos necesarios

Recorrido por un conjunto 

Para obtener la unión e intersección de dos conjuntos se requiere, en primer lugar, el poder recorrer un conjunto del que no se sabe en principio cuántos elementos contiene. Para ello usaremos la idea de celda vacía. El recorrido se basará entonces en “avanzo mientras la celda no esté vacía”. Esta condición se puede verificar en VBA con la función IsEmpty, que nos devuelve True si la celda no contiene ningún dato. Con ella es fácil programar un recorrido:

fila = 7
While Not IsEmpty(Cells(fila, columna)) And … (cualquier otra condición)
‘ Aquí las operaciones que deseemos realizar con el elemento.
fila = fila + 1
Wend

Este sencillo esquema se repetirá cada vez que realicemos una operación elemento a elemento: ver si un dato pertenece o no al conjunto, buscar repetidos, incorporar elementos nuevos y otros. Comenzamos por la fila 7, que es donde comienzan nuestros conjuntos y después se va bajando de fila hasta que no queden elementos.

Por ejemplo, la siguiente función ESTA nos devuelve True si un valor n pertenece al conjunto situado en la cierta columna

Public Function esta(n, columna) As Boolean
Dim fila
Dim est As Boolean

est = False
fila = 7
While Not IsEmpty(Cells(fila, columna)) And Not est
If n = Cells(fila, columna).Value Then est = True
fila = fila + 1
Wend
esta = est
End Function

Es fácil identificar la estructura del recorrido por el conjunto. Esta función ESTA nos servirá para saber si podemos agregar un elemento nuevo a un conjunto mediante el procedimiento  AGREGA, que servirá para ir incorporando términos a la unión y a la intersección.

Sub agrega(n, columna)
Dim i

i = 7
While Not IsEmpty(Cells(i, columna))
i = i + 1
Wend
If Not esta(n, columna) Then Cells(i, columna).Value = n
End Sub

Recorre el conjunto, y si no encuentra el elemento dado, baja una fila y lo incorpora.
Con los procedimientos de recorrido y agregación y la función ESTA podemos ya planificar nuestra tarea:


  • Se elige el primer conjunto
  • Se recorre, y para cada elemento:
  • (A) Si no está en la unión, se agrega (así evitamos repetidos)
  • (B) Se compara con todos los elementos del segundo (mediante un recorrido por el mismo) y si está repetido, se incorpora a la intersección si todavía no está.
  • Se repite la tarea con el segundo conjunto, pero esta vez no se busca la intersección, que ya estará resuelta.

Para entender el listado que sigue recuerda que los conjuntos están escritos en las columnas  tercera y cuarta, que la unión se escribe en la quinta y la intersección en la sexta.

Así quedaría:

Option Explicit  ‘Evita el uso de variables no dimensionadas

Public Function esta(n, columna) As Boolean ‘ Ya explicada. Determina si un elemento pertenece a un conjunto
Dim fila
Dim est As Boolean

est = False
fila = 7

While Not IsEmpty(Cells(fila, columna)) And Not est
If n = Cells(fila, columna).Value Then est = True
fila = fila + 1
Wend
esta = est
End Function

Sub agrega(n, columna) ‘También explicada: añade un elemento si aún no está
Dim i

i = 7
While Not IsEmpty(Cells(i, columna))
i = i + 1
Wend
If Not esta(n, columna) Then Cells(i, columna).Value = n
End Sub


Sub union() ‘Esquema general de trabajo. Se inicia al pulsar el botón “Operación”
Dim i, j, n1, n2
Dim esinter As Boolean

i = 7
Call borrar ‘Macro grabada aparte
While Not IsEmpty(Cells(i, 3)) ‘Recorre el primer conjunto


'Se recorre la primera columna
n1 = Cells(i, 3).Value
Call agrega(n1, 5) ‘Agrega el elemento a la unión

'se busca la intersección
j = 7
esinter = False
While Not IsEmpty(Cells(j, 4)) And Not esinter ‘Se recorre el segundo conjunto
n2 = Cells(j, 4).Value
If n1 = n2 Then esinter = True
j = j + 1
Wend
If esinter Then Call agrega(n1, 6) ‘Si está repetido se agrega a la intersección
i = i + 1
Wend
i = 7
While Not IsEmpty(Cells(i, 4))
'Se recorre la segunda columna y se repite el agregar a la unión.
n1 = Cells(i, 4).Value
Call agrega(n1, 5)
i = i + 1
Wend
End Sub

Si lo has entendido, intenta programar la diferencia entre dos conjuntos, los elementos que pertenecen a uno pero no al otro. Puedes repasar la hoja alojada en (http://www.hojamat.es/blog/union de conjuntos.xlsm) y modificarla libremente.

lunes, 13 de octubre de 2014

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 x2 + 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.


lunes, 29 de septiembre de 2014

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 x2ºa (mod p) entonces a(p-1)/2ºxp-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=1411 Calculamos el resto de este último por potencias sucesivas: 141º14 (mod 23), 142º12 (mod 23) 144º12*12º6 (mod 23) 148º6*6º13 (mod 23), luego 1411º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: 701º-31 (mod 101), : 702º31*31º-49 (mod 101), 704º49*49º-23 (mod 101), 708º23*23º24 (mod 101), 7016º24*24º-30 (mod 101), 7032º30*30º-9 (mod 101), y ahora construimos el 50:

7050º70327016702º-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)

martes, 16 de septiembre de 2014

Restos cuadráticos

En esta entrada y otras posteriores trataremos el tema de las congruencias de segundo grado. Usaremos como siempre las hojas de cálculo, y, en especial una herramienta que hemos creado para este fin. Todo el tema gira alrededor de la ecuación

 

Imagina una clase de restos, por ejemplo la correspondiente a módulo 7, {0, 1, 2, 3, 4, 5, 6} Elige un resto, sea el 5. ¿Existirá otro resto que multiplicado por sí mismo dé como resultado 5, módulo 7? Probemos: 1*1º1, 2*2º4, 3*3º2, 4*4º2, 5*5º4, 6*6º1. Así que no es posible, los únicos resultados  son 1, 4 y 2. Nunca resulta un 5, ni tampoco 3 ni 6.

Podemos resumir esta situación calificando 1, 2 y 4 como “restos cuadráticos” y 3, 5 y 6 como “no restos cuadráticos”. También podemos hablar de la “raíz cuadrada” de los primeros: 12=1, 32=2 y 22=4. Es fácil ver que si k es raíz de n, también lo es m-k. Eleva esta última al cuadrado y lo comprobarás.

Esta situación la tendrás siempre. Unos elementos podrán ser restos cuadráticos y otros no. El primer intento que hemos hecho para averiguarlo ha sido el probar los elementos uno a uno hasta conseguir que el cuadrado de uno de ellos coincida con el resto dado, o bien comprobar que esto es imposible y que se trata de un “no resto cuadrado”.

Para estudiar el tema con profundidad puedes acudir a

http://hojamat.es/parra/restocuad.pdf
http://mate.dm.uba.ar/~pdenapo/teoria_analitica_de_numeros/clase11.pdf
http://en.wikipedia.org/wiki/Quadratic_residue

Diremos que a es resto cuadrático módulo p, coprimo con él, cuando exista una solución a la ecuación



Con hoja de cálculo (o con ligeras variaciones, en cualquier lenguaje de programación) podemos automatizar este procedimiento. Definiremos una función, que dependa de un resto dado y del módulo correspondiente, que nos devuelva la raíz cuadrada, con lo que sabremos que es resto cuadrático, o bien un cero si no lo es.

Public Function restocuad(n,modu) ‘los parámetros son el resto y el módulo
Dim k, r,s
Dim es As Boolean

es = False ‘ nos indica que aún no se ha encontrado una raíz
k = 1 ‘contador que busca la raíz
r = 0 ‘raíz encontrada
While k <= modu / 2 And Not es ‘va buscando las posibles raíces
s=(n-k*k)/modu
If s=int(s) Then es = True: r = k ‘se ha encontrado la raíz
k = k + 1 ’seguimos buscando
Wend
If es Then restocuad = r Else restocuad = 0 ‘devuelve un cero si no se ha encontrado
End Function

Con esta función implementada, puedes analizar qué restos son cuadráticos, formar tablas de restos y no restos y resolver la ecuación x2ºa, o, con los cambios adecuados, la ecuación general de segundo grado. Lo vemos con un ejemplo:

Resolver x2-26x+10º7 (mod 11)

Damos estos pasos:

x2-26x+10 º (x-13)2-159 º 7 (mod 11)
(x-13)2º166 (mod 11)
(x-13)2º1 (mod 11)

Buscamos la raíz cuadrada de 1 y resulta ser 1 o -1 (o 10) es decir:

(x-13)º1 o 10 (mod 11)

Despejando: x=3 y x=1

Comprobamos: 32-26*3+10=-59 º-4 º 7 (mod 11) y 12-26*1+10=-15 º-4 ?º7 (mod 11)

Hemos elegido un ejemplo que tenía solución, pero si llega a aparecer un no resto en lugar de 1, no podríamos seguir. Por eso es tan importante saber previamente si un resto es cuadrático o no.

Caso de módulo primo e impar

En este caso, si consultas la teoría descubrirás que si p es el módulo primo e impar resulta que el número de restos cuadráticos es (p-1)/2, que son congruentes con 12, 22, 32,…,((p-1)/2)2 y por tanto, este también es el número de no-restos.

Previamente estudia esta propiedad:

La ecuación x2º a (mod p) para un a dado, o no tiene solución, o tiene dos.

En efecto, si tiene una solución x1 con x12º a (mod p)  también será solución –x1 y sólo tenemos que demostrar que ambas son distintas. Es fácil: si fueran iguales tendríamos que 2x1=0, pero ni 2 ni x1 son divisores del cero, por ser p primo impar. La segunda solución la puedes expresar como p-x1

Por tanto, el número de restos cuadráticos no sobrepasará (p-1)/2. Es más, es igual que ese número, porque los restos de 12, 22, 32,…,((p-1)/2)no se repiten , ya que una igualdad entre ellos haría que la ecuación  x2º a (mod p) tuviera cuatro soluciones en lugar de dos.

Esta propiedad te ofrece un procedimiento para encontrar todos los restos cuadráticos en este caso, y es calcular los valores de  12, 22, 32,…,((p-1)/2)y los resultados serán los restos cuadráticos, y los demás será no restos.

Hemos preparado una herramienta en  hoja de cálculo

 (ver http://www.hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm#restoscuad),

cuya primera prestación es la de encontrar el conjunto de restos y no restos para un módulo primo e impar. En ella está implementado el procedimiento de ir calculando los valores de .12, 22, 32,…,((p-1)/2) La novedad de este esquema es que va situando los restos en una columna y los no restos en otra.



En la imagen figuran los 15 restos módulo 31, sus raíces, y los 15 no restos. Para ver cómo lo logra tendrías que acceder al Basic, pero no lo analizaremos en este momento.

Su funcionamiento en esta parte es muy simple: escribes el nuevo módulo,  y después pulsas el botón de Restos y no restos  para que aparezcan.

Puedes alternar tus cálculos manuales con los de la hoja para entenderlo todo mejor y comprobar resultados.

En la siguiente entrada simplificaremos los cálculos necesarios para saber si un resto es cuadrático o no mediante un criterio debido a Euler.

martes, 2 de septiembre de 2014

Nueva temporada 2014-15


Iniciamos hoy nuestra séptima temporada (o curso) con el anuncio de un nuevo resumen anual de este blog. Lo hemos alojado en 


En la anterior temporada iniciamos dos temas que continuaremos en la presente: comprobaciones de conjeturas y estudio de sucesiones recurrentes. También se publicó un capítulo sobre permutaciones y ciclos, que por ahora consideramos terminado.

Nuestro propósito para la nueva temporada, además de la continuación de los temas citados y de la atención a cuestiones ocasionales y de actualidad, es el de publicar entradas sobre el tema de los restos cuadráticos, con lo que, poco a poco, iremos completando temas teóricos.

En los dos primeros meses, por tener que atender a otras cuestiones personales, nuestras entradas aparecerán con intervalos de unos quince días, en lugar de los diez habituales. Quizás para diciembre recuperaremos la periodicidad acostumbrada, aunque ese mes el autor cumple 73 años y su ritmo de creación va disminuyendo forzosamente.