Diophantische Gleichungen
Eine Gleichung der Form mit ganzzahligen Koeffizienten a, b und c, für die ganze Zahlen x und y als Lösungen gesucht sind, heißt eine (lineare) diophantische Gleichung in zwei Unbekannten.
Diophantische Gleichungen können gelöst werden durch systematisches Probieren, mit der Methode der korrespondieren Kongruenzen, mittels formaler Bruchschreibweise sowie mithilfe des euklidischen Algorithmus.
Von Alltagsproblemen sind Aufgaben folgender Art bekannt:
- Beispiel 1: Für fünf Euro sollen zwei Sorten Kuchen zu bzw. zu gekauft werden.
- Beispiel 2: Für zehn Euro sind Briefmarken zu und von der Post mitzubringen.
- Beispiel 3: Kann man für 25 Euro Socken zu vier Euro und zu sechs Euro kaufen?
In allen Fällen kommen nur natürliche Zahlen als Lösungen infrage (falls das Problem überhaupt lösbar ist). Ein Rest darf nicht auftreten. Es sind somit spezielle lineare Gleichungen zu lösen.
- Eine Gleichung der Form
mit ganzzahligen Koeffizienten a, b und c, für die ganze Zahlen x und y als Lösungen gesucht sind, heißt eine (lineare) diophantische Gleichung in zwei Unbekannten.
Anmerkung: Entsprechend heißen Gleichungen der Form diophantische Gleichungen mit n Unbekannten.
Die diophantische Gleichung lässt sich auch als lineare Kongruenz schreiben, denn aus ergibt sich mit :
Wir beweisen den folgenden Satz:
- Die diophantische Gleichung bzw. die lineare Kongruenz ist genau dann lösbar, wenn der größte gemeinsame Teiler von a und b auch ein Teiler von c ist, wenn also gilt:
Beweis:
(1) sei Teiler von c.
Der größte gemeinsame Teiler von a und b lässt sich stets als Linearkombination von a und b mit ganzen Zahlen u und v schreiben:
Die Voraussetzung bedeutet, dass es eine ganze Zahl w gibt, mit . Multipliziert man obige Gleichung mit w, erhält man . Somit sind (spezielle) Lösungen der Gleichung .
(2) Sei umgekehrt die Gleichung lösbar mit x und y aus und .
Der größte gemeinsame Teiler d ist auch Teiler von jeder Linearkombination von a und b, also auch von . Damit gilt .
Das eingangs angegebene Beispiel 3 führt zur diophantischen Gleichung . Da aber ist und 2 kein Teiler von 25 ist, ist die Aufgabe nicht lösbar.
Für die weiteren Betrachtungen sei vorausgesetzt, da jede lösbare diophantische Gleichung nach Division durch d darauf zurückzuführen ist.
Ist das Paar eine spezielle Lösung von , so erhält man daraus die Gesamtheit aller Lösungen wie folgt:
Geht man von der zugehörigen linearen Kongruenz aus, so ergibt sich daraus die folgende Restklassengleichung
Wegen der Voraussetzung existiert das inverse Element zur Restklasse
Die Klasse ist eine Lösung der Restklassengleichung und damit auch der linearen Kongruenz. Alle Elemente x dieser Klasse haben die Form
Den zugehörigen Wert y als allgemeine Lösung von erhält man durch Einsetzen:
ist die zu gehörende spezielle Lösung von , d.h. .
Lösungsmethoden
Jede lösbare diophantische Gleichung bzw. lineare Kongruenz besitzt eine unendliche Menge von Lösungspaaren. Zum Auffinden spezieller Lösungen gibt es verschiedene Methoden.
- Systematisches Probieren
Lösen durch systematisches Probieren bietet sich vor allem für den Fall an, dass die Zahlen a oder b „klein“ sind. Dann lassen sich in der linearen Kongruenz die Zahlen systematisch durch einen kleineren Repräsentanten ersetzen.
Wir betrachten dazu das oben gegebene Beispiel 1:
- Methode der korrespondierenden Kongruenzen
Die Methode der korrespondierenden Kongruenzen verwendet mehrfach die Umwandlung von diophantischen Gleichungen in lineare Kongruenzen und umgekehrt, wobei jedes Mal nach dem kleineren Modul reduziert wird.
Am Beispiel 2 soll das Verfahren demonstriert werden:
Obwohl die diophantische Gleichung lösbar ist, gibt es keine Lösung für die vorgegebene Problemstellung, da für jedes entweder x oder y negativ wird.
- Formale Bruchschreibweise
Beim Lösen mittels formaler Bruchschreibweise geht man von der linearen Kongruenz zu dem formalen Bruch über.Danach ersetzt man c oder a durch andere Repräsentanten , bis man durch Kürzen zu einem ganzzahligen Wert gelangt.
Oben gegebenes Beispiel 1 wird mit dieser Methode gelöst:
Wegen ist die Gleichung lösbar und führt zu folgender der gekürzter Gleichung:
Für y erhält man durch Einsetzen von in die diophantische Gleichung . Der Aufgabenstellung entsprechen die Werte
- Euklidischer Algorithmus
Eine weitere Möglichkeit, diophantische Gleichungen lösen, ist das Lösen mithilfe des euklidischen Algorithmus.
Man bestimmt die Linearkombination von und formt um, wie im nachfolgend wiederum am Beispiel 1 gezeigt wird:
Die Linearkombination des größten gemeinsamen Teilers 1 von 7 und 9 ergibt sich wie folgt:
Multipliziert mit 50, so erhält man Damit sind spezielle Lösungen.
Die allgemeine Lösung ist gegeben durch:
An diesem Beispiel erkennt man, dass beim euklidischen Algorithmus relativ große Zahlen als spezielle Lösungen auftreten können. Nur für erhält man mit eine Lösung, die der Aufgabenstellung genügt.
Weitere Lösungsverfahren gibt es unter Verwendung der eulerschen und mithilfe von Kettenbrüchen.