Elementare Zahlentheorie
-
Kongruenzen
-
Diophantische Gleichungen
Lineare Gleichungen
Lineare Diophantische Gleichung
Eine lineare diophantische Gleichung ist eine diophantische Gleichung der Form
Auflösung von Gleichungen mit zwei Variablen
Die lineare diophantische Gleichung
mit vorgegebenen ganzen Zahlen a, b, c hat genau dann ganzzahlige Lösungen in x und y, wenn c durch den größten gemeinsamen Teiler g von a und b teilbar ist. (Die linke Seite ist durch g teilbar, also muss auch c durch g 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
Bestimmt man also eine Lösung der ursprünglichen, inhomogenen Gleichung (1) (man spricht dann von einer "Partikularlösung"), so erhält man durch Addition von Lösungen der homogenen Gleichung sämtliche anderen Lösungen der inhomogenen Gleichung (1).
Lösungen der homogenen Gleichung
Schreibt man a = ga' und b = gb' mit g = ggT(a, b), so ist die homogene Gleichung äquivalent zu
und da a' und b' teilerfremd sind, ist x durch b' und y durch a' teilbar. Sämtliche Lösungen der homogenen Gleichung sind also durch
für eine beliebige ganze Zahl t gegeben.
Auffinden einer Partikularlösung
Mithilfe des erweiterten euklidischen Algorithmus kann man Zahlen u, v bestimmen, so dass
gilt. Setzt man s = c/g, so ist
eine Lösung der Gleichung (1).
Gesamtheit der Lösungen
Die Gesamtheit der Lösungen von (1) ist gegeben durch
für beliebige ganze Zahlen t.
An Archimedes wird man sich erinnern, wenn Aischylos vergessen ist - weil zwar die Sprachen sterben, nicht aber die mathematischen Ideen.
Godfrey Harold Hardy
Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Lineare Diophantische Gleichung aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Lizеnz Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). Listе dеr Autorеn des Originalartikels. Achtung! Unter Umständen besitzt diese Seite kaum noch Ähnlichkeit mit dem genannten Wιkιpеdιa-Artikel, da dieser komplett überarbeitet werdet musste, um Fehler und irrelevante Informationen zu entfernen.