Logo alpertron

Página principal del sitio de Darío Alpern
See Site in English

 ELECTRÓNICA >> Microprocesadores Intel | Descargas
 MATEMÁTICAS >> Calculadoras | Teoría de Números | Problemas
 PROGRAMAS >> Assembler 80386 (descargas) | Java | Juegos
 CONTACTO >> Personal | Comentarios | Libro de invitados | Enlaces

Todo entero positivo es una suma de cuatro cuadrados perfectos

por Michael Barr

Introducción

El teorema del título se conoce desde hace siglos, pero creo que Lagrange hizo la primera demostración. Cuando era estudiante, vi una demostración muy diferente (y en mi opinión, más complicada) que la que se muestra aquí. No sé quién descubrió esta demostración, pero la vi en el pequeño libro de Alan Baker sobre teoría de números.

Hay otra prueba que usa la factorización única en el anillo no conmutativo de los cuaterniones enteros. Los cuaterniones enteros incluyen (1+i+j+k)/2 y de hecho es el anillo de todos los polinomios en ese número.

Todas las pruebas que vi hasta ahora usan la identidad

(a2+b2+c2+d2) (A2+B2+C2+D2) = (aA+bB+cC+dD)2 + (aB-bA+cD-dC)2 + (aC-bD-cA+dB)2 + (aD-dA+bC-cB)2

que implica que el producto de dos números, cada uno de los cuales es la suma de cuatro cuadrados, es también una suma de cuatro cuadrados. Aunque esta identidad se puede verificar directamente vale la pena indicar que si se toma u=a-bi-cj-dk y U=A+Bi+Cj+Dk, esto es simplemente el cuadrado de la identidad que dice que |uU|=|u||U|. Esto es lo que yo normalmente llamo identidad de producto de cuaterniones. De esta manera la conclusión es que es suficiente realizar la prueba para números primos. Como cada potencia de 2 es obviamente un cuadrado o la suma de dos cuadrados, es suficiente probar que cada primo impar es la suma de cuatro cuadrados.

Posteriormente usaremos lo que se llama la identidad de producto de complejos:

(a2+b2) (A2+B2) = (aA+bB)2 + (aB-bA)2

Aquí daremos una demostración que tiene la ventaja adicional de ser convertida fácilmente en un algoritmo. No es determinístico ya que hay ensayo y error, pero cada ensayo tiene al menos un 50% de probabilidad de éxito. Se asume que el lector está familiarizado con la aritmética modular, pero podría agregar una introducción sobre este tema en el futuro. Si a y n son números enteros, diremos que el resto r cuando a se divide por n es el residuo de a mod n (residuo es una palabra antigua para lo que hoy en día se llama resto, pero esa palabra es la que se usa en teoría de números). Claramente, a = r (mod p) y r es el menor número no negativo con esta propiedad. Estrechamente relacionado con este concepto es el residuo menor absoluto definido como el menor de r y r-n en valor absoluto. Si n es par y r=n/2, entonces |r|=|r-n| y se puede tomar caulquiera de los dos valores, pero para que no haya ambigüedades en la frase, tomaremos r.

Así que queremos mostrar que cada primo impar es la suma de cuatro cuadrados. A continuación daremos dos demostraciones separadas, la primera es que cada primo congruente a 1 mod 4 es la suma de dos cuadrados y la segunda es que cada primo congruente a 3 mod 4 es la suma de cuatro cuadrados.

Primos congruentes a 1 mod 4

Comenzaremos mostrando que si p es un primo y p = 1 (mod 4), entonces existe un número a tal que a2 = -1 (mod p). Diremos que -1 es un residuo cuadrático mod p. Una forma de ver esto es lo siguiente.

Si a, b, y c son tres enteros y p no divide a a, entonces ab = ac (mod p) implica que b = c (mod p). La razón es que las condiciones implican que p divide a ab-ac y p no divide a a así que p divide a b-c, que es la conclusión. Ahora para cada a tal que 0 < a < p los números a, 2a, 3a, ..., (p-1)a son todos no congruentes entre sí mod p y por lo tanto deberán ser congruentes a 1, 2, 3, ..., p-1 en algún orden. Tomando el producto de todos los enteros en ambos conjuntos, vemos que ap-1(p-1)! = (p-1)! (mod p). Como p no divide ningún factor de (p-1)!, se puede cancelar para concluir que ap-1 = 1 (mod p) (pequeño teorema de Fermat).

Luego si a no es divisible por p, si hacemos b=a(p-1)/2, entonces b2 = 1 (mod p). Esto significa que p divide a (b2-1) = (b-1)(b+1) lo que significa que a(p-1)/2 = b = ±1 (mod p).

¿Puede ser a(p-1)/2=1 para todo a? No, no puede. No daré todos los detalles aquí, pero la razón es que la aritmética modulo un número primo es como la aritmética ordinaria en casi todos sus aspectos. En particular, el argumento usual que dice que un polinomio de grado d tiene como máximo d raíces distintas es válido. Si f(x) es un polinomio, f(a) = 0 (mod p) si y sólo si x-a divide a f(x), con la división haciéndose mod p. Esto no es cierto para números compuestos. Por ejemplo, x2-1 = (x-1)(x+1) tiene cuatro raíces mod 8 porque 2 puede dividir uno de los factores y 4 puede dividir el otro. Volviendo al argumento principal, el polinomio x(p-1)/2-1 puede tener como máximo (p-1)/2 raíces al igual que el otro factor de xp-1-1 = (x(p-1)/2-1) (x(p-1)/2+1). Como el polinomio tiene p-1 raíces (1, 2, ..., p-1), se concluye que exactamente (p-1)/2 de los factores deben satisfacer la ecuación x(p-1)/2 = -1 (mod p). Hasta ahora, este argumento es válido para todos los primos impares. El siguiente paso está limitado a los primos p, para los cuales 4 divide a p-1.

Si a(p-1)/2 = -1 (mod p) y hacemos b=a(p-1)/4, entonces b2 = -1 (mod p), como queremos.

Así que el primer paso del proceso consiste en hallar una raíz cuadrada de -1 mod p. De hecho, hemos mostrado que exactamente la mitad de los números 1, ..., p-1 tienen la propiedad deseada. No conozco un proceso determinístico para encontrar uno de estos números, pero parecen estar distribuidos aleatoriamente así que es sólo cuestión de probar números al azar hasta encontrar alguno. Cada prueba tiene 50% de probabilidad de éxito. No es difícil mostrar que la solución mínima debe ser un número primo así que se pueden ir probando los diferentes primos 2, 3, 5, 7, 11, ... hasta tener éxito. Aún si se desea descomponer un primo de 1000 dígitos es muy extraño que no se encuentre la solución antes del 2000° primo, así que para propósitos de programación, probablemente valga la pena tener una lista de los primeros 2000 primos.

Actualmente, es mucho más fácil si una potencia grande de 2 divide a p-1. Si 2k divide a p-1 y hacemos m=(p-1)/2k, entonces tan pronto como am!= 1 (mod p), alguno de los siguientes números a, a2, a4 será una raíz cuadrada de -1 mod p. La probabilidad de que un número elegido al azar satisfaga am = 1 (mod p) es sólo 1 en 2k-1.

Ahora a2+12 es un múltiplo de p, digamos a2+12=kp. Como a <= p-1, vemos que a2+1 < p2 así que k < p. Ahora describiremos un procedimiento que continúa produciendo soluciones de a2+b2=kp, pero con valores menores de k hasta que k=1 que es lo que necesitamos. Asumiendo que tenemos un par a y b, sean a' y b' los residuos menores absolutos a mod k y b mod k, respectivamente. Esto significa que a' y b' son enteros en el rango (-k/2,k/2]. De ello sigue que a'2+b'2 <= (k/2)2+(k/2)2 = k2/2. Además, a'2+b'2 = a2+b2 = 0 (mod k) porque a = a' (mod k) y b = b' (mod k).

Así a'2+b'2=mk con m < k. Multiplicando, encontramos que (a2+b2)(a'2+b'2) = mk2p. Ahora tenemos la identidad,

(a2+b2)(a'2+b'2) = (aa'+bb')2+(ab'-ba')2   (*)

Como aa'+bb' = a2+b2 = 0 (mod k) y ab'-ba' = ab-ba = 0 (mod k) sigue que ambos términos del miembro derecho de (*) son divisibles por k y así

((aa'+bb')/k)2 + ((ab'-ba')/k)2 = mp

y m < k. Se puede mostrar que la cantidad de pasos de reducción está acotado por log2 p.

Primos congruentes a 3 mod 4

En este caso, comenzaremos buscando números a y b tales que a2+b2+1 = 0 (mod p). Esto es lo mismo que b2=-1-a2 (mod p). Así que podemos probar en la secuencia -1-4, -1-9, ..., hasta que alguno de ellos tenga una raíz cuadrada mod p. No sé si existe un teorema al respecto, pero empíricamente parece que por cada valor de a existe una probabilidad del 50% que -1-a2 sea un residuo cuadrático. No es difícil probar que existe como mínimo una solución a y2=-1-x2 (mod p). Para verlo, primero observe que los cuadrados 02, 12, ..., ((p-1)/2)2 tienen todos distintos residuos mod p ya que a2 = b2 (mod p) implica que p divide a (a2-b2)=(a+b)(a-b) y de aquí que a = b (mod p) o a = -b (mod p), lo que es imposible para dos números distintos en el rango [0,(p-1)/2]. Así aquellos cuadrados tienen (p+1)/2 residuos distintos. Por razones similares, los números -1-02, -1-12, ..., -1-((p-1)/2)2 tienen (p+1)/2 residuos distintos. Como hay p a lo sumo, los dos conjutos de residuos se solpan y hay como mínimo una solución a x2+y2+1 = 0 (mod p). Esto prueba que hay como mínimo una solución, pero si hubiera una sola, encontrarla sería como buscar una aguja muy pequeña en un pajar muy grande (asumiendo que p es muy grande). De hecho, los experimentos me convencen que -1-x2 es congruente a un cuadrado cerca de la mitad de las veces y hay muchas soluciones. De hecho, se puede mostrar que -2=-1-12 es un residuo cuadrático siempre que p = 3 (mod 8), lo que cubre la mitad de los casos de los primos que son congruentes a 3 mod 4. Criterios similares existen para -5=-1-22, -10=-1-32, etc. Así que parecería que simplemente habría que ir probando -2, -5, -10, ... hasta encontrar uno que funcione. (Incidentalmente, -1 nunca puede ser un residuo cuadrático para estos primos, cuya demostración es un ejercicio muy sencillo.)

Para nuestros propósitos, sin embargo, no es suficiente encontrarx, también hace falta y. Afortunadamente, para los primos que son congruentes a 3 mod 4, existe una manera muy sencilla de construir una raíz cuadrada de cualquier número que sea un residuo cuadrático. De lo que yo sé, no hay una manera tan sencilla para hacer lo mismo para los primos congruentes a 1 mod 4. Consideremos un número a, no divisible por p. Suponiendo que a = b2 (mod p). Luego

a(p+1)/2 = bp+1 = b2bp-1 = b2 = a (mod p)

de lo que podemos ver que (a(p+1)/4)2 = a (mod p) y entonces a(p+1)/4 es una raíz cuadrada de a mod p si tiene uno. (Si no lo tiene, es una raíz cuadrada de -a.)

Una vez que tenemos x y y tales que x2+y2+1 = 0 (mod p), podremos reemplazarlos por residuos menores absolutos y suponiendo que |x| < (p-1)/2 y |y| < (p-1)/2 de lo que se puede ver que x2+y2+1 < p2/2. Así obtenemos valores iniciales de a,b,c,d para los cuales a2+b2+c2+d2 = kp con k < p.

Ahora mostraremos como, si k > 1, encontrar una nueva solución con un valor menor de k. El argumento es similar, pero más complicado, que en el caso anterior de la suma de dos cuadrados. Consideraremos el caso de k impar y par separadamente.

Supongamos que k es impar. En ese caso, sean a', b',c', y d' los residuos absolutos menores de a, b, c, y d mod k. Entonces cada uno de |a'|, |b'|, |c'| y |d'| es <= (k-1)/2 así que

a'2+b'2+c'2+d'2 <= (k-1)2

mientras que

a'2+b'2+c'2+d'2 = a2+b2+c2+d2 = 0 (mod k)

Hence a'2+b'2+c'2+d'2 = mk con m < k. Ahora tenemos que

mk2p = (a2+b2+c2+d2) (a'2+b'2+c'2+d'2) = (aa'+bb'+cc'+dd')2 + (ab'-ba'+dc'-cd')2 + (ac'-ca'+bd'-db')2 + (ad'-a'd+cb'-bc')2 y, de una manera similar al primer caso, cada término es divisible por k, de lo que concluimos que

mp = ((aa'+bb'+cc'+dd')/k)2 + ((ab'-ba'+dc'-cd')/k))2 + ((ac'-ca'+bd'-db')/k)2 + ((ad'-a'd+cb'-bc')/k)2

lo que completa la construcción.

Cuando k es par, el argumento anterior falla específicamente en el caso a'=b'=c'=d'=k/2 ya que entonces a'2+b'2+c'2+d'2 = k2. Aunque podríamos daruna prueba que funcione para este caso específico, es casi tan sencillo y computacionalmente mejor dar un argumento que divida por dos el valor de k cuando es par. Observemos que a2+b2+c2+d2 = kp es par así que ninguno o dos o los cuatro valores de a, b, c y d son pares. En cualquier caso podemos intercambiar los valores de forma que a±b y c±d sean pares y entonces

((a+b)/2)2 + ((a-b)/2)2 + ((c+d)/2)2 + ((c-d)/2)2 = (k/2)p

lo que completa la prueba.

Reproducido aquí con el permiso del autor. Traducido por Darío Alejandro Alpern.

Apriete aquí para abrir un applet que encuentra la descomposición de números enteros positivos como suma de hasta cuatro cuadrados perfectos usando este método.


Cálculo de la suma de cuadrados si se desconoce la factorización

por Dario Alejandro Alpern

Los métodos que se muestran arriba sirven solamente si se conoce la factorizacion del número en números primos. Si éste no es el caso se necesita una modificación.

Como es mucho más fácil verificar si un número es primo que factorizarlo, podemos utilizar el siguiente método:

Si el número no tiene la forma 4r (8k+7) se puede expresar como una suma de tres cuadrados perfectos. En este caso se deberá sustraer un cuadrado perfecto al número original tal que la diferencia sea un primo de la forma 4k+1. Entonces, utilizando el método explicado arriba encontraremos la descomposición del número primo en una suma de dos cuadrados perfectos. Si el número no se puede expresar como una suma de tres cuadrados se deberán restar dos cuadrados perfectos.

Desafortunadamente este método simple no funciona: cuando el número es múltiplo de 4, no se puede hallar una diferencia de la forma 4k+1 sustrayendo uno o dos cuadrados. Además, cuando el número tiene la forma 8k+3 se puede expresar como una suma de tres cuadrados, pero sustrayendo un cuadrado no se puede obtener una diferencia de la forma 4k+1. No es difícil cambiar la idea para que funcione.

El método se puede expresar como sigue:

Para acelerar el algoritmo, en vez de buscar primos, podemos buscar "casi primos". En este contexto los casi primos son números que se pueden expresar como un producto de primos de la forma 4k+1 y cuadrados de primos de la forma 4k+3 hasta alguna cota, y un primo grande. Los casi primos se pueden expresar fácilmente como una suma de dos cuadrados perfectos.

No es necesario utilizar un método para hallar primos certificados. Esto es así porque sólo hace falta hallar un número q tal que q2 = -1 (mod (4k+1)). Este número q se utiliza en el algoritmo que calcula la suma de dos cuadrados.

Una desventaja de este método es que un número que es un producto de primos grandes de la forma 4k+1 se descompondrán en una suma de tres cuadrados cuando dos bastarían.

Apriete aquí para abrir un applet que encuentra la descomposición de números enteros positivos como suma de hasta cuatro cuadrados perfectos usando este método.

Última actualización: 19 de febrero de 2003.