Nat. Zahl als Summe von Quadratzahlen |
07.10.2009, 15:55 | pi_mal_Daumen | Auf diesen Beitrag antworten » |
Nat. Zahl als Summe von Quadratzahlen Ich hätte da mal eine Frage, wie man generell vorgeht, wenn man eine bestimmte Zahl als Summe von 4 Quadratzahlen schreiben soll (was nach Vorlesung stets möglich ist). Bei recht kleinen Zahlen ist das ja kein Problem, sodass man das noch ohne Probleme im Kopf lösen kann. Was aber mache ich denn genau, wenn die Zahlen etwas größer werden, und man das nicht mehr auf Anhieb sehen kann? Gibt es da einen konkreten Algorithmus? Konnte da leider nichts konkretes ausfindig machen. Hoffe mir kann jemand dazu sagen. |
||
08.10.2009, 16:39 | Mystic | Auf diesen Beitrag antworten » |
Das ist sicher eine sehr interessante Frage, auf die ich allerdings selbst die Antwort nicht genau weiß. Ich würde jedoch rein intuitiv so vorgehen: 1. Setze t := 0. 2. Versuche t und n-t in der Form darzustellen. Wenn das gelingt, dann ist eine Darstellung von n als Sume von 4 Quadraten und wir sind fertig. Andernfalls 3.Setze t := t+1 und mache bei 2. weiter. Damit stellt sich allerdings automatisch die Frage, welche Zahlen m man als Summe von 2 Quadraten darstellen kann und wie man eine solche Drrstellung findet. Dazu benötigst du zunächst einmal eine Zerlegung von m der Form wobei u quadratfrei ist, d.h., eine Darstellung als Produkt verschiedener Primzahlen besitzt. Darunter dürfen keine von der Form 4k+3 sein, andernfalls besitzt m keine Darstellung als Summe von 2 Quadraten. Wenn das zutrifft, musst du nun weiter für jede dieser Primzahlen eine Darstellung finden und damit die komplexe Zahl bilden. Dann ist die gesuchte Darstellung als Summe von 2 Quadraten. Bleibt als letztes die Frage, wie man Primzahlen der Form 4k+1 als Summe von 2 Quadraten darstellen kann. (Für die Primzahl 2 hat man ja die triviale Darstellung 2 =1+1.) Sei p eine solche Primzahl und x die größere der beiden Lösungen von Dann musst du den Euklidischen Eukklidischen Algorithmus auf p und x solange anwenden, bis erstmals eine Rest r auftritt mit Es ist dann auch ganzzahlig und es gilt . Ok, das war's....Ich hab das auch in Derive ausprobiert und es funktioniert bis etwa 30-stellige Zahlen in wenigen Sekunden... |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|