Matheseitenüberblick   •  lineare Gleichungssysteme   •  zurück   •  © Arndt Brünner

Lösungsverfahren für lineare diophantische Gleichungen

        ...funktioniert hier auch interaktiv, wenn Javascript aktiviert ist

Gleichungen, die nur ganzzahlige Koeffizienten und keine reellen Funktionen, wie z.B. Quadratwurzeln, oder transzendente Funktionen (Logarithmen oder trigonometrische Funktionen), enthalten, nennt man nach Diophantos von Alexandria (um 250 v.Chr.) Diophantische Gleichungen, wenn zusätzlich auch die Lösungen auf die Menge der Ganzen Zahlen Z eingeschränkt sind.

Beispiele:     3x² - 4x + 51y = 5      75x = 3y + 2       11a - 2b + 3c - 4d = 5

Spezialfälle dieser Gleichungen spielen eine wichtige Rolle in der Zahlentheorie; z.B. ist es für die Faktorzerlegung großer Zahlen n wichtig, ganzzahlige Lösungen der Gleichung x² - y² = n zu finden. (Wegen x²-y²=(x-y)(x+y) hat man damit zwei Faktoren gefunden. x ist der Mittelwert der Faktoren und y der Abstand zwischen Mittelwert und Faktoren.) Leider gibt es (noch?) kein allgemeines Verfahren, die Lösungen zu solchen Gleichungen zu finden.

Zu anderen Typen gibt es jedoch Verfahren, etwa zu den sogenannten Pellschen Gleichungen x² - dy² = 1, wobei d eine bekannte Zahl darstellt.

Hier soll allerdings ein Verfahren dargestellt werden, mit dem man Lösungen zu diophantischen Gleichungen finden kann, deren Variablen alle in der ersten Potenz stehen, also keine Exponenten besitzen. Solche Gleichungen nennt man linear.

Unter der Voraussetzung, daß der größte gemeinsame Teiler (ggT) der Koeffizienten, d.h. der Faktoren vor den Variablen, ein Teiler der konstanten Zahl ist, haben diese Gleichungen stets unendlich viele Lösungen. Man kann diese in Abhängigkeit freier Parameter angeben, die jeweils die Menge der Ganzen Zahlen durchlaufen können.

Gib eine beliebige lineare Gleichung ein und betätige die Schaltfläche. Es sind keine Klammerausdrücke, keine Brüche (siehe dazu die Hinweise unten), Kommazahlen oder Potenzen erlaubt.

         

Hinweise:
Es sind Variablen aus dem kompletten Alphabet möglich, ihre Zahl ist "nicht auf wenige" eingeschränkt. Aus Speichergründen kann das Script allerdings nicht beliebig viele Variablen verarbeiten. Die Eingabeart ist insofern frei, als die Variablen und Konstanten links und rechts vom Gleichheitszeichen stehen dürfen - auch mehrere Summanden mit gleicher Variable. Die Gleichung wird jedoch automatisch normalisiert, und auch im Eingabefeld mit der zusammengefaßten Version überschrieben.
Es sind auch mehrbuchstabige Variablennamen möglich; Anzeigeprobleme bei der Detaildarstellung gibt es, wenn kürzere Variablennamen in längeren enthalten sind. (Die Substitution erfolgt für die Anzeige über Stringmanipulationen.) Unabhängig davon werden jedoch die Ergebnisse wieder korrekt angezeigt.

Es ist interessant und aufschlußreich, das Verfahren auch auf Gleichungen loszulassen, die nicht lösbar sind, denn das Scheitern des Algorithmus beleuchtet recht deutlich, warum es in diesen Fällen keine ganzzahligen Lösungen geben kann und inwiefern das mit der Teilbarkeit der Konstante durch den ggT der Koeffizienten zusammenhängt.

Ganzzahlige Lösungen von Gleichungen mit rationalen Koeffizienten kann man mit demselben Verfahren finden, indem man die Gleichung zunächst mit dem kgV der Nenner multipliziert. So werden alle Koeffizienten ganzzahlig. Ich habe experimentell diese Möglichkeit auch im Script vorgesehen, vermute aber, daß es nicht ganz fehlerlos funktioniert. Hier kann diese Funktion zu- und abgeschaltet werden:
rationale Koeffizienten in der Eingabe zulassen und Gleichung automatisch umwandeln.

Das Script macht automatisch die Probe mit 10 Zufallswerten für die Parameter. Ein falsches Resultat wird auf jeden Fall angezeigt. Auch die Ganzzahldivisionen während der Laufzeit werden überprüft und im Fehlerfalle per Meldung angezeigt. Ursache waren in allen mir bekannten Fällen Rundungsfehler bei sehr großen Zahlen oder Programmierfehler, die natürlich sofort behoben wurden. Bitte schreiben Sie mir eine Mail, falls Sie weitere Fehler entdecken!

Proben anzeigen

© Arndt Brünner, 2./3. 1. 2003
Matheseitenüberblick
zurück
Lösen linearer Gleichungssysteme
Lösen linearer Gleichungen mit einer Unbekannten
Euklidischer Algorithmus
Kettenbruchentwicklung
Pythagoreische Zahlentripel
Polynomdivision
Forum
Gästebuch
Version: 8. 8. 2003