Fermat 4n+1 bzw. 4n-1 als Summe zweier Quadratzahlen
Burkart Venzke
irgendjemand schrieb irgendwo kürzlich:
> [...]
> oder diese unbewiesene annahme aus dem fermat buch:
> alle primzahlen der klassen 4n+1 und 4n-1 haben folgende eigenschaften:
>
> 4n+1 kann immer als summe zweier quadratzahlen dargestellt werden,
> 4n-1 nie.
>
> 3 = 4*1-1: -
> 5 = 4*1+1: 4+1 (2^2+1^2)
> 7 = 4*2-1: -
> 11 = 4*3-1: -
> 13 = 4*3+1: 9+4
> 17 = 4*4+1: 16+1
> 19 = 4*5-1: -
Die Aussage ist nur halb richtig; man kann leicht zeigen, daß die Zahlen 4n-1
niemals als Summe zweier Quadratzahlen darstellbar sind.
Wen es reizt, prüfe es nach.
Viele Grüße,
Burkart
--
_____________________________________________________________
NewsGroups Suchen, lesen, schreiben mit http://netnews.web.de
Helmut Richter
>> oder diese unbewiesene annahme aus dem fermat buch:
>> alle primzahlen der klassen 4n+1 und 4n-1 haben folgende eigenschaften:
>>
>> 4n+1 kann immer als summe zweier quadratzahlen dargestellt werden,
>> 4n-1 nie.
>Die Aussage ist nur halb richtig; man kann leicht zeigen, daß die Zahlen 4n-1
>niemals als Summe zweier Quadratzahlen darstellbar sind.
Die andere Richtung ist auch schon längst bewiesen (aber der Rand
dieses Postigns ist zu schmal, diesen wunderbaren Beweis zu fassen).
Helmut Richter
Burkart Venzke
Na, dann brauche ich ja die Lösung nicht mehr für die Welt suchen zu gehen (nur
noch für mich). :)
Helmut Richter
>Helmut....@lrz-muenchen.de (Helmut Richter) wrote:
>>"Burkart Venzke" <venzke....@eae.com> writes:
>>
>>>> oder diese unbewiesene annahme aus dem fermat buch:
>>>> alle primzahlen der klassen 4n+1 und 4n-1 haben folgende eigenschaften:
>>>>
>>>> 4n+1 kann immer als summe zweier quadratzahlen dargestellt werden,
>>>> 4n-1 nie.
>>
>>>Die Aussage ist nur halb richtig; man kann leicht zeigen, daß die Zahlen 4n-1
>>>niemals als Summe zweier Quadratzahlen darstellbar sind.
>>
>>Die andere Richtung ist auch schon längst bewiesen (aber der Rand
>>dieses Postigns ist zu schmal, diesen wunderbaren Beweis zu fassen).
>>
>>Helmut Richter
>Na, dann brauche ich ja die Lösung nicht mehr für die Welt suchen zu gehen (nur
>noch für mich). :)
Sei also p eine Primzahl der Gestalt 4n+1.
Im erst kürzlich beendeten Thread "Primes as sums of squares?" in der
Newsgruppe sci.math finden sich zwei Beweise. Beide sind wenig
konstruktiv insofern, als zwar aus der Existenz eines x, so dass x²+1
durch p teilbar ist, auf die Existenz eines y geschlossen wird, so
dass p-y² eine Quadratzahl ist, aber kein Weg gegeben wird, wie man
aus dem x das y ausrechnet (außer durchprobieren: sind ja nur endlich
viele Kandidaten).
Dabei wäre der eine, von Arturo Magidin gepostete, eigentlich ganz
konstruktiv: der Euklidische Algorithmus, der mit x und p startet,
kommt nämlich unterwegs bei y vorbei (sog. "Algorithmus von
Cornacchia"). Dafür weiß ich aber keinen einfachen Beweis.
In der Praxis findet man leichter das x zu gegebenem p als das y, so
dass man für den Algorithmus von Cornacchia recht dankbar ist.
Helmut Richter
Christian Schneider
>
> >>> oder diese unbewiesene annahme aus dem fermat buch:
> >>> alle primzahlen der klassen 4n+1 und 4n-1 haben folgende eigenschaften:
> >>> 4n+1 kann immer als summe zweier quadratzahlen dargestellt werden,
> >>> 4n-1 nie.
> >
> noch für mich). :)
Schlag nach bei Minkowski (Gitterpunktsatz)
Gruss, Christian
Helmut Kahovec
>| irgendjemand schrieb irgendwo kürzlich:
>|
>| > [...]
>| > oder diese unbewiesene annahme aus dem fermat buch:
>| > alle primzahlen der klassen 4n+1 und 4n-1 haben folgende eigenschaften:
>| >
>| > 4n+1 kann immer als summe zweier quadratzahlen dargestellt werden,
>| > 4n-1 nie.
Hallo Burkhart!
Dieses Thema ist schon öfters in de.sci.mathematik besprochen worden.
Ich habe mir die von Helmut Richter erwähnten Beiträge in sci.math
angeschaut und festgestellt, daß eigentlich kein einziger von ihnen
einen vollständigen Beweis enthält. Man findet aber den folgenden Satz
in jedem Buch über Zahlentheorie: "Eine Primzahl p kann genau dann als
Summe zweier Quadratzahlen dargestellt werden, wenn p+1 nicht durch 4
teilbar ist."
Meine bevorzugte Argumentation ist, zunächst sqrt(-1) zum Körper Q der
rationalen Zahlen zu adjungieren. Die Elemente des so erzeugten
quadratischen Zahlkörpers Q(sqrt(-1)) sind die Zahlen w=a+b*sqrt(-1),
wobei a und b rationale Zahlen aus Q sind. Für diese Zahlen ist eine
Norm definiert durch N(w)=N(a+b*sqrt(-1))=a^2+b^2=w*conjugate(w). Diese
Norm ist eine multiplikative Funktion in Q(sqrt(-1)).
Wenn a und b ganze Zahlen aus Z sind, dann bilden die entsprechenden
Elemente von Q(sqrt(-1)) den Ring Z(sqrt(-1)) der algebraisch ganzen
Zahlen in Q(sqrt(-1)). In diesem Ring gilt eine (bis auf die Reihenfolge
und die Einheiten -i,-1,i,1 als Vorfaktoren) eindeutige Faktorisierung
von algebraisch ganzen Zahlen in Primelemente, wofür die Existenz eines
euklidischen Algorithmus in Z(sqrt(-1)) eine hinreichende Bedingung ist.
Ringe, in denen ein euklidischer Algorithmus existiert, heißen
euklidisch. Z(sqrt(-1)) ist ein solcher.
Die eindeutige Faktorisierung in Primelemente bedeutet insbesondere, daß
in Z(sqrt(-1)) ein Primelement p entweder w1 oder w2 teilen muß, wenn p
Teiler des Produktes w1*w2 ist. Umgekehrt ist in Z(sqrt(-1)) q kein
Primelement, wenn q weder w1 noch w2 teilt, aber Teiler von w1*w2 ist.
Wir betrachten nun in Z die Primzahl q=4*n+1. Dann gilt nach dem Satz
von Wilson (q-1)!=-1 mod q, und q ist ein Teiler von (4*n)!+1. Modulo q
können wir diese Summe auch schreiben als
1*2*...*(2*n)*(-2*n)*...*(-2)*(-1) + 1 = 0 mod q
oder
((2*n)!)^2 + 1 = 0 mod q
bzw. in Z(sqrt(-1))
((2*n)!+i)*((2*n)!-i) = 0 mod q
In Z(sqrt(-1)) teilt q offensichtlich weder w1=((2*n)!+i) noch
w2=((2*n)!-i), ist aber Teiler von w1*w2. Daher kann q in Z(sqrt(-1))
keine Primzahl sein und besitzt dort die Zerlegung q=(a+b*i)*(c+d*i).
Aus der Multiplikativität der Norm in Z(sqrt(-1)) und dem Faktum, daß q
eine Primzahl in Z ist, können wir schließen, daß c=a und d=-b gelten
muß, und erhalten schließlich q=(a+b*i)*(a-b*i) oder q=a^2+b^2.
Die einzige gerade Primzahl 2=1^2+1^2 ist trivialerweise als Summe
zweier Quadratzahlen darstellbar.
Teilt man die ganzen Zahlen aus Z in gerade und ungerade Zahlen, dann
gibt es keine Kombination zweier Zahlen aus diesen beiden Klassen, deren
Quadratsumme von der Form 4*n+3 ist. Dies bestätigt man durch
Nachrechnen. Man sagt auch, daß durch Betrachtung modulo 2 die Zahlen
4*n+3 als Summe zweier Quadratzahlen ausgeschlossen werden können.
Insgesamt ist damit der oben angeführte Satz vollständig bewiesen.
MfG, Helmut
Helmut Kahovec
>| Ich habe mir die von Helmut Richter erwähnten Beiträge in sci.math
>| angeschaut und festgestellt, daß eigentlich kein einziger von ihnen
>| einen vollständigen Beweis enthält.
Nach nochmaligem Lesen der Beiträge in sci.math möchte ich meine obige
Behauptung zurückziehen. Dennoch finde ich den zitierten Beweis von
Niven-Zuckerman umständlich, und im Beweis von "Ray" fehlt der Hinweis
auf die eindeutige Faktorisierung in Z(sqrt(-1)). Diese ist aber das
entscheidende Argument im Beweis. Möglicherweise wird die eindeutige
Faktorisierung in Z(sqrt(-1)) von den Lesern in sci.math als Trivialität
angesehen und nicht für extra erwähnenswert gehalten.
MfG, Helmut
Helmut Richter
>Helmut Kahovec wrote:
Die ist eigentlich nicht trivial, weil es andere, ganz ähnlich
aussehende Ringe gibt, wo die eindeutige Faktorisierung nicht
gilt. Für Z(sqrt(-1)) haben wir aber gezeigt, dass es ein Euklidischer
Ring ist.
Ich erwähne das noch einmal, weil man damit sogar konstruktiv (also
anders als durch Durchprobieren der endlich vielen Möglichkeiten) aus
einer Wurzel von -1 mod p eine Zerlegung von p als Summe zweier
Quadrate gewinnt:
Sei x²=-1 (mod p). Dann gibt es (nichtkonstruktiv) a, b aus Z, so dass
p=(a+bi)(a-bi). Damit ist für irgendein k aus Z
(x+i)(x-i) = x²+1 = kp = k(a+bi)(a-bi)
Damit lässt sich a±bi als ggT von x±i und p mit dem Euklidischen
Algorithmus ausrechnen.
Damit wäre der (wohl eher nichttriviale) Algorithmus von Cornacchia
erst einmal unnötig, obwohl er weniger aufwendig ist. Es kann aber
sein, dass der Cornacchia im Wesentlichen einfach dieser Euklidische
Algorithmus in Z(sqrt(-1)) unter Weglassung der Imaginärteile ist;
muss ich mir mal anschauen.
Helmut Richter
Burkart Venzke
sagt mal, gibt's auch 'ne Möglichkeit, den Beweis mit einfacheren Mitteln
darzustellen?
Ich versuche mich ja durch Helmuts Beweis durchzukämpfen, aber mir fehlt das
Vokabular bzw. die Definitionen für einiges. Alleine die Gleichung (q-1)!=-1 mod
q macht mir schon Schwierigkeiten, weil ich mod nicht für negative Zahlen
(definiert) kenne.
Überhaupt wäre einiges gewonnen, wenn man die Mathematik (überhaupt die
Wissenschaften) ein wenig einfacher darstellen könnte/würde.
Andere Frage: Wo (Datum) stehen denn in dieser Newsgroup die früheren Postings
zu diesem Thema?
Viele Grüße,
Helmut Kahovec
>| Die ist eigentlich nicht trivial, weil es andere, ganz ähnlich
>| aussehende Ringe gibt, wo die eindeutige Faktorisierung nicht
>| gilt. Für Z(sqrt(-1)) haben wir aber gezeigt, dass es ein Euklidischer
>| Ring ist.
>|
>| Ich erwähne das noch einmal, weil man damit sogar konstruktiv (also
>| anders als durch Durchprobieren der endlich vielen Möglichkeiten) aus
>| einer Wurzel von -1 mod p eine Zerlegung von p als Summe zweier
>| Quadrate gewinnt:
>|
>| Sei x²=-1 (mod p). Dann gibt es (nichtkonstruktiv) a, b aus Z, so dass
>| p=(a+bi)(a-bi). Damit ist für irgendein k aus Z
>|
>| (x+i)(x-i) = x²+1 = kp = k(a+bi)(a-bi)
>|
>| Damit lässt sich a±bi als ggT von x±i und p mit dem Euklidischen
>| Algorithmus ausrechnen.
Hallo Helmut!
Stan Wagon beschreibt auf den Seiten 296-298 im Abschnitt 9.3 seines
Buches [1] genau diese Berechnung von a und b mit Hilfe des Euklidischen
Algorithmus in Z(sqrt(-1)). Überhaupt ist Kapitel 9 in seinem Buch eine
Fundgrube zu diesem Thema!
Auf ein Detail am Rande möchte ich aber doch noch hinweisen: Die
Existenz eines Euklidischen Algorithmus ist in einem Ring für die
eindeutige Zerlegung in Primelemente nur hinreichend, aber nicht
notwendig. So gibt es z.B. in den Ringen Z(sqrt(-19)), Z(sqrt(-43)),
Z(sqrt(-67)) und Z(sqrt(-163)) durchaus eine eindeutige Zerlegung in
Primelemente, obwohl in diesen Ringen kein Euklidischer Algorithmus
existiert. Somit gibt es für gewisse Primzahlen in Z zwar eindeutige
Darstellungen der Form a^2+19*b^2, a^2+43*b^2, a^2+67*b^2 und
a^2+163*b^2, diese können aber nicht mit einem Euklidischen Algorithmus
gefunden werden. Dies ist ein großer Nachteil, denn der Euklidische
Algorithmus ist ein sehr effizienter Algorithmus.
MfG, Helmut
Referenz:
[1] Stan Wagon, "Mathematica in Action", W.H. Freeman & Company 1991,
ISBN 0-7167-2202-X
Helmut Kahovec
>| sagt mal, gibt's auch 'ne Möglichkeit, den Beweis mit einfacheren Mitteln
>| darzustellen?
>|
>| Ich versuche mich ja durch Helmuts Beweis durchzukämpfen, aber mir fehlt das
>| Vokabular bzw. die Definitionen für einiges. Alleine die Gleichung (q-1)!=-1 mod
>| q macht mir schon Schwierigkeiten, weil ich mod nicht für negative Zahlen
>| (definiert) kenne.
... lines skipped ...
>| Andere Frage: Wo (Datum) stehen denn in dieser Newsgroup die früheren Postings
>| zu diesem Thema?
Hallo Burkhart!
Zu Deiner ersten Frage, ob es eine einfachere Darstellung des von mir
skizzierten Beweises gibt, möchte ich Dich bitten, die bereits von
Helmut Richter erwähnten Beiträge in sci.math zum Thema "Primes as sums
of squares?" anzuschauen. Der erste Beitrag dazu war am 3. Mai 2000.
Dort findest Du (unter anderem) eine ausgearbeitete Version des von mir
skizzierten Beweises vom Autor "spam...@Nil.nil". Du mußt selber
entscheiden, welche der beiden Beiträge leichter zu lesen ist.
Ein möglicherweise besonders leicht nachzuvollziehender Beweis stammt
von D. Zagier und kann auf den Seiten 19-20 von [1] nachgelesen werden.
Er wirft die interessante Frage auf, ob auch andere Sätze der
Zahlentheorie durch geeignete Abbildungen von endlichen Mengen auf sich
selbst bewiesen werden können.
Nun zu Deiner Frage bezüglich der negativen Reste: -1=q-1 mod q. Du
kannst immer +q oder -q zu einem Rest modulo q addieren. Mit negativen
und positiven Resten gleichzeitig zu arbeiten hat den Vorteil, daß der
Absolutbetrag eines solchen vorzeichenbehafteten Restes modulo n
höchstens gleich ceiling(n/2) ist. So sind die Reste modulo 5 sowohl
0,1,2,3,4 als auch -2,-1,0,1,2, diejenigen modulo 6 sowohl 0,1,2,3,4,5
als auch -2,-1,0,1,2,3. Weitere Einzelheiten findest Du in jedem Buch
über Zahlentheorie.
Frühere Diskussionen zu diesem Thema hier in de.sci.mathematik sind z.B.
(es ist der jeweils erste Beitrag der Diskussion angegeben):
> Wed, 25 Aug 1999, "Gibt es komplexe Primzahlen?", Sebastian Kunze
> Tue, 21 Sep 1999, "S:Beweis", Sebastian Kunze
> Sat, 30 Oct 1999, "Beweis", Michael Schmidt
> Thu, 13 Apr 2000, "Summe von vier Quadratzahlen", Thomas Heye
> Thu, 20 Apr 2000, "Puzzle: Faktorisierung von 10^184 + 1", Joe Leherbauer
MfG, Helmut
Referenz:
[1] M. Aigner, G. Ziegler, "Proofs from THE BOOK", Springer Verlag
Berlin 1998, ISBN 3-540-63698-6
Helmut Kahovec
>| Wieweit hängt die Eigenschaft, Euklidischer Ring zu sein, von der genauen
>| Definition eines solchen ab? Ich meine folgendes:
>|
>| Für einen Euklidischen Ring braucht man eine Wertfunktion w, so dass es
>| eine Division mit Rest gibt, bei der der Wert des Restes kleiner ist als
>| der Wert des Divisors. Damit der Euklidische Algorithmus funktioniert,
>| wird gemeinhin entweder gefordert,
>|
>| (a) dass der Wertebereich von w die natürlicher Zahlen ist oder
>|
>| (b) dass im Wertebereich von w es zu jeden Element nur endlich viele
>| kleinere Elemente gibt
>|
>| Aus (a) folgt (b) unmittelbar, und es gibt wohl, wenn es ein w mit (b)
>| gibt, immer auch ein anderes w mit (a). *Aber*: weder von (a) noch von (b)
>| wird im Beweis der Terminierung des Eu.Alg. Gebrauch gemacht. Dafür hätte
>| nämlich auch gereicht,
>|
>| (c) dass der Wertebereich von w wohlgeordnet ist.
>|
>| Gibt es jetzt vielleicht gar keine Hauptidealringe, die nicht auch Eu.R.
>| wären, wenn man deren Definition nicht so unnötig eng gemacht hätte?
Hallo Helmut!
Auf Deine letzte Frage habe ich leider auch keine Antwort. Wie die
Definition eines Euklidischen Ringes erweitert werden sollte, damit man
z.B. den Ring Z(sqrt(-5)) vom Ring Z(sqrt(-19)) unterscheiden kann, weiß
ich nicht. Beide Ringe haben keinen Euklidischen Algorithmus. Ersterer
hat die Klassenzahl 2 und damit keine eindeutige Zerlegung in
Primelemente, letzterer hat die Klassenzahl 1 und damit eine eindeutige
Primfaktorzerlegung. Die entscheidende Größe ist eben die Klassenzahl
und nicht die Existenz oder Nichtexistenz eines Euklidischen
Algorithmus.
Existiert in einem Zahlkörper ein Euklidischer Algorithmus, dann kann
man sicher sein, daß seine Klassenzahl gleich 1 ist und daß es in ihm
eine eindeutige Primfaktorzerlegung gibt. Im Falle eines
imaginärquadratischen Zahlkörpers mit Euklidischem Algorithmus kann die
Darstellung a^2+D*b^2 entsprechender Primzahlen mit verhältnismäßig
wenig Aufwand gewonnen werden. Wie das im Falle eines
imaginärquadratischen Zahlkörpers ohne Euklidischen Algorithmus
geschieht, habe ich noch nicht untersucht.
MfG, Helmut
Florian Weimer
> (b) dass im Wertebereich von w es zu jeden Element nur endlich viele
> kleinere Elemente gibt
>
> Aus (a) folgt (b) unmittelbar, und es gibt wohl, wenn es ein w mit (b)
> gibt, immer auch ein anderes w mit (a). *Aber*: weder von (a) noch von (b)
> wird im Beweis der Terminierung des Eu.Alg. Gebrauch gemacht.
Sicher? Man will i.d.R. eine Terminierung nach endlich vielen
Schritten, und nicht nach beliebig vielen Schritten. (Immerhin ist das
Algebra. ;)
> Dafür hätte nämlich auch gereicht,
> (c) dass der Wertebereich von w wohlgeordnet ist.
Das reicht nicht, denke ich.
> Gibt es jetzt vielleicht gar keine Hauptidealringe, die nicht auch Eu.R.
> wären, wenn man deren Definition nicht so unnötig eng gemacht hätte?
Natürlich. Aber ich fürchte, solche pseudo-euklidischen Ringe wären
i.a. nicht einmal Hauptidealringe.
Helmut Richter
>Helmut....@lrz-muenchen.de (Helmut Richter) writes:
>> Dafür hätte nämlich auch gereicht,
>> (c) dass der Wertebereich von w wohlgeordnet ist.
>Das reicht nicht, denke ich.
Denke doch. Ist M wohlgeordnet vermöge <, und f(x)<x für x>min M, dann
gibt es zu jeden m aus M ein n aus N, so dass f^(n)(m)= min M.
Beweis: Das kleinste Element in M, das nicht in endlich vielen
Schritten terminiert, kommt in einem Schritt auf eines, das schon in
endlich vielen Schritten terminiert.
Gell, transfinite Induktion ist was Feines. Ich weiß auch nicht, warum
man sie den meisten Mathematikern nicht beibringt.
Helmut Richter
Florian Weimer
> Gell, transfinite Induktion ist was Feines.
Ja.
> Ich weiß auch nicht, warum man sie den meisten Mathematikern nicht
> beibringt.
Ich glaube, ich hab's schon mal ohne Nachzudenken verwendet. ;)
Zurück zum ursprünglichen Frage, ob man den Begriff des Euklidischen
Ringes nicht allgemeiner fassen könnte: Aus meinem beschränkten
Blickwinkel sieht es sowieso so aus, als ob jeder darunter etwas
anderes verstünde. Häufig interessiert man sich sowieso nicht für den
euklidischen Algorithmus, sondern für die Bewertungsabbildung, die
vielleicht noch ein paar zusätzliche Eigenschaften hat
(z.B. multiplikativ oder additiv ist).