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.