Der Satz von Lagrange

Leider hat der berühmte Satz von Joseph-Louis Lagrange (1736-1813), dass jede natürliche Zahl sich als Summe von höchstens vier Quadratzahlen darstellen lässt (siehe Wikipedia), bislang noch nicht seinen Platz im Buch der Beweise [Aigner, Ziegler 2014] gefunden. Weil es sich dabei um eins meiner Lieblings-Theoreme handelt, soll diesem Mangel hier abgeholfen werden. Dabei sollen nur Methoden benutzt werden, die einem Oberstufenschüler geläufig sind, nämlich Teilbarkeitsüberlegungen und einige Rechnungen mit Restklassen. Ferner wird Wert darauf gelegt, dass keine Lücken bleiben, dass also auch Zwischenschritte bewiesen werden, die man üblicherweise mit der Floskel wie man leicht sieht übergehen würde.

Theorem von Lagrange
Jede natürliche Zahl ist als Summe von höchstens vier Quadratzahlen darstellbar. D.h. zu jedem $n \in \mathbb{N}$ gibt es $x, y, z, w \in \mathbb{N}_0$ mit \[n = x^2 + y^2 +z^2 + w^2\].

Beispiele sind etwa $17 = 4^2 + 1^2$ oder $7 = 2^2 +1^2 + 1^2 + 1^2.$ Das letzte Beispiel zeigt, dass man wirklich vier Quadratzahlen braucht.

Zu den Teilbarkeitsüberlegungen, die im Laufe des Beweises benötigt werden, gehört das Lemma von Euklid: Wenn eine Primzahl $p$ ein Produkt teilt, symbolisch $p \mid ab,$ teilt $p$ mindestens einen der Faktoren, $p \mid a$ oder $p \mid b.$ Wer meint, dass dies wegen der Eindeutigkeit der Primfaktorzerlegung trivial ist, möge sich daran erinnern, dass man zum Beweis der Eindeutigkeit der Primfaktorzerlegung eben dieses Lemma von Euklid benutzt.

Wir beweisen das Lemma von Euklid mit Hilfe des Lemma von Bézout  und beginnen daher mit diesem:

Lemma von Bézout
Seien $a$ und $b$ aus $\mathbb{Z}$ und sei $d$ der größte gemeinsame Teiler von $a$ und $b.$ Dann gibt es $s$ und $t$ aus $\mathbb{Z}$ mit \[d = sa + tb\].

Beweis:
Unter allen Zahlen der Form $sa + tb$ mit $s, t \in \mathbb{Z}$ gibt es sicher solche, die echt größer als 0 sind. Sei $x$ die kleinste von ihnen. Da $d$ ein Teiler von $a$ und von $b$ ist, muss $d$ auch ein Teiler von $x$ sein. Wenn $x = 1$ ist, muss $d = 1$ sein und wir sind fertig. Für $x \gt 1$ liefert die Division mit Rest: $a = qx +r$ mit $0 \leq r \lt x.$ Setzt man für $x$ den Wert $sa + tb$ ein, erhält man: $$ \begin{align*} a &= q(sa + tb) + r \\ r &= (1-qs)a + (-qt)b \\ \end{align*} $$ $r$ ist also ebenfalls von der Form $s'a + t'b$ und gleichzeitig kleiner als $x.$ Da $x$ minimal gewählt war, muss $r = 0$ sein. Folglich ist $x$ ein Teiler von $a,$ d.h. $x \mid a.$ Ganz analog zeigt man, dass $x \mid b.$ Daher gilt auch $x \mid d.$ Da wir bereits $d \mid x$ hatten, muss $x = d$ gelten. ∎

Lemma von Euklid
Sei $p$ eine Primzahl und $p \mid ab$ mit $a, b \in \mathbb{Z}$ dann gilt $p \mid a$ oder $p\mid b.$

Beweis:
Es genügt zu zeigen: Wenn $p \mid ab$ und $p \nmid a,$ dann folgt $p \mid b.$ Aus $p \nmid a$ folgt, dass $p$ und $a$ teilerfremd sein müssen, dass also der ggT von $a$ und $p$ gleich 1 ist. Nach dem Lemma von Bézout gilt daher: \[1 = sa + tp\] mit $s, t \in \mathbb{Z}.$ Multiplikation mit $b$ liefert: \[b = s(ab) + tbp\] Da jeder Summand in dieser Darstellung durch $p$ teilbar ist, gilt dies auch für die Summe $b,$ daher gilt $p \mid b.$  ∎

Der folgende Produktsatz von Euler erlaubt es, sich beim Beweis des Theorems von Lagrange auf Primzahlen zu beschränken. Es wird nämlich gezeigt, dass das Produkt zweier Summen von vier Quadraten sich wieder als Summe von vier Quadraten darstellen lässt. Da jede natürliche Zahl Produkt von Primfaktoren ist, folgt das allgemeine Theorem von Lagrange aus dem für Primzahlen durch Ausmultiplizieren und Zusammenfassen gemäß dem Eulerschen Produktsatz sowie der trivialen Darstellung $1 = 1^2 + 0^2 +0^2 +0^2$ für die Nicht-Primzahl 1.

Eulerscher Produktsatz
Wenn zwei natürliche Zahlen als Summe von vier Quadraten darstellbar sind, dann auch deren Produkt.

Beweis:
Durch explizites Nachrechnen der folgenden Formel: $$ \begin{multline*} (x^2 + y^2 + z^2 + w^2)(x_1^2 + y_1^2 + z_1^2 + w_1^2) \\ = (xx_1 + yy_1 + zz_1 + ww_1)^2 + (xy_1 -yx_1 + wz_1 - zw_1)^2 \\ +(xz_1 - zx_1 + yw_1 - wy_1)^2 + (xw_1 - wx_1 + zy_1 - yz_1)^2  ∎ \end{multline*} $$

Da für $2 = 1^2 + 1^2 + 0^2 + 0^2$ eine Darstellung als Summe von vier Quadraten explizit angegeben werden kann, reicht es sogar, das Theorem von Lagrange nur für ungerade Primzahlen $p,$ d.h. Primzahlen $p \gt 2$ zu beweisen.

Dieser Beweis erfolgt nach der Methode des unendlichen Abstiegs, die von Fermat eingeführt und für viele zahlentheoretische Beweise angewandt worden ist. Wir beweisen dazu zunächst, dass man jedes Produkt $mp$ mit einer ungeraden Primzahl $p$ und einem Faktor $m$ mit $1 \leq m \lt p$ als Summe von vier Quadraten darstellen kann. Der Abstieg  besteht darin, dass man aus der Darstellung \[x^2 +y^2 + z^2 + w^2 = mp\] für $m \gt 1$ eine Darstellung \[x'^2 +y'^2 + z'^2 + w'^2 = m'p\] konstruiert, wobei $m' \lt m$ gilt. Da man diese Konstruktion so oft wiederholen kann, bis $m' = 1$ gilt, hat man damit das Theorem von Lagrange für ungerade Primzahlen bewiesen.

Um den Einstieg für unseren Abstieg zu finden brauchen wir noch folgendes

Lemma
Für jede ungerade Primzahl $p$ und alle $x$ mit $0 \leq x \leq (p-1)/2$ liegen die Quadrate $x^2$ in unterschiedlichen Restklassen mod $p.$

Beweis:
Angenommen man hätte $x \neq y$ mit $0 \leq x \lt y \leq (p-1)/2,$ deren Quadrate bei Teilung durch $p$ den gleichen Rest haben. Dann teilt $p$ die Differenz der Quadrate und man hat: $$ \begin{align*} p {}& \mid y^2 - x^2 \\ p {}& \mid (y+x)(y-x) \end{align*} $$ Aus dem Lemma von Euklid folgt, dass $p \mid (y+x)$ oder $p \mid (y-x).$ Angenommen $p \mid (y-x),$ dann liegen $x$ und $y$ in der gleichen Restklasse mod $p.$ Da beide Werte außerdem zwischen $0$ und $(p-1)/2$ liegen, wäre dann $y = x,$ was der Voraussetzung widerspricht. Nun ist aber $0 \lt y+x \leq p -1 \lt p,$ d.h. es gilt $p \nmid (y + x).$ Damit führt die Annahme, dass $x^2$ und $y^2$ den gleichen Rest mod $p$ haben, zum Widerspruch. ∎

Nun können wir den Ausgangspunkt für den Abstieg konstruieren und benutzen dazu das folgende

Lemma (Euler)
Für jede ungerade Primzahl $p$ existieren $x, y \in \mathbb{Z},$ mit $0 \leq x,y \leq (p-1)/2$ so dass gilt: \[ x^2 + y^2 + 1^2 \equiv 0 \pmod{p} \]

Beweis:
Wir haben oben gesehen, dass die $(p+1)/2$ Quadrate $x^2$ mit $0 \leq x \leq (p-1)/2$ sämtlich in verschiedenen Restklassen mod $p$ liegen. Daraus folgt unmittelbar, dass auch die $(p+1)/2$ Ausdrücke $-1-y^2$ mit $0 \leq y \leq (p-1)/2$ sämtlich in verschiedenen Restklassen mod $p$ liegen. Wenn nun keine der Restklassen, in denen $x^2$ liegt, mit einer der Restklassen, in denen $-1-y^2$ liegt übereinstimmte, hätte man insgesamt $p+1$ verschiedene Restklassen mod $p.$ Es gibt aber nur $p$ verschiedene Restklassen mod $p.$ Also gibt es mindestens ein $x^2$ und ein $-1-y^2,$ die in der gleichen Restklasse liegen. Die Differenz $x^2 + y^2 + 1$ ist somit durch $p$ teilbar und das ist genau die obige Aussage. ∎

Wir führen nun den Abstieg durch:

Beweis des Theorems von Lagrange

Zunächst ergibt sich aus der Wahl von $x$ und $y$ in obigem Lemma folgende Abschätzung:

Die Teilbarkeitsaussage des obigen Lemmas lässt sich wie folgt formulieren: \[x^2 + y^2 + 1^2 + 0^2 = mp\] wobei für $m$ wegen der Abschätzung gilt $1 \leq m \lt p.$ Wir haben mithin gezeigt, dass für jede ungerade Primzahl $p$ eine Darstellung der Form \[x^2 + y^2 + z^2 + w^2 = mp\] möglich ist, mit $1 \leq m \lt p.$ Das ist der Ausgangspunkt für den Abstieg.

Wenn $m = 1$ gilt, sind wir fertig. Sei also $m \gt 1.$ Wir vollziehen nun den Abstieg getrennt für gerades und ungerades $m.$

Sei $m \gt 1$ gerade. Dann ist auch $mp$ gerade. Wenn eine Summe gerade ist, muss die Anzahl ungerader Summanden gerade sein (oder 0). Folglich kann man die Summanden immer zu Paaren zusammenfassen, deren Summe und Differenz gerade ist. Durch geeignete Umbenennung können wir erreichen dass $x^2, y^2$ sowie $z^2, w^2$ solche Paare sind. Das gilt nicht nur für die Quadrate sondern auch für $x, y, z$ und $w$ selbst. Demnach sind $(x \pm y)/2$ und $(z \pm w)/2$ ganze Zahlen und wir rechnen aus: $$ \begin{align*} {}& \left(\dfrac{ x+y}{ 2}\right)^2 + \left(\dfrac{ x-y}{ 2}\right)^2 + \left(\dfrac{ z+w}{ 2}\right)^2 + \left(\dfrac{ z-w}{ 2}\right)^2 \\[6pt] &= \dfrac{ 2x^2 + 2y^2}{ 4} + \dfrac{ 2z^2 + 2w^2}{ 4} \\[6pt] &= \dfrac{1}{2}(x^2 + y^2 + z^2 + w^2) \\[6pt] &= \dfrac{m}{2}p \end{align*} $$

Mit $x' = (x+y)/2$, $y' = (x-y)/2,$ $z' = (z+w)/2, w' = (z-w)/2$ und $m' = m/2$ haben wir daher den Abstieg zu einer Darstellung mit $m' \lt m$ vollzogen.

Nun sei $m \gt 1$ ungerade. Wir wählen $x_1 \equiv x \pmod{m},$ $y_1 \equiv y \pmod{m},$ $z_1 \equiv z \pmod{m},$ und $w_1 \equiv w \pmod{m}$ mit $|x_1|, |y_1|, |z_1|, |w_1| \lt m/2.$ Das ist immer möglich, denn für, $b = m - a$ gilt $a \equiv -b \pmod{m}$ und einer der Werte $|a|, |b|$ ist kleiner als $m/2,$ weil $m$ ungerade ist.

Nun ist \[x_1^2 + y_1^2 + z_1^2 + w_1^2 \equiv x^2 + y^2 + z^2 + w^2 \equiv 0 \pmod{m}\] Daher gibt es ein $m' \in \mathbb{Z}$ mit \[x_1^2 + y_1^2 + z_1^2 + w_1^2 = m'm\] Andererseits ist \[x_1^2 + y_1^2 + z_1^2 + w_1^2 \lt 4(m/2)^2 = m^2\] Also muss für $m'$ gelten $1 \leq m' \lt m.$ Wir wenden nun den Eulerschen Produktsatz auf die Quadratsummen für $mp$ und $m'm$ an und erhalten $$ \begin{align*} m^2m'p &= (x^2 + y^2 + z^2 + w^2)(x_1^2 + y_1^2 + z_1^2 + w_1^2) \\[10pt] &= a^2 + b^2 + c^2 + d^2 \end{align*} $$ mit $a, b, c, d$ wie aus dem Eulerschen Produktsatz.

Nun haben wir folgende Äquivalenzen mod $m$: $$ \begin{align*} a {}& \equiv xx_1 + yy_1 + zz_1 + ww_1 \equiv x^2 + y^2 + z^2 + w^2 \equiv 0 \pmod{m}\\ b {}& \equiv xy_1 -yx_1 + wz_1 - zw_1 \equiv xy -yx + wz -zw \equiv 0 \pmod{m} \\ c {}& \equiv xz_1 - zx_1 + yw_1 - wy_1 \equiv xz -zx + yw - wy \equiv 0 \pmod{m}\\ d {}& \equiv xw_1 - wx_1 + zy_1 - yz_1 \equiv xw -wx + zy -yz \equiv 0 \pmod{m} \end{align*} $$ Folglich sind $a, b, c, d$ durch $m$ teilbar. Wir erhalten also ganze Zahlen $x' = a/m, y' = b/m, z' = c/m$ und $w' = d/m$ mit \[x'^2 + y'^2 +z'^2 +w'^2 = \tfrac{1}{m^2}(a^2 +b^2 + c^2 + d^2) = m'p\] und $1 \leq m' \lt m$ womit der Abstieg auch im ungeraden Fall vollzogen und das Theorem von Lagrange vollständig bewiesen wäre. ∎

Der Beweis ist durchaus konstruktiv, d.h. man kann nach dem obigen Verfahren die Quadratsumme für eine Primzahl wirklich ausrechnen, wenn man die Summe für ein Vielfaches dieser Primzahl kennt. Das ist zwar nicht unbedingt die einfachste Methode, soll aber hier am Beispiel 95 demonstriert werden.

Es ist: \[ 95 = 9^2 + 3^2 + 2^2 + 1^2 = 5 \cdot 19\] Wir wollen für die Primzahl 19 die Zerlegung in vier Quadrate berechnen und bilden dazu die Restklassen der Summanden mod 5 (unser $m$): $$ \begin{align*} 9 {}& \equiv 4 \equiv -1 \pmod{5}\\ 3 {}& \equiv -2 \pmod{5} \\ 2 {}& \equiv 2 \pmod{5} \\ 1 {}& \equiv 1 \pmod{5} \end{align*} $$ Dann ist $(-1)^2 + (-2)^2 + 2^2 + 1^2 = 10 = 2 \cdot 5,$ also ist unser $m'$ gleich 2.

Wir rechnen nun $a, b, c, d$ nach dem Eulerschen Produktsatz aus: $$ \begin{align*} a &= xx_1 + yy_1 + zz_1 + ww_1 = -9 - 6 + 4 + 1 = -10 \\ b &= xy_1 -yx_1 + wz_1 - zw_1 = -18 -(-3) + 2 - 2 = -15 \\ c &= xz_1 - zx_1 + yw_1 - wy_1 = 18 -(-2) + 3 -(-2) = 25 \\ d &= xw_1 - wx_1 + zy_1 - yz_1 = 9 -(-1) + (-4) - 6 = 0 \\ \end{align*} $$ dividieren $a, b, c, d$ jeweils durch 5 und bilden die Summe \[(a/5)^2 + (b/5)^2 + (c/5)^2 + (d/5)^2 = 2^2 + 3^2 + 5^2 + 0^2 = 38 = 2 \cdot 19\] Wir haben so eine Darstellung für $m'p = 2 \cdot 19$ gefunden und können jetzt den Abstieg für gerades $m$ anwenden, wobei wir die beiden ungeraden Zahlen zusammenfassen müssen: \[ \left(\frac{ 5+3}{ 2}\right)^2 + \left(\frac{ 5-3}{ 2}\right)^2 + \left(\frac{ 2+0}{ 2}\right)^2 + \left(\frac{ 2-0}{ 2}\right)^2 \\ = 4^2 + 1^2 + 1^2 + 1^2 = 19 \] womit wir in der Tat eine Zerlegung von 19 in vier Quadrate gefunden haben.