Lineare diophantische Gleichung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Eine lineare diophantische Gleichung (benannt nach dem griechischen Mathematiker Diophantos von Alexandria, vermutlich um 250 n. Chr.) ist eine Gleichung der Form a1x1 + a2x2 + a3 x3 + . . . + anxn + 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[Bearbeiten | Quelltext 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. (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

Bestimmt 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 .

Lösungen der homogenen Gleichung[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

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

mit

gilt. Setzt man so ist

eine Lösung der Gleichung .

Gesamtheit der Lösungen[Bearbeiten | Quelltext bearbeiten]

Die Gesamtheit der Lösungen von ist gegeben durch

für beliebige ganze Zahlen .

Berechnungsbeispiel[Bearbeiten | Quelltext bearbeiten]

Die Gleichung

soll gelöst werden.

Partikularlösung[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

Es ist , also . Die homogene Gleichung

hat also die Lösungen für ganze Zahlen

Gesamtheit der Lösungen[Bearbeiten | Quelltext bearbeiten]

Alle Lösungen ergeben sich also als

beispielsweise sind die Lösungen mit nichtnegativen und

Weblinks[Bearbeiten | Quelltext bearbeiten]