Lineare Diophantische Gleichung

Eine lineare diophantische Gleichung (benannt nach dem griechischen Mathematiker Diophantos/Diophant von Alexandria, um 250) 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
2 Berechnungsbeispiel
3 Weblinks

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 Addition von Lösungen der homogenen Gleichung sämtliche anderen Lösungen der inhomogenen Gleichung $( * )$ .

Lösungen der homogenen Gleichung

Schreibt man $a = g a'$ und $b = g b'$ 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

a u + b v = 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

$6 x + 10 y = 100$

soll gelöst werden.

Partikularlösung

Der erweiterte euklidische Algorithmus liefert

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