Lineare Diophantische Gleichung

aus Wikipedia, der freien Enzyklopädie

Eine lineare diophantische Gleichung (benannt nach dem griechischen Mathematiker Diophantos/Diophant von Alexandria, um 250 v. Chr.) ist eine Gleichung der Form a₁x₁ + a₂x₂ + a₃ x₃ + . . . + a_nx_n + c = 0 mit ganzzahligen Koeffizienten a_i, bei der man sich nur für ganzzahlige Lösungen interessiert. Linear bedeutet, dass die Variablen x_i nicht in Potenzen auftreten (Im Gegensatz zur allgemeinen diophantischen Gleichung).

Inhaltsverzeichnis 1 Auflösung von Gleichungen mit zwei Variablen 1.1 Lösungen der homogenen Gleichung 1.2 Auffinden einer Partikularlösung 1.3 Gesamtheit der Lösungen 2 Berechnungsbeispiel 2.1 Partikularlösung 2.2 Lösungen der homogenen Gleichung 2.3 Gesamtheit der Lösungen 3 Weblinks

[Bearbeiten] 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 ( * ) (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 ( * ).

[Bearbeiten] Lösungen der homogenen Gleichung

Schreibt man a = ga' und b = gb' mit , 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

für eine beliebige ganze Zahl t gegeben.

[Bearbeiten] Auffinden einer Partikularlösung

Mithilfe des erweiterten euklidischen Algorithmus kann man Zahlen u,v bestimmen, so dass

au + bv = g mit

gilt. Setzt man s = c / g, so ist

eine Lösung der Gleichung ( * ).

[Bearbeiten] Gesamtheit der Lösungen

Die Gesamtheit der Lösungen von ( * ) ist gegeben durch

für beliebige ganze Zahlen t.

[Bearbeiten] Berechnungsbeispiel

Die Gleichung

6x + 10y = 100

soll gelöst werden.

[Bearbeiten] Partikularlösung

Der erweiterte euklidische Algorithmus liefert

Aus der vorletzten Zeile ergibt sich durch Multiplikation mit 100 / 2 = 50:

Eine Partikularlösung ist also (x,y) = (100, − 50).

[Bearbeiten] Lösungen der homogenen Gleichung

Es ist a = 6,b = 10,g = 2, also a' = 3,b' = 5. Die homogene Gleichung

6x + 10y = 0

hat also die Lösungen (x,y) = (5t, − 3t) für ganze Zahlen t.

[Bearbeiten] Gesamtheit der Lösungen

Alle Lösungen ergeben sich also als

(x,y) = (100 + 5t, − 50 − 3t),

beispielsweise sind die Lösungen mit nichtnegativen x und y

[Bearbeiten] Weblinks

• Online-Tool zum Lösen von linearen diophantischen Gleichungen