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: 1²=1, 3²=2 y 2²=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 x²ºa, o, con los cambios adecuados, la ecuación general de segundo grado. Lo vemos con un ejemplo:

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

Damos estos pasos:

x²-26x+10 º (x-13)²-159 º 7 (mod 11)
(x-13)²º166 (mod 11)
(x-13)²º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: 3²-26*3+10=-59 º-4 º 7 (mod 11) y 1²-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 1², 2², 3²,…,((p-1)/2)² y por tanto, este también es el número de no-restos.

Previamente estudia esta propiedad:

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

En efecto, si tiene una solución x1 con x1²º 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 1², 2², 3²,…,((p-1)/2)² no se repiten , ya que una igualdad entre ellos haría que la ecuación  x²º 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  1², 2², 3²,…,((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 .1², 2², 3²,…,((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.