Eine quadratische diophantische Gleichung

Neue Frage »

Apatheia Auf diesen Beitrag antworten »
Eine quadratische diophantische Gleichung
Hallo!

Ich suche einen Algorithmus zum Lösen quadratischer diophantischer Gleichungen der folgenden Form:



Gesucht sind ganzzahlige Lösungen in x und y. Es sind die natürlichen Zahlen a,b,c,d gegeben. Der Algorithmus soll auch für große a,b,c,d effizient sein.

Ein Ansatz meinerseits war, die Gleichung mit der für quadratische diophantische Gleichungen üblichen Transformation auf folgende Form zu bringen:



Diese Form ist als Ausgangspunkt für einen effizienten Algorithmus aber für mich unbefriedigend, da F bei großen a,b,c,d auch sehr groß wird und ich nicht voraussetzen möchte, dass eine Faktorisierung von F bekannt ist. Das ist ärgerlich, denn für Gleichungen der Form



gäbe es, wenn D keine Quadratzahl ist, meiner Kenntnis nach durchaus schöne Algorithmen, die auf die Theorie zur Pell'schen Gleichung aufbauen.

Meine Frage: Kennt jemand andere Transformationen oder Ideen, die mir beim Lösen des Problems eine Hilfe sein könnten? Ich bin für jede Inspiration dankbar.
HAL 9000 Auf diesen Beitrag antworten »

Ich bin ein wenig irritiert: Du kannst es dir doch nicht "raussuchen", ob du im konkreten Einzelfall durch Umformung auf



oder auf



mit quadratfreiem D kommst: Schon allein deshalb, weil erstere Gleichung nur endlich viele Lösungen hat, und letztere unendlich viele (sofern sie überhaupt Lösungen hat), wenn ich mich richtig erinnere... verwirrt
Apatheia Auf diesen Beitrag antworten »

Das ist richtig. Ich habe es mir ja auch nicht ausgesucht. Ich komme, wie gesagt, auf die erste Gestalt. Es stimmt auch, dass die ursprüngliche Gleichung nur endlich viele Lösungen hat.
Mit meinem Verweis auf X^2-D*Y^2=F wollte ich lediglich deutlich machen, dass es für mich ärgerlich ist, dass es in solchen Fällen schöne Algorithmen gibt, mir im Falle der für mich interessanten Gleichung aber nichts Derartiges bekannt ist. Und genau darum geht es in meiner Frage.
Captain Kirk Auf diesen Beitrag antworten »

Ein Blick hierhin:
alpertron.com.ar/JQUAD.HTM
dürfte sich lohnen.
Apatheia Auf diesen Beitrag antworten »

Diese Seite war mir bereits bekannt und verweist für Gleichungen meines Typs leider lediglich auf die Faktorisierung



Kennen wir die Teiler von F, ist es aufgrund dieser Eigenschaft natürlich ein Leichtes, alle Lösungen der Gleichung zu bestimmen. Ich interessiere mich hingegen für alternative Ideen, in denen die Teiler von F nicht benötigt werden; etwa für Ansätze, bei denen die ursprüngliche Gleichung grundsätzlich anders transformiert wird.

Danke dennoch für die Antwort. : )
Captain Kirk Auf diesen Beitrag antworten »

Wie groß willst du denn die Zahlen machen, so dass F nicht mehr zu faktorisieren ist?
Und was willst du genau?
Eine Lösung oder alle?

Eine Lösung geht, wenn ich mich nicht verrechnet hab, sehr schnell, denn 4A|F.

Wenn es alle sein sollen würd ich auf den ersten Blick sagen, eine Lösung wär eine Veröffentlichung wert. Daher war wohl mathoverflow.net die bessere Anlaufstelle.
 
 
Apatheia Auf diesen Beitrag antworten »

Die Zahlen a,b,c,d können durchaus sehr groß sein. Eine Lösung ist mir bei meinem speziellen Problem sowieso grundsätzlich bekannt. Ich suche daher alle Lösungen.

Danke für den Hinweis auf MathOverflow.net, die Seite kannte ich noch nicht.
Apatheia Auf diesen Beitrag antworten »

Eine ähnliche Frage, für die ich nun keinen frischen Thread eröffnen wollte:

Wie sieht es mit der diophantischen Gleichung



aus, ebenfalls in den Unbekannten x und y und in den bekannten natürlichen Zahlen a,b,c,d,e. Was kubische diophantische Gleichungen betrifft, bin ich leider gar nicht bewandert. Gibts es auch hier übliche Transformationen und Normalformen? Schlussendlich würde ich auch ein Verfahren für die Lösungen dieser Gleichung suchen.

Danke für die Antwort.
HAL 9000 Auf diesen Beitrag antworten »

Im konkreten Beispiel würde ich zuerst umformen:



Nun Polynomdivision der linken Seite durch mit Rest, das ergebnis sei



Damit ist das Problem auf das simple reduziert. Natürlich kannst du dich auch hier wieder über die "komplizierte" Primfaktorzerlegung des möglicherweise sehr großen aufregen... Big Laugh


P.S.: Eine kurze Rechnung ergibt für die "neuen" Koeffizienten.
Apatheia Auf diesen Beitrag antworten »

Danke für die Idee. : )

Natürlich kannst du dich auch hier wieder über die "komplizierte" Primfaktorzerlegung des möglicherweise sehr großen aufregen...
Jo, das is leider noch immer ein Problem.^^

lg
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »