Nat. Zahl als Summe von Quadratzahlen

07.10.2009, 15:55	pi_mal_Daumen	Auf diesen Beitrag antworten »
Nat. Zahl als Summe von Quadratzahlen Hallo! 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 $\begin{eqnarray} t=a^2+b^2,\ n-t=c^2+d^2 \end{eqnarray}$ darzustellen. Wenn das gelingt, dann ist $\begin{eqnarray} n=a^2+b^2+c^2+d^2 \end{eqnarray}$ 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 $\begin{eqnarray} m=uv^2 \end{eqnarray}$ wobei u quadratfrei ist, d.h., eine Darstellung $\begin{eqnarray} u=p_1p_2\ldots p_t \end{eqnarray}$ 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 $\begin{eqnarray} p_i=r_i^2+s_i^2,\ i=1,2,\ldots,t \end{eqnarray}$ finden und damit die komplexe Zahl $\begin{eqnarray} z=(r_1+is_1)\ldots(r_t+is_t)v \end{eqnarray}$ bilden. Dann ist $\begin{eqnarray} \Re(z)^2+\Im(z)^2=m \end{eqnarray}$ 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 $\begin{eqnarray} x^2 \equiv -1 \mod p \end{eqnarray}$ Dann musst du den Euklidischen Eukklidischen Algorithmus auf p und x solange anwenden, bis erstmals eine Rest r auftritt mit $\begin{eqnarray} r < \sqrt p \end{eqnarray}$ Es ist dann auch $\begin{eqnarray} s:=\sqrt{p-r^2} \end{eqnarray}$ ganzzahlig und es gilt $\begin{eqnarray} p=r^2+s^2 \end{eqnarray}$ . Ok, das war's....Ich hab das auch in Derive ausprobiert und es funktioniert bis etwa 30-stellige Zahlen in wenigen Sekunden...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »