Sommes de carrés

On se reportera aux travaux de Fermat, Euler, Gauss etc pour des détails et démonstrations.
Notons les résultats suivants :

Tout nombre est somme d'au plus 4 carrés non nuls (théorème de Lagrange)
Tout nombre qui n'est pas de la forme 4ⁿ(8k+7) est somme d'au plus 3 carrés non nuls
Les seuls nombres qui sont somme de deux carrés sont (théorème de Fermat-Girard) :
- le nombre 2 = 1² + 1²
- Les nombres premiers de la forme 4k + 1
- Les carrés des nombres premiers de la forme 4k + 3
- et les produits de tels nombres
D'ailleurs si deux nombres sont sommes de deux carrés, leur produit aussi, de deux façons :
(a² + b²)(c² + d²) = (ac + bd)² + (ad - bc)² = (ac - bd)² + (ad + bc)²
Par contre un produit de deux sommes de 3 carrés n'est pas forcément somme de 3 carrés :
26 = 4² + 3² + 1² et 38 = 5² + 3² + 2² alors que 26×36 = 988 = 4×(8×30 + 7) est de la forme (2) et ne peut pas être somme de 3 carrés.
Notons aussi l'identité d'Euler pour les sommes de 4 carrés :
(a² + b² + c² + d²)(x² + y² + z² + t²) = (ax + by + cz + dt)² + (ay - bx + ct - dz)² + (az - cx + dy - bt)² + (at - dx + bz - cy)²
ainsi que les formules obtenues en changeant b en -b etc...
Soit N = 2^t∏p^m∏q²ⁿ la décomposition en facteurs premiers de N, où l'on a dissocié le facteur 2, les facteurs premiers p de la forme 4k + 1 et les facteurs premiers q de la forme 4k + 3.
N est la somme de deux carrés si et seulement si les exposants des facteurs premiers 4k+3 sont pairs
Alors le nombre de représentations de N comme somme de 2 carrés est r(N) = 4×∏(m + 1) et ne dépend que des exposants des facteurs premier 4k + 1.
Les représentations (±x, ±y) et (±y, ±x) comptent pour 8 représentations différentes, sauf cas x = 0, y = 0 ou x = y.
Le nombre de décompositions normalisées de N = x² + y², x ≥ y ≥ 0 est :
d(N) = [(1 + ∏(m + 1))/2]

Exemple :
Le nombre de représentations de 1521000 = 8×3²×5³×13² est 4×(3 + 1)(2 + 1) = 48 (seuls 5 et 13 sont de la forme 4k + 1, d'exposants 3 et 2). Le nombre de décompositions est [(1 + (3 + 1)(2 + 1))/2] = 6.
Pour obtenir la décomposition en somme de 2 carrés d'un nombre premier 4k + 1, on peut opérer ainsi :
- Par essai de x = 0, 1, 2... jusqu'à trouver un carré p - x². Evident, simple, mais pas très rapide.
- Ou en itérant les formules :
  y = [_ √(p - x²) _] et x = [¯ √(p - y²) ¯] à partir de x = 0 jusqu'à un reste nul ou x > y.
  Avec [_ z _] plus grand entier n ≤ z et [¯ z ¯] le plus petit entier n ≥ z.
  Par exemple p = 269 x = 0, y = 16, x = 4, y = 15, x = 7, y = 14, x = 9, y = 13, x = 10 et c'est fini : 269 = 10² + 13²
- Ou encore avec l'algorithme de Legendre :
  A₀ = 1, B₀ = 0, C₀ = -p, N = [√p]
  Répéter jusqu'à A_n + C_n = 0 (l'arrêt n'est garanti que si p = 4k + 1 premier) :
  m_i = [(|B_i| + N)/|A_i|], A_i+1 = A_im_i² + 2B_im_i + C_i, B_i+1 = A_im_i + B_i, C_i+1 = A_i
  Alors p = |A_n|² + |B_n|².
  Par exemple p = 269 : N = 16, A₀ = 1, B₀ = 0, C₀ = -269
  m₀ = 16, A₁ = -13, B₁ = 16, C₁ = 1
  m₁ = 2, A₂ = 13, B₂ = -10, C₂ = -13 c'est fini : 269 = 13² + 10²
- Enfin la méthode de Heath-Brown :
  Pour p = 4k + 1 posons x = k, y = 1, z = 1 puis répéter les transformations
  si x > y + z : x = x - y - z, y = y, z = 2y + z
  si x < y + z : x = y + z - x, y = x, z = 2x - z
  (invariant 4xy + z² = p, x - y + z > 0)
  jusqu'à x = y. Alors p = 4x² + z²
  Par exemple avec p = 29 = 4*7 + 1 x = 7, y = 1, z = 1, y + z = 2
  x = 5, y = 1, z = 3, y + z = 4
  x = 1, y = 1, z = 5 c'est fini 29 = 4 + 25 = 2² + 5²
Pour obtenir toutes les décompositions en sommes de 2 carrés de N = 2^t∏p^m∏q²ⁿ avec p = u² + v² les nombres premiers de la forme 4k + 1 et q les nombres premiers de la forme 4k + 3, on pose le nombre complexe :
A + iB = e(1 + i)^t ∏(u + iv)^r(u - iv)^m-r ∏qⁿ avec e = {± i, ± 1}, et pour chaque facteur 0 ≤ r ≤ m
Alors N = A² + B² est une représentation de N en somme de 2 carrés. On les obtient toutes en faisant varier e et chaque r. On n'obtient que les décompositions (non équivalentes) en fixant e et des contraintes sur les r.
Exemple : N = 1521000 = 8×3²×5³×13², A + iB = e(1 + i)³(2 + i)^r(2-i)^3-r(3 + 2i)^s(3 - 2i)^2-s×3
On peut fixer e = -i de sorte que e(1 + i)³ = 2(1 + i), et les contraintes r = {0,1,2,3} et s = {0,1,2}.
Mais si on choisit indépendament r et s, on constate que r = 0, s = 0 et r = 3, s = 2 donnent des représentations équivalentes -258-1206i et -1206-258i car les nombres (2 - i)³(3 - 2i)² et (2 + i)³(3 + 2i)² sont conjugués.
Pour n'obtenir que les 6 décompositions il faut se limiter à r = {0, 1} s = {0, 1, 2}.
r = 0, s = 0 : 6(1 + i)(2 - i)³(3 - 2i)² = -258-1206i soit N = 1206² + 258²
r = 0, s = 1 : 6(1 + i)(2 - i)³(3 + 2i)(3-2i) = 1014-702i soit N = 1014² + 702²
r = 0, s = 2 : 6(1 + i)(2 - i)³(3 + 2i)² = 1038+666i soit N = 1038² + 666²
r = 1, s = 0 : 6(1 + i)(2 + i)(2 - i)²(3 - 2i)² = 810-930i soit N = 930² + 810²
r = 1, s = 1 : 6(1 + i)(2 + i)(2 - i)²(3 + 2i)(3-2i) = 1170+390i soit N = 1170² + 390²
r = 1, s = 2 : 6(1 + i)(2 + i)(2 - i)²(3 + 2i)² = 90+1230i soit N = 1230² + 90²
De façon générale, il faut limiter un des r à la moitié de ses valeurs. Choisir un p d'exposant impair pour cela. Si tous les p sont d'exposant pair (N est un carré ou le double d'un carré), r sera limité à la moitié de ses valeurs, plus une, de façon récursive sur tous les exposants.
Par exemple N = 5⁴×13⁴×17⁴ A + iB = (2 + i)^r(2-i)^{4 -r}(3+2i)^s(3-2i)^{4 -s}(4+ i)^t(4-i)^{4 -t}
r = {0, 1}, s = {0, 1, 2, 3, 4}, t = {0, 1, 2, 3, 4} : limitation sur r, 50 décompositions
r = 2, s = {0, 1}, t = {0, 1, 2, 3, 4} : r fixé, limitation sur s, 10 décompositions
r = 2, s = 2, t = {0, 1} : r et s fixés, limitation sur t, 2 décompositions
r = 2 s = 2 t = 2 : r, s, t fixés, 1 décomposition
Ce qui donne bien les 63 décompositions de N
Un Javascript pour donner toutes les décompositions de N avec cette méthode.

Applications :

Quel est le plus petit nombre se décomposant en somme de deux carrés de 10 façons différentes ?
Le plus petit nombre se composera exclusivement de facteurs premiers p = 4k + 1 les plus petits possible N = 5^ax13^bx17^cx29^d... avec a ≥ b ≥ c ≥ d... Les exposants sont tels que P = (a + 1)(b + 1)(c + 1)...= 19 ou 20.
- P = 19 = 1×19 donne N = 5¹⁸
- P = 20 = 1×20 = 2×10 = 4×5 = 2×2×5 donnent : 5¹⁹, 5⁹×13, 5⁴×13³, 5⁴×13×17.
Le plus petit est 5⁴×13×17 = 138125.
Plus petite hypothénuse commune à 10 triangles rectangles différents à cotés entiers.
Le carré de l'hypothénuse L² se décompose en somme de deux carrés de 10 façons différentes. La formule classique prend en compte L² + 0². Si on élimine cette "décomposition", il en faut 11 et P = 21 ou 22.
L² étant un carré (mais si !), P est impair.
P = 21 = 1×21 = 3×7 L² = 5²⁰ et L² = 5⁶×13².
L² = 5⁶× 13² est le plus petit et donne l'hypothénuse L = 5³×13 = 1625.
Nota : la plus petite hypothénuse commune à au moins 10 triangles rectangles n'est pas forcément celle-là ! Pour la trouver, examinons les produits de nombres impairs qui soient supérieurs ou égaux à 21. 3×7 = 21 est celui trouvé ci dessus mais 3×3×3 = 27 conduisant à L² = 5²×13²×17² donne une hypothénuse = 5×13×17 = 1105 plus petite, commune à 13 triangles rectangles propres, 14 avec L² + 0².
Cercle passant par le plus possible de points entiers.
Là R² = 5^a×13^b×17^c... minimum avec a ≥ b ≥ c... et d(R²) maximum, mais R n'est pas forcément un entier.
Sur du papier quadrillé A4 = 210×297 : 2R ≤ 210 = 42 carreaux soit R² ≤ 441.
R² = 5²×13 = 325 : 24 représentations (1,18) (6,17) (10,15) et leurs symétriques.
R² = 5³ = 125 : 16 représentations seulement (2,11) (5,10) et leurs symétriques.
Si R est entier, alors R est lui même 5^a×13^b..., et pas seulement R².
R ≤ 21 donne R = 5, R² = 25 et 12 représentations seulement (0,5) (3,4) et leurs symétriques.
Avec du papier millimètré, 2R ≤ 210mm et R² ≤ 11025. Les seuls candidats sont :
R² = 5⁵ = 3125, 24 représentations
R² = 5⁴×13 = 8125, 40 représentations
R² = 5²×13² = 4225, 36 représentations
R² = 5²×13×17 = 5525, 48 représentations (7,74) (14,73) (22,71) (25,70) (41,62) (50,55) et leurs symétriques
le maximum est cette dernière valeur.