Zwei-Quadrate-Satz

Der Zwei-Quadrate-Satz von Fermat ist ein mathematischer Satz der Zahlentheorie:

Eine ungerade Primzahl $p$ kann genau dann in der Form

$p=x^2+y^2$

mit ganzzahligen $x$ und $y$ dargestellt werden, wenn

$p\equiv 1(\mathrm{mod}4).$

Primzahlen, die letztere Bedingung erfüllen, nennt man auch pythagoreische Primzahlen.

Beispielsweise sind die Primzahlen 5, 13, 17, 29, 37, 41 kongruent zu 1 modulo 4 und können als Summe zweier Quadrate geschrieben werden:

$\begin{array}{cc}5& =1^2+2^2\\ 13& =2^2+3^2\\ 17& =1^2+4^2\\ 29& =2^2+5^2\\ 37& =1^2+6^2\\ 41& =4^2+5^2\end{array}$

Andererseits sind die Primzahlen 3, 7, 11, 19, 23 und 31 kongruent zu 3 modulo 4 und können nicht als Summe zweier Quadrate geschrieben werden.

Als Arbeitsdefinition wird im Folgenden darstellbare Zahl kurz für „Zahl, die eine Darstellung als Summe zweier Quadratzahlen besitzt“ gebraucht. Dies entspricht auch dem Sprachgebrauch des im Buch der Beweise vorgestellten Beweises, den wir im Folgenden skizzieren wollen:

Der einfachere Teil des Satzes (dass jede darstellbare ungerade Primzahl pythagoreisch ist) folgt ganz leicht aus der Tatsache, dass ein Quadrat modulo 4 nur zu 0 oder zu 1 kongruent sein kann. Daher ging es immer nur darum, zu zeigen, dass auch umgekehrt jede pythagoreische Zahl darstellbar ist.

Historische Bemerkungen

Als Erster hat Albert Girard diese Beobachtung gemacht, er hat sogar alle (nicht nur die primen) positiven, ganzen Zahlen beschrieben, die als Summe zweier Quadrate ausgedrückt werden können, dies wurde 1625 veröffentlicht. Die Aussage, dass jede Primzahl der Form $4n+1$ die Summe zweier Quadrate ist, heißt manchmal Satz von Girard. Diesen Teil der Aussage sowie die Bestimmung der Anzahl der verschiedenen Möglichkeiten, eine gegebene Primzahlpotenz als Summe zweier Quadrate zu schreiben, hat Fermat in einem Brief an Marin Mersenne ausgearbeitet, dieser datiert vom 25. Dezember 1640. Daher wird diese Version des Satzes manchmal auch Fermats Weihnachtstheorem genannt.

Beweise des Zwei-Quadrate-Satzes

Üblicherweise hat Fermat keine Beweise seiner Behauptungen veröffentlicht, auch für den Zwei-Quadrate-Satz hat er keinen Beweis geliefert. Ein erster Beweis wurde mit viel Aufwand mittels der Methode des unendlichen Abstiegs von Euler gefunden. Er hatte ihn zunächst in zwei Briefen vom 6. Mai 1747 und 12. April 1749 an Goldbach angekündigt, der vollständige Beweis wurde dann zwischen 1752 und 1755 in zwei Artikeln veröffentlicht. Lagrange erbrachte 1775 einen Beweis mittels seiner Untersuchungen über quadratische Formen. Dieser wurde von Gauß in seinen Disquisitiones Arithmeticae vereinfacht. Dedekind lieferte mindestens zwei Beweise, die auf der Arithmetik gaußscher Zahlen fußen. Weiter gibt es einen eleganten Beweis, der den minkowskischen Gitterpunktsatz verwendet. 2016 veröffentlichte D. Christopher einen kombinatorisch-zahlentheoretischen Beweis.

Eulers Beweis mit der Methode des unendlichen Abstiegs

Der Beweis von Euler besteht aus fünf Schritten. Die ersten vier Schritte sind die Sätze 1 bis 4 aus dem ersten der oben erwähnten Artikel, der fünfte Schritt stammt aus dem zweiten Artikel.

Im Folgenden kann auch die Null Summand der „Summe zweier Quadrate“ sein. Somit können auch Quadratzahlen als Summen zweier Quadrate aufgefasst werden.

1. Das Produkt zweier Zahlen, die jeweils als Summen zweier Quadrate darstellbar sind, lässt sich selbst als Summe zweier Quadrate schreiben.

Dies ist eine wohlbekannte Eigenschaft, die auf der Identität

$(a^2+b^2)(p^2+q^2)=(ap+bq{)}^2+(aq-bp{)}^2$

beruht, die auf Diophant zurückgeht.

2. Wenn die Summe zweier Quadrate durch eine Primzahl teilbar ist, die sich ebenfalls als Summe zweier Quadrate schreiben lässt, dann ist auch der Quotient die Summe zweier Quadrate. (Satz 1 in Eulers erstem Artikel)

Zum Beweis wird angenommen, dass $a^2+b^2$ durch $p^2+q^2$ teilbar ist, wobei der letzte Term eine Primzahl ist. Dann teilt $p^2+q^2$ auch

$(pb-aq)(pb+aq)=p^2{b}^2-a^2{q}^2=p^2(a^2+b^2)-a^2(p^2+q^2).$

Da $p^2+q^2$ eine Primzahl ist, muss es einen der beiden Faktoren teilen. Zunächst wird angenommen, dass $p^2+q^2$ Teiler von $pb-aq$ ist. Wegen Diophants Identität

$(a^2+b^2)(p^2+q^2)=(ap+bq{)}^2+(aq-bp{)}^2$

folgt daraus, dass $p^2+q^2$ Teiler von $(ap+bq{)}^2$ ist.

Daher kann die Gleichung durch das Quadrat von $p^2+q^2$ dividiert werden, ohne den Bereich der ganzen Zahlen zu verlassen. Es ergibt sich

$\frac{a^2+b^2}{p^2+q^2}={\left(\frac{ap+bq}{p^2+q^2}\right)}^2+{\left(\frac{aq-bp}{p^2+q^2}\right)}^2.$

Das bedeutet, dass der Quotient, wie behauptet, die Summe zweier Quadrate ist.

Entsprechendes gilt, wenn $p^2+q^2$ Teiler von $pb+aq$ ist. Für die Begründung verwendet man eine Variante von Diophants Identität, nämlich

$(a^2+b^2)(q^2+p^2)=(aq+bp{)}^2+(ap-bq{)}^2.$

3. Wenn die Summe zweier Quadrate durch eine Zahl teilbar ist, die sich nicht als Summe zweier Quadrate schreiben lässt, dann hat der Quotient einen Teiler, der nicht als Summe zweier Quadrate darstellbar ist. (Satz 2 aus Eulers zweitem Artikel)

$q$ sei ein Teiler von $a^2+b^2$, der sich nicht als Summe zweier Quadrate ausdrücken lässt. Der Quotient wird in (möglicherweise mehrfach auftretende) Primfaktoren zerlegt, also in der Form $p_1{p}_2\cdots p_n$ geschrieben, sodass $a^2+b^2=q{p}_1{p}_2\cdots p_n$ gilt. Wenn alle Faktoren $p_i$ als Summen zweier Quadrate darstellbar sind, dann kann man $a^2+b^2$ der Reihe nach durch $p_1$, $p_2$ usw. dividieren; aus Schritt (2.) schließt man, dass die kleiner werdenden Quotienten jeweils Summen zweier Quadrate sind. Letztendlich wäre $q$ selbst die Summe zweier Quadrate, was in Widerspruch zur Voraussetzung steht. Folglich ist wenigstens eine der Primzahlen $p_i$ nicht die Summe zweier Quadrate.

4. Sind $a$ und $b$ teilerfremde natürliche Zahlen, dann ist jeder Faktor von $a^2+b^2$ die Summe zweier Quadrate. (Dieser Schritt verwendet Schritt (3.), um einen ‚unendlichen Abstieg‘ zu erzeugen, und entspricht dem Satz 4 in Eulers erstem Artikel. Der Beweis, der hier skizziert wird, enthält auch den Beweis von Eulers Satz 3.)

Es seien $a,b$ teilerfremde natürliche Zahlen. Ohne Beschränkung der Allgemeinheit sei $a^2+b^2$ nicht selbst prim, denn sonst gäbe es nichts zu beweisen. Es sei daher $q$ ein echter Teiler von $a^2+b^2$, nicht notwendig eine Primzahl: Wir wollen zeigen, dass $q$ die Summe zweier Quadrate ist. Dabei kann $q>2$ vorausgesetzt werden, da der Fall $q=2=1^2+1^2$ offensichtlich ist.

$m$ und $n$ seien die nicht-negativen ganzen Zahlen mit der Eigenschaft, dass $mq$ bzw. $nq$ (dem Betrag nach) so nahe wie möglich bei $a$ bzw. $b$ liegt. Man beachte, dass die Differenzen $c=a-mq$ und $d=b-nq$ ganze Zahlen sind, deren absolute Beträge kleiner als $q/2$ sind.

Durch Ausmultiplizieren erhalten wir

$a^2+b^2=m^2{q}^2+2mqc+c^2+n^2{q}^2+2nqd+d^2=Aq+(c^2+d^2),$

wobei $A$ eine eindeutig bestimmte nicht-negative ganze Zahl ist. Da $q$ Teiler von $a^2+b^2$ ist, muss auch $c^2+d^2$ durch $q$ teilbar sein: $c^2+d^2=qr$ mit einer ganzen Zahl $r$. Es sei nun $g$ der größte gemeinsame Teiler von $c$ und $d$, der wegen der Teilerfremdheit von $a$ und $b$ teilerfremd zu $q$ ist. Folglich ist $g^2$ Teiler von $r$. Setzt man $e=c/g$, $f=d/g$ und $s=r/g^2$, erhält man $e^2+f^2=qs$. $e$ und $f$ sind teilerfremd und es gilt $s<q/2$ wegen

$qs=e^2+f^2\le c^2+d^2<{\left(\frac{q}{2}\right)}^2+{\left(\frac{q}{2}\right)}^2=q^2/2.$

Nun erfolgt schließlich der Abstiegsschritt: Wenn $q$ nicht die Summe zweier Quadrate ist, dann muss es gemäß (3.) einen Faktor von $s$, etwa $q_1$, geben, der nicht Summe zweier Quadrate ist. Es gilt jedoch $q_1\le s<q/2<q$. Wiederholt man diese Schritte (beginnend mit $e,f;q_1$ anstelle von $a,b;q$) immer wieder, so findet man eine streng monoton abnehmende unendliche Folge $q,q_1,q_2,\dots$ von natürlichen Zahlen, die jeweils nicht als Summe zweier Quadrate darstellbar sind. Weil ein solcher unendlicher Abstieg unmöglich ist, muss $q$ die Summe zweier Quadrate sein, wie behauptet.

5. Jede Primzahl der Form $4n+1$ ist die Summe zweier Quadrate. (Hauptresultat von Eulers zweitem Artikel)

Wenn $p=4n+1$ gilt, dann ist nach dem kleinen fermatschen Satz jede der Zahlen $1,2^{4n},3^{4n},\dots ,(4n{)}^{4n}$ kongruent zu 1 modulo $p$. Die Differenzen $2^{4n}-1,3^{4n}-2^{4n},\dots ,(4n{)}^{4n}-(4n-1{)}^{4n}$ sind daher alle durch $p$ teilbar. Jede dieser Differenzen kann faktorisiert werden als

$a^{4n}-b^{4n}=(a^{2n}+b^{2n})(a^{2n}-b^{2n}).$

Als Primzahl muss $p$ einen der beiden Faktoren teilen. Wenn $p$ in jedem der $4n-1$ Fälle den ersten Faktor teilt, kann man nach dem letzten Schritt schließen, dass $p$ selbst die Summe zweier Quadrate ist; $a$ und $b$ unterscheiden sich nämlich um 1 und sind daher teilerfremd. Es genügt also zu zeigen, dass $p$ nicht immer den zweiten Faktor teilen kann.

Angenommen, $p$ teilt alle $4n-1$ Differenzen $2^{2n}-1,3^{2n}-2^{2n},\dots ,(4n{)}^{2n}-(4n-1{)}^{2n}$. Dann teilt $p$ auch alle $4n-2$ Differenzen der ursprünglichen Differenzen, alle $4n-3$ Differenzen von deren Differenzen und so weiter. Da die $k$-ten Differenzen der Folge $1^k,2^k,3^k,\dots$ alle gleich $k!$ sind, wären die $2n$-ten Differenzen alle konstant und gleich $(2n)!$. Andererseits ist $(2n)!$ sicher nicht durch $p$ teilbar. $p$ kann also nicht alle zweiten Faktoren teilen. Durch diesen Widerspruch ist bewiesen, dass $p$ tatsächlich die Summe zweier Quadrate ist.

Beweis mit dem Gitterpunktsatz von Minkowski

Ist $p$ eine Primzahl, die kongruent zu 1 modulo 4 ist, dann ist $-1$ nach dem eulerschen Kriterium ein quadratischer Rest modulo $p$. Daher existiert eine ganze Zahl $m$, sodass $p$ Teiler von $m^2+1$ ist. Es seien nun ${𝐞}_{\mathrm{𝟏}}$, ${𝐞}_{\mathrm{𝟐}}$ die Elemente der Standardbasis des Vektorraums ${ℝ}^2$, außerdem $𝐮={𝐞}_{\mathrm{𝟏}}+m{𝐞}_{\mathrm{𝟐}}$ und $𝐯=0{𝐞}_{\mathrm{𝟏}}+p{𝐞}_{\mathrm{𝟐}}$. Man betrachtet das Gitter $S=\{a𝐮+b𝐯\mid a,b\in \mathbb{Z}\}$. Wenn $𝐰=a𝐮+b𝐯=a{𝐞}_{\mathrm{𝟏}}+(am+bp){𝐞}_{\mathrm{𝟐}}$ Element von $S$ ist, gilt $\Vert 𝐰{\Vert }^2=a^2+(am+bp{)}^2\equiv a^2(1+m^2)\equiv 0(\mathrm{mod}p)$. Daher ist $p$ für jedes $𝐰\in S$ ein Teiler von $\Vert 𝐰{\Vert }^2$.

Der Flächeninhalt der Grundmasche (Fundamentalmasche) des Gitters ist $p$. Der Flächeninhalt der offenen Kreisscheibe $D$ mit dem Mittelpunkt im Ursprung und dem Radius $\sqrt{2p}$ beträgt $2\pi p>4p$. Außerdem ist $D$ konvex und symmetrisch bezüglich des Ursprungs. Daher existiert nach dem Gitterpunktsatz von Minkowski ein vom Nullvektor verschiedener Vektor $𝐰\in S$ mit $𝐰\in D$. Weil $\Vert 𝐰{\Vert }^2<2p$ gilt und $p$ Teiler von $\Vert 𝐰{\Vert }^2$ ist, muss $p=\Vert 𝐰{\Vert }^2$ gelten. Folglich ist $p$ die Summe zweier Quadrate, nämlich der Quadrate der Koordinaten von $𝐰$.

Don Zagiers Beweis

Berühmt geworden ist ein Beweis von Don Zagier, den er selbst als „Einzeiler“ bezeichnete (one-sentence proof). Dies ist eine Vereinfachung eines früheren kurzen Beweises von Heath-Brown, der wiederum von auf Lagrange zurückgehenden Ideen inspiriert war.

Der Beweis lautet folgendermaßen: Für eine Primzahl $p=4k+1$ hat die auf der endlichen Menge $S=\{(x,y,z)\in {\mathbb{N}}^3:x^2+4yz=p\}$ definierte Involution, gegeben durch

$(x,y,z)\mapsto \{\begin{array}{c}(x+2z,z,y-x-z),\text{wenn}x<y-z\\ (2y-x,y,x-y+z),\text{wenn}y-z<x<2y\\ (x-2y,x-y+z,y),\text{wenn}x>2y\end{array}$

einen Fixpunkt. Daher ist die Mächtigkeit $|S|$ ungerade. Aus dieser Tatsache kann man folgern, dass auch die Involution $(x,y,z)\mapsto (x,z,y)$ auf $S$ einen Fixpunkt besitzt. Weil für diesen Fixpunkt $y=z$ gelten muss, folgt $x^2+4y^2=p,$ d. h., $p$ lässt sich als Summe zweier Quadratzahlen schreiben.

Zagier gab im selben Artikel, in dem er den Beweis vorstellte, zu, dass dieser one-sentence proof mehrere Annahmen trifft, die man mit mehr als einem Satz erklären müsse – wie, dass die Menge $S$ endlich ist, dass die erste Abbildung eine wohldefinierte Involution mit eindeutig bestimmtem Fixpunkt ist und wie genau daraus der Zwei-Quadrate-Satz folgt.

Verwandte Resultate

Vierzehn Jahre später hatte Fermat zwei verwandte Resultate angekündigt. In einem Brief vom 25. September 1654 an Blaise Pascal behauptete er über eine ungerade Primzahl $p$:

• $p$ ist genau dann von der Form $x^2+2y^2$, wenn $p\equiv 1\text{ oder }p\equiv 3(\mathrm{mod}8)$,
• $p$ ist genau dann von der Form $x^2+3y^2$, wenn $p\equiv 1(\mathrm{mod}3)$.

Weiter schrieb er:

Enden zwei Primzahlen auf die Ziffern 3 oder 7 und sind beide um 3 größer als ein Vielfaches von 4, so ist ihr Produkt eine Summe aus einem Quadrat und dem Fünffachen eines Quadrates.

Mit anderen Worten, wenn $p$ und $q$ Primzahlen der Form $20k+3$ oder $20k+7$ sind, dann ist $pq$ von der Form $x^2+5y^2$. Euler hat dies später zu der Vermutung ausgeweitet, dass gilt:

• $p$ ist genau dann von der Form $x^2+5y^2$, wenn $p\equiv 1\text{ oder }p\equiv 9(\mathrm{mod}20)$,
• $2p$ ist genau dann von der Form $x^2+5y^2$, wenn $p\equiv 3\text{ oder }p\equiv 7(\mathrm{mod}20)$.

Beide Behauptungen von Fermat sowie die von Euler aufgestellten Vermutungen wurden schließlich von Lagrange bewiesen.

Algorithmische Lösung

Die gesuchten Zahlen $x,y$, mit denen $p=x^2+y^2$ gilt, lassen sich algorithmisch finden. Ein naheliegender Algorithmus ergibt sich mithilfe des Lemmas von Thue und lautet folgendermaßen: Für ein natürliches $x$ mit $1\le x<\sqrt{p}$ überprüfe man, ob $\sqrt{p-x^2}$ eine ganze Zahl ist. Falls dies so ist, so hat man das $x$ gefunden und das $y$ ergibt sich von selbst. Jedoch wächst mit größer werdendem $p$ der Rechenaufwand exponentiell, sodass sich dieser Weg nur für kleinere Primzahlen eignet.

Der Mathematiker Stan Wagon gab einen Algorithmus an, der unter Benutzung des euklidischen Algorithmus das Problem in Polynomialzeit löst.

Darstellung natürlicher Zahlen als Summe zweier Quadratzahlen

Auf den Zwei-Quadrate-Satz aufbauend kann man sich fragen, welche natürlichen Zahlen (nicht nur Primzahlen) als Summe zweier Quadratzahlen darstellbar sind. Hieraus ergibt sich folgender Satz (siehe Satz über die Summe zweier Quadrate):

Genau dann ist eine natürliche Zahl darstellbar als Summe zweier Quadratzahlen, wenn in der Primfaktorzerlegung jeder Primfaktor der Form $4m+3$ mit geradem Exponenten auftritt.

Beweisskizze

Für die eine Richtung benötigt man folgende Tatsachen:

• Die Zahlen $1$ und $2$ sind darstellbar, denn $1=1^2+0^2$ und $2=1^2+1^2$.
• Nach dem Zwei-Quadrate-Satz sind ungerade Primzahlen nur darstellbar, wenn sie von der Form $4m+1$ sind.
• Nach der Brahmagupta–Fibonacci-Identität ist das Produkt zweier darstellbarer Zahlen wieder darstellbar.
• Wenn $n=x^2+y^2$ darstellbar ist, so ist auch $n{z}^2$ für $z\in \mathbb{Z}$ darstellbar, denn

$n{z}^2=(zx{)}^2+(zy{)}^2.$

Für die Rückrichtung benötigt man zusätzlich folgende Aussagen:

• Ist $4m+3$ eine Primzahl, die eine darstellbare Zahl $n=x^2+y^2$ teilt, so teilt sie auch $x$ und $y$.
• Wenn $n$ darstellbar ist und durch eine Primzahl der Form $4m+3$ teilbar ist, so ist $n$ auch durch $(4m+3{)}^2$ teilbar und der Quotient $n/(4m+3{)}^2$ ist immer noch darstellbar.

Die ganze Aussage ergibt sich dann, indem man die Primfaktorzerlegung betrachtet.

Beispiel

Die Zahl $127050643720$, gegeben durch die Primfaktorzerlegung $2^3\cdot 5\cdot 7^4\cdot 11^2\cdot 13\cdot 29^2$, ist darstellbar als Summe zweier Quadratzahlen. Nicht nur ist die Existenz bewiesen; aus dem Abschnitt zur algorithmischen Lösung und der Beweisskizze kann man die Darstellung sogar per Hand berechnen.

Dafür findet man zunächst die Darstellungen der darstellbaren Primfaktoren (das wären hier $2$, $5$ und $13$). Dann ergibt sich unter Anwendung der Brahmagupta–Fibonacci-Identität und der Tatsache $n{z}^2=(zx{)}^2+(zy{)}^2$ die folgende Darstellung als Summe:

$127050643720=35574^2+354662^2$

Würde man $127050643720$ mit $7$ multiplizieren, dann wäre das Ergebnis nach dem obigen Resultat nicht mehr als Summe zweier Quadratzahlen darstellbar, da $7$ geteilt durch $4$ den Rest $3$ hinterlässt, aber dann mit ungeradem Exponenten aufträte.

Verhältnis zu den Gaußschen Zahlen

Vorlage:Hauptartikel Es besteht eine sehr starke Beziehung zu den Gaußschen Zahlen $\mathbb{Z}[\mathrm{i}]$. Denn die Primelemente im Ring der Gaußschen Zahlen sind (abgesehen von den vier Einheiten $\pm 1,\pm \mathrm{i}$ als Faktoren) genau die Primzahlen der Form $4k+3,k\in {\mathbb{N}}_0$, die Zahl $1+i$ und die Zahlen $a+b\cdot \mathrm{i},a,b\in \mathbb{Z}$, für die $a^2+b^2=p$ eine Primzahl in $\mathbb{Z}$ ist, die man als $p=4k+1,k\in \mathbb{Z}$ schreiben kann.

Mit etwas Arbeit lässt sich daraus sogar die Leibniz-Reihe herleiten, wie das Edmund Weitz im Laufe seines Buches Pi und Primzahlen vorgestellt hat.

Siehe auch

• Drei-Quadrate-Satz von Legendre
• Vier-Quadrate-Satz von Lagrange
• Quadratsummen-Funktion
• Lemma von Thue

Literatur und Weblinks

• L. E. Dickson: History of the Theory of Numbers. Band 2. Chelsea Publishing Co., New York 1920.
• J. Stillwell: Introduction zu: Richard Dedekind: Theory of Algebraic Integers. Cambridge University Library, Cambridge University Press 1996, ISBN 0-521-56518-9.
• D. A. Cox: Primes of the Form x² + ny². Wiley-Interscience 1989, ISBN 0-471-50654-0.
• Manon Bischoff: Ein Theorem rund um Weihnachten, Windmühlen und Primzahlen. Artikel auf Spektrum.de mit Beweisskizze.