Lineare Diophantische Gleichung

Eine lineare diophantische Gleichung ist eine diophantische Gleichung der Form
a1x1+a2x2+a3x3+…a_{1}x_{1} + a_{2}x_{2} + a_{3} x_{3} +\ldots +anxn+c=0 + a_{n}x_{n} + c = 0
mit ganzzahligen Koeffizienten aia_{i}, bei der man sich nur für ganzzahlige Lösungen interessiert. Linear bedeutet, dass die Variablen xix_{i} nicht in Potenzen auftreten. (Im Gegensatz zur allgemeinen diophantischen Gleichung.)

Auflösung von Gleichungen mit zwei Variablen

Die lineare diophantische Gleichung
ax+by=c ax + by = c (1)
mit vorgegebenen ganzen Zahlen a,b,ca,b,c hat genau dann ganzzahlige Lösungen in xx und yy, wenn cc durch den größten gemeinsamen Teiler gg von aa und bb teilbar ist. (Die linke Seite ist durch gg teilbar, also muss auch cc durch gg 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  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′a=ga' und b=gb′b=gb' mit g=ggT⁡(a,b)g=\ggT(a,b), so ist die homogene Gleichung äquivalent zu
a′x=−b′y,a'x = -b'y,
und da a′a' und b′b' teilerfremd sind, ist xx durch b′b' und yy durch a′a' teilbar. Sämtliche Lösungen der homogenen Gleichung sind also durch
x=tb′,y=−ta′x=tb',\quad y=-ta'
für eine beliebige ganze Zahl tt gegeben.

Auffinden einer Partikularlösung

Mithilfe des erweiterten euklidischen Algorithmus kann man Zahlen u,vu,v bestimmen, so dass
au+bv=gau+bv=g mit g=ggT⁡(a,b)g=\ggT(a,b)
gilt. Setzt man s=c/g,s=c/g, so ist
x0=su,y0=svx_0=su,\quad y_0=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′x=x_0+tb',\quad y=y_0-ta'
für beliebige ganze Zahlen tt.
 
 

Seit der Zeit der Griechen bedeutet "Mathematik" zu sagen, "Beweis" zu sagen.

N. Bourbaki

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Lineare Diophantische Gleichung aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Elementare Zahlentheorie