Lineare Diophantische Gleichung

Eine lineare diophantische Gleichung (benannt nach dem griechischen Mathematiker Diophant von Alexandrien, 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).

Auflösung von Gleichungen mit zwei Variablen

Die lineare diophantische Gleichung

$ax + by = c \qquad (*)$

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 ( * ) (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

Schreibt man a = ga' und b = gb' mit $g=\operatorname{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',\quad 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=\operatorname{ggT}(a,b)$

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

$x_0=su,\quad y_0=sv$

eine Lösung der Gleichung ( * ).

Gesamtheit der Lösungen

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

$x=x_0+tb',\quad y=y_0-ta'$

für beliebige ganze Zahlen t.

Berechnungsbeispiel

Die Gleichung

6x + 10y = 100

soll gelöst werden.

Partikularlösung

Bei einfachen Zahlenbeispielen wie diesem lässt sich eine Partikularlösung leicht ablesen oder erraten, hier zum Beispiel (x,y) = (0,10).

Der erweiterte euklidische Algorithmus liefert für die gegebene Gleichung

$\begin{matrix} 10 &=& 1\cdot 6 &+& 4 \\ 6 &=& 1\cdot 4 &+& 2 & \qquad\mbox{(2 ist der ggT von 6 und 10)}\\ 4 &=& 2\cdot 2 &+& 0 \\ \end{matrix}$

Es folgt $2 = 6 - 4 = 6 - (10-6) = 2 \cdot 6 + (-1)\cdot 10$. Durch Multiplikation mit 100 / 2 = 50 ergibt sich:

$100 = 100\cdot 6 + (-50)\cdot 10,$

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

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.

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

$\begin{matrix} t=-20:&(0,10)\\ t=-19:&(5,7)\\ t=-18:&(10,4)\\ t=-17:&(15,1). \end{matrix}$

Weblinks

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

• Facharbeit zu linearen diophantischen Gleichungen (PDF, 397 Kbyte)

• Beispiel: Ein Bauer …