Factorización de un primo de la forma 4k+1 en el anillo de los enteros gaussianos

Este artículo es una colaboración enviada por fede a gaussianos (arroba) gmail (punto) com.

Introducción

Un número primo de la forma $4k+1$ es suma de los cuadrados de dos números enteros. Además la representación $p=x^2 + y^2$ es única si $0 < x < y$ .

Como $x^2 + y^2 = (x+iy)(x-iy)$ , la representación anterior da una factorización de un primo natural $p = 4k+1$ en el anillo de los enteros gaussianos. Además los factores $(x+iy)$ y $(x-iy)$ son primos en ese anillo.

Este post describe cómo obtener los enteros $x,y$ que son solución de $p=x^2 + y^2$ .

Describiendo el algoritmo

Podemos probar con un programa valores sucesivos de $x$ hasta que encontremos la solución de $x^2+y^2=p$ , y eso puede funcionar para primos pequeños como 100123456789 y 100987654321, pero no sirve para primos algo más grandes como el primo gemelo titánico más pequeño o el primo más pequeño de 2000 dígitos decimales.

La demostración de Zagier de que un primo de la forma $4k+1$ es suma de dos cuadrados tampoco da un método práctico para encontrar la solución, ni las de Euler, Lagrange o Dedekind.

Tampoco la fórmula explícita de Gauss

$x \equiv \dfrac{(2k)!}{2(k!)^2} \pmod{p}, \quad y \equiv (2k)!x \pmod{p}$

es útil para calcular los valores de $x$ e $y$ .

Sin embargo existe un algoritmo muy simple para obtener la solución. Podemos describirlo de la siguiente forma:

Obtenemos un $r < p$ tal que $r = \pm \sqrt{-1} \pmod{p}$ , es decir, $r^2 \equiv -1 \pmod{p}$ .

A continuación aplicamos el algoritmo de Euclides a $\dfrac{p}{r}$ . El primer resto que encontramos menor que $\sqrt{\dfrac{p}{2}}$ es el valor de $x$ y el resto anterior es el valor de $y$ .

El algoritmo se deriva de las demostraciones de Serret, Hermite y H.J. Smith, las primeras publicadas en el “Diario de Liouville” en 1848 y la última en el “Diario de Crelle” en 1855.

Calculadora de las componentes de los factores

Podéis probar el algoritmo introduciendo un primo en la casilla de abajo. Para encontrar primos de algunos centenares de dígitos, podéis copiar y pegar en la casilla de abajo primos cuyas 2 últimas cifras sean de la forma $4k+1$ desde las páginas de “Prime Curios!”.

Paso	Resultado	Duración
1. Validación de entrada
2. Busca no-residuo
3. Calcula raíz de -1
4. Alg.Euclides sobre p/r
5. Comprobación
	x =
	y =

Descripción de la calculadora

El paso 1 sólo verifica que el número introducido sea de la forma 4k+1.
Los dos siguientes pasos sirven para obtener $r = \sqrt{-1} \pmod{p}$ , y están basados en los resultados de la teoría elemental de residuos cuadráticos.
En el paso 2 se busca un no-residuo cuadrático $t$ (es decir, un número que no sea un cuadrado $\pmod{p}$ ). Como la mitad de los números menores que $p$ son no-residuos, y es rápido determinar si un número es o no un residuo cuadrático (calculando el símbolo de Jacobi), probando con números al azar podemos obtener rápidamente un no-residuo cuadrático.
Sin embargo no está demostrado (todavía) que exista algoritmo determinista en tiempo polinomial para obtener un no-residuo cuadrático.

La implementación devuelve el menor no-residuo, si éste es menor que 2000.
Una vez que tenemos un no-residuo $t$ , en el paso 3 se obtiene $r = t^{(p-1)/4} \pmod{p}$ .
Por el criterio de Euler para residuos cuadráticos, $r= \pm \sqrt{-1} \pmod{p}$ .
Que el paso 4 nos da la solución se justifica por el teorema de Serret:

Si $r^2 \equiv -1 \pmod{p}, \ r < p$ , la lista de cocientes parciales del desarrollo en fracción continua de $\dfrac{p}{r}$ es simétrica (omando la lista de longitud par, lo que siempre es posible porque ${}[a_0, \ldots, a_n] = [a_0, \ldots, a_n-1, 1]$ ).

A partir de los resultados mencionados en el post sobre fracciones continuas finitas, y con la notación usada alli, resulta que $p = N[a_0,\ldots,a_h,a_h,\ldots ,a_0] = N[a_0,\ldots,a_h]^2 + N[a_0,\ldots,a_{h-1}]^2$ .

Por ser simétrica la fracción continua, los restos que se obtienen al aplicar el algoritmo de Euclides a $\dfrac{p}{r}$ son los numeradores de los convergentes parciales (en orden inverso) y por tanto no hace falta calcular los numeradores de dichos convergentes parciales. Basta con aplicar el algoritmo de Euclides a $\dfrac{p}{r}$ hasta que obtengamos un resto menor que $\sqrt{\dfrac{p}{2}}$ .
Por último, en el paso 5 se comprueba si los valores obtenidos cumplen $x^2 + y^2=p$ . Si no se cumple la igualdad, se concluye que el número $p$ introducido no es primo (y los valores de $t,r$ no serán, en general, correctos).

El teorema de Serret se demuestra fácilmente usando la relación entre numeradores y denominadores de los convergentes parciales consecutivos y las reglas de formación de esos numeradores y denominadores. De ese teorema se obtiene una demostración de que un primo de la forma $4k+1$ es suma de dos cuadrados, que pertenece al grupo de demostraciones que parten de que, para un primo de esa forma, -1 es un cuadrado $\pmod{p}$

En cambio la demostración de H.J. Smith que exponemos a continuación no hace uso de este hecho.

La demostración de H.J. Smith

Usamos la notación ${}[ a_0, a_1, \ldots, a_n ]$ para representar la fracción continua finita cuyos cocientes parciales son $a_0,a_1, \ldots ,a_n$ . Designamos con $N[ a_0, a_1, \ldots, a_n ]$ el numerador de la fracción ${}[ a_0, a_1, \ldots, a_n ]$ .

Como ${}[a_0, a_1, \ldots, a_{n-1}, 1 ] = [a_0, a_1, \ldots, a_{n-1} + 1 ]$ , asumimos que el último cociente es siempre mayor que 1.

En el post sobre fracciones continuas vimos que se cumple

$N[a_0, a_1, \ldots, a_n ] = N[a_n, a_{n-1}, \ldots, a_0 ]$ ,
$N[a_0,\ldots,a_k,\ldots,a_n] = N[a_0,\ldots,a_k] N[a_{k+1},\ldots,a_n] + N[a_0,\ldots,a_{k-1}] N[a_{k+2},\ldots,a_n]$

Estas identidades implican:

(1) $N[a_0,\ldots,a_h,a_h,\ldots ,a_0] = N[a_0,\ldots,a_h]^2 + N[a_0,\ldots,a_{h-1}]^2$ .
(2) $N[a_0,\ldots,a_h,a_{h+1},a_h,\ldots ,a_0] = N[a_0,\ldots,a_{h}] ( N[a_0,\ldots,a_{h+1}] + N[a_0,\ldots,a_{h-1}] )$ .

De esta última igualdad se concluye que si $a_0$ es mayor que 1 (y hay más de un cociente), $N[a_0,\ldots,a_h,a_{h+1},a_h,\ldots ,a_0]$ no es primo.

Para un primo de la forma $4k + 1$ , sea $S$ el conjunto de las fracciones $\dfrac{p}{i}, \ \ 2 \le i \le \dfrac{p-1}{2}$ , desarrolladas en fracción continua.

En el desarrollo en fracción continua de $\dfrac{p}{i} = [a_0, a_1, \ldots, a_n ]$ se tiene que $a_0 \ge 2$ , porque $i \le \dfrac{p-1}{2}$ , y $a_n \ge 2$ porque asumimos que el último cociente es mayor que 1.

La función $f([a_0, \ldots, a_n ]) = [a_n, \ldots, a_0]$ asocia a cada elemento de $S$ otro elemento de $S$ , porque el numerador de una fracción continua no se altera si se invierte el orden de los cocientes y el denominador es un número menor que $\dfrac {p}{2}$ , porque $a_n \ge 2$ .

La función $f$ es entonces una involución de $S$ .

Si $p=4k+1$ , el número de elementos de $S$ es $2k-1$ , un número impar, y entonces $f$ tiene por lo menos un punto fijo, es decir, existe un $r, \ 2 \le r \le \dfrac{p-1}{2}$ que da una fracción continua simétrica $\dfrac{p}{r} = [a_0, \ldots, a_h, a_h, \ldots, a_0]$ (por la observación (2) anterior, el número de cocientes ha de ser par porque $p$ es primo).

Entonces $p$ es suma de 2 cuadrados por la observación (1) anterior.

Sea $\dfrac{p}{r} = [a_0, \ldots, a_h, a_h, \ldots, a_0 ] = \dfrac{N[a_0, \ldots, a_h , a_h, \ldots, a_0]}{D[a_0, \ldots, a_h , a_h, \ldots, a_0]}$ .

Como

$D[a_0,a_1,\ldots a_n] = N[a_1,\ldots a_n], \ \ r=N[a_1,\ldots a_h, a_h, \ldots, a_0]$

y como

$N[a_0 \ldots,a_n] N[a_1, \ldots,a_{n-1}] - N[a_0 \ldots,a_{n-1}] N[a_1, \ldots,a_n] = (-1)^{n-1}$

tenemos que

$p N[a_1,\ldots,a_h,a_h,\ldots, a_1] - r^2 = 1$

y por tanto

$r^2 \equiv -1 \pmod{p}$

7 comentarios

josejuan | 6 de February de 2010 | 02:43

Me quedo estupefacto al leer en la página 139 del libro “El camino a la realidad” de Roger Penrose la siguiente identidad

$1+x^{2}+x^{4}+x^{6}+x^{8}+\cdot \cdot \cdot =(1-x^{2})^{-1}$

sin imponer ninguna restricción a $x$

pero además, se queda tan ancho al evaluar dicha expresión para $x=2$ ¡y no negar que sea correcto el valor evaluado de $-1/3$ ! por supuesto, no lo aclara (al menos en ese capítulo).

En mi opinión, la suma de dicha serie es clara

$S(n)=1+x^{2}+x^{4}+x^{6}+x^{8}+\cdot \cdot \cdot+x^{2(n-1)}$
$x^{2} S(n)=x^{2}+x^{4}+x^{6}+x^{8}+\cdot \cdot \cdot +x^{2n}$
$x^{2} S(n) - S(n) = x^{2n} - 1$
$S(n) = \frac{x^{2n}-1}{x^{2}-1}$

ahora, tomando límites tenemos

$S=\lim_{n\rightarrow \infty }\frac{x^{2n}-1}{x^{2}-1}$

que para $x=1$ no está definido, para x>1 es $\infty$ y para $x<1$ toma el valor $\left( \allowbreak 1-x^{2}\right) ^{-1}$ ¡pero para $x<1$ !

¿Estoy en un error o es que se quiere reir de nosotros hasta aclararlo más tarde?
josejuan | 6 de February de 2010 | 03:04

(Cuando acoto $x$ realmente debería haber puesto $|x|$ )
Dani | 6 de February de 2010 | 17:17

sí, algún compañero desorientado de físicas me preguntó sobre ese extracto del libro de penrose. no sé qué pretende ilustrar con ese ejemplo, si avisar de tener cuidado con las series y sus radios de convergencia o si simplemente es una “broma” que decidió gastar…
es como ese famosa demostración de 2=1 metiante una disimulada división por cero que siempre deja de piedra a los estudiantes de primero jejejej
Naka Cristo | 6 de February de 2010 | 22:12

Supongo que se estará refiriendo a su continuación analítica.
Jonas Castillo Toloza | 10 de February de 2010 | 16:48

Alguien que me explique, por favor
Si expreso un entero de la forma (4n+1) como suma de dos cuadrados de dos maneras distintas,¿còmo hago para descomponer este nùmero como producto de dos factores?
Y tambièn el proceso inverso.
(es claro que este (4n+1) es compuesto en este caso)
fede | 10 de February de 2010 | 19:56

Jonas, aquí dice algo:
http://es.wikipedia.org/wiki/M%C3%A9todo_de_factorizaci%C3%B3n_de_Euler
o
http://mathworld.wolfram.com/EulersFactorizationMethod.html
Jonas Castillo Toloza | 16 de February de 2010 | 21:56

Gracias fede