Logo

Mathepedia

Mathepedia auf Facebook

Wurzelzieher Blog

Elementare Zahlentheorie


Lineare Diophantische Gleichung

Eine lineare diophantische Gleichung ist eine diophantische Gleichung der Form
a1 x1 + a2 x2 + a3 x3 + ... + an xn + c = 0
mit ganzzahligen Koeffizienten ai , bei der man sich nur für ganzzahlige Lösungen interessiert. Linear bedeutet, dass die Variablen xi nicht in Potenzen auftreten. (Im Gegensatz zur allgemeinen diophantischen Gleichung.)

Auflösung von Gleichungen mit zwei Variablen

(1)
ax + by = c
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
ax + by = 0
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
a'x = - b'y,
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
x = tb', y = - ta'
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
au + bv = g mit g = ggT(a, b)
gilt. Setzt man s = c/g, so ist
x0 = su, y0 = sv
eine Lösung der Gleichung (1).

Gesamtheit der Lösungen

Die Gesamtheit der Lösungen von (1) ist gegeben durch
x = x0 + tb', y = y0 - ta'
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.



Anbieterkеnnzeichnung: Wurzelzieher Mathеpеdιa  •  Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
 
G: 24.01.2014 14:13:51 (549 ms; 251 M)
C: 24.04.2014 00:22:45 (111 ms; 150 M)