Todo entero positivo es una suma de cuatro cuadrados perfectos

  1. Alpertron
  2. Teoría de números
  3. 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

(a² + b² + c² + d²) ⁢(A² + B² + C² + D²) = (a⁢A+b⁢B+c⁢C+d⁢D)² + (a⁢B−b⁢A+c⁢D−d⁢C)² + (a⁢C−b⁢D−c⁢A+d⁢B)² + (a⁢D−d⁢A+b⁢C−c⁢B)²

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−b⁢i−c⁢j−d⁢k y U=A+B⁢i+C⁢j+D⁢k, la identidad mencionada es simplemente el cuadrado de la identidad que dice que |u⁢U|=|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:

(a² + b²) ⁢(A² + B²) = (a⁢A+b⁢B)² + (a⁢B−b⁢A)²

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 cualquiera 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 a² = −1 (mod p). Diremos que −1 es un residuo cuadrático módulo p. Una forma de ver esto es lo siguiente.

Si a, b, y c son tres enteros y p no divide a a, entonces a⁢b = a⁢c (mod p) implica que b = c (mod p). La razón es que las condiciones implican que p divide a a⁢b−a⁢c 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, 2⁢a, 3⁢a, ..., (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 b² = 1 (mod p). Esto significa que p divide a (b²−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 cualquier valor de 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, x²−1 = (x−1)⁢(x+1) tiene cuatro raíces módulo 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 b² = −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, a², a⁴ 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 a²+1² es un múltiplo de p, digamos a²+1²=k⁢p. Como a <= p−1, vemos que a²+1 < p² así que k < p. Ahora describiremos un procedimiento que continúa produciendo soluciones de a²+b²=k⁢p, pero con valores decrecientes 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'²+b'² <= (k/2)²+(k/2)² = k²/2. Además, a'²+b'² = a²+b² = 0 (mod k) porque a = a' (mod k) y b = b' (mod k).

Así a'²+b'² = m⁢k con m < k. Multiplicando, encontramos que (a²+b²)⁢(a'²+b'²) = m⁢k²⁢p. Ahora tenemos la identidad,

(a²+b²)(a'²+b'²) = (a⁢a'+b⁢b')²+(a⁢b'−b⁢a')²   (*)

Como a⁢a'+b⁢b' = a²+b² = 0 (mod k) y a⁢b'−b⁢a' = a⁢b−b⁢a = 0 (mod k) sigue que ambos términos del miembro derecho de (*) son divisibles por k y así

((a⁢a'+b⁢b')/k)² + ((a⁢b'−b⁢a')/k)² = m⁢p

y m < k. Se puede mostrar que la cantidad de pasos de reducción está acotado por el logaritmo en base 2 de p.

Primos congruentes a 3 mod 4

En este caso, comenzaremos buscando números a y b tales que a²+b²+1 = 0 (mod p). Esto es lo mismo que b² = −1−a² (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−a² sea un residuo cuadrático. No es difícil probar que existe como mínimo una solución a y² = −1−x² (mod p). Para verlo, primero observe que los cuadrados 0², 1², ..., ((p−1)/2)² tienen todos distintos residuos mod p ya que a² = b² (mod p) implica que p divide a (a²−b²) = (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−0², −1−1², ..., −1−((p−1)/2)² tienen (p+1)/2 residuos distintos. Como hay p a lo sumo, los dos conjuntos de residuos se solapan y hay como mínimo una solución a x²+y²+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−x² es congruente a un cuadrado cerca de la mitad de las veces y hay muchas soluciones. De hecho, se puede mostrar que −2=−1−1² 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−2², −10=−1−3², 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 encontrar x, 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 = b² (mod p). Luego

a(p+1)/2 = bp+1 = b²⁢bp−1 = b² = a (mod p)

de lo que podemos ver que (a(p+1)/4)² = 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 x²+y²+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 x²+y²+1 < p²/2. Así obtenemos valores iniciales de a, b, c, d para los cuales a²+b²+c²+d² = k⁢p 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'²+b'²+c'²+d'² <= (k−1)²

mientras que

a'²+b'²+c'²+d'² = a²+b²+c²+d² = 0 (mod k)

Por lo tanto a'²+b'²+c'²+d'² = m⁢k con m < k. Ahora tenemos que

m⁢k²⁢p = (a²+b²+c²+d²) ⁢(a'²+b'²+c'²+d'²) = (a⁢a'+b⁢b'+c⁢c'+d⁢d')² + (a⁢b'−b⁢a'+d⁢c'−c⁢d')² + (a⁢c'−c⁢a'+b⁢d'−d⁢b')² + (a⁢d'−a'⁢d+c⁢b'−b⁢c')² y, de una manera similar al primer caso, cada término es divisible por k, de lo que concluimos que

m⁢p = ((a⁢a'+b⁢b'+c⁢c'+d⁢d')/k)² + ((a⁢b'−b⁢a'+d⁢c'−c⁢d')/k))² + ((a⁢c'−c⁢a'+b⁢d'−d⁢b')/k)² + ((a⁢d'−a'⁢d+c⁢b'−b⁢c')/k)²

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'²+b'²+c'²+d'² = k². Aunque podríamos dar una 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 a²+b²+c²+d² = k⁢p 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)² + ((a−b)/2)² + ((c+d)/2)² + ((c−d)/2)² = (k/2)⁢p

lo que completa la prueba.

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

Este sitio Web incluye una aplicación de factorización de números enteros que también 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 Darío Alejandro Alpern

Los métodos que se muestran arriba sirven solamente si se conoce la factorización 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 (8⁢k+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 4⁢k+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 4⁢k+1 sustrayendo uno o dos cuadrados. Además, cuando el número tiene la forma 8⁢k+3 se puede expresar como una suma de tres cuadrados, pero sustrayendo un cuadrado no se puede obtener una diferencia de la forma 4⁢k+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 4⁢k+1 y cuadrados de primos de la forma 4⁢k+3 hasta alguna cota, y un primo grande de la forma 4⁢k+1. 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 q² = −1 (mod (4⁢k+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 4⁢k+1 se descompondrán en una suma de tres cuadrados cuando dos bastarían.

Puede ejecutar la aplicación que descompone un número natural en suma de hasta cuatro cuadrados perfectos usando este método.

Última actualización: 4 de agosto de 2022.