Eine lineare diophantische Gleichung (benannt nach dem griechischen Mathematiker Diophantos von Alexandria, vermutlich um 250 n. Chr.) ist eine Gleichung der Form mit ganzzahligen Koeffizienten und , für die nur ganzzahlige Lösungen gesucht werden. Linear bedeutet, dass die Variablen nicht in Potenzen auftreten (im Gegensatz zur allgemeinen diophantischen Gleichung).
Auflösung von Gleichungen mit zwei Variablen Bearbeiten
Die lineare diophantische Gleichung
mit vorgegebenen ganzen Zahlen hat genau dann ganzzahlige Lösungen in und , wenn durch den größten gemeinsamen Teiler () von und teilbar ist. D.h. die linke Seite ist durch teilbar, also muss auch durch teilbar sein. Wir nehmen dies im Folgenden an.
Wie bei jeder linearen Gleichung ist die Differenz zweier Lösungen eine Lösung der zugehörigen homogenen Gleichung
Sucht man also eine Lösung der ursprünglichen, inhomogenen Gleichung , man spricht dann von einer "Partikularlösung", so erhält man durch Superposition mit den Lösungen der homogenen Gleichung sämtliche anderen Lösungen der inhomogenen Gleichung .
Geometrisch interpretiert sind Gitterpunkte mit ganzzahligen Koordinaten in der Euklidischen Ebene, die auf der durch definierten Geraden liegen.
Lösungen der homogenen Gleichung Bearbeiten
Schreibt man und mit , so ist die homogene Gleichung äquivalent zu
und da und teilerfremd sind, ist durch , und durch teilbar. Sämtliche Lösungen der homogenen Gleichung sind also durch
für eine beliebige ganze Zahl gegeben.
Auffinden einer Partikularlösung Bearbeiten
Mithilfe des erweiterten euklidischen Algorithmus kann man Zahlen bestimmen, so dass
gilt. Setzt man so ist
eine Lösung der Gleichung .
Gesamtheit der Lösungen Bearbeiten
Die Gesamtheit der Lösungen von ist gegeben durch
für beliebige ganze Zahlen .
Explizite Lösung mittels Satz von Euler Bearbeiten
Der Satz von Euler lautet
Darin ist die Eulersche Phi-Funktion, d. h. die Anzahl der zu teilerfremden Restklassen.
Wir nehmen zur Vereinfachung an, dass der bereits herausdividiert ist und deshalb gilt. Dann betrachtet man die Gleichung modulo , was ergibt. Der Satz von Euler liefert dann eine explizite Lösung , nämlich
d. h. alle Zahlen der Form .
Eingesetzt in die Ausgangsgleichung ergibt das
was nach dem Satz von Euler ebenfalls eine ganze Zahl ist.
Berechnungsbeispiel Bearbeiten
Die Gleichung
soll gelöst werden.
Partikularlösung Bearbeiten
Bei einfachen Zahlenbeispielen wie diesem lässt sich eine Partikularlösung leicht ablesen oder erraten, hier zum Beispiel .
Der erweiterte euklidische Algorithmus liefert für die gegebene Gleichung
Es folgt . Durch Multiplikation mit ergibt sich:
also die Partikularlösung
Lösungen der homogenen Gleichung Bearbeiten
Es ist , also . Die homogene Gleichung
hat also die Lösungen für ganze Zahlen
Gesamtheit der Lösungen Bearbeiten
Alle Lösungen ergeben sich also als
beispielsweise sind die Lösungen mit nichtnegativen und
Explizite Lösung mittels Satz von Euler Bearbeiten
Nach dem Dividieren durch den erhält man . Mit ergibt sich folglich
Literatur Bearbeiten
- Alexander Ossipowitsch Gelfond: Die Auflösung von Gleichungen in ganzen Zahlen (diophantische Gleichungen) (= Kleine Ergänzungsreihe zu den Hochschulbüchern für Mathematik. Band 5). Deutscher Verlag der Wissenschaften, Berlin 1973.
Weblinks Bearbeiten
Einzelnachweise Bearbeiten
- Ilja Nikolajewitsch Bronstein, Konstantin Adolfowitsch Semendjajew: Taschenbuch der Mathematik. 5. Auflage. Verlag Harri Deutsch, 2000, ISBN 3-8171-2005-2, S. 335.
- E. Krätzel: Zahlentheorie. VEB Deutscher Verlag der Wissenschaften, Berlin 1981, S. 24.