Lineare diophantische Gleichung

Eine lineare diophantische Gleichung (benannt nach dem griechischen Mathematiker Diophantos von Alexandria, vermutlich um 250 n. Chr.) ist eine Gleichung der Form $a_{1}x_{1}+a_{2}x_{2}+\dots +a_{n}x_{n}+c=0$ mit ganzzahligen Koeffizienten $a_{1},...,a_{n}$ und $c$, für die nur ganzzahlige Lösungen gesucht werden. Linear bedeutet, dass die Variablen $x_{1},...,x_{n}$ 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. D.h. 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.\,$

Sucht 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 $(*)$.

Geometrisch interpretiert sind $P:=(x,y)$ Gitterpunkte mit ganzzahligen Koordinaten in der Euklidischen Ebene, die auf der durch $(*)$ definierten Geraden liegen.

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

Explizite Lösung mittels Satz von Euler

Der Satz von Euler lautet

Aus $\mathrm {ggT} (a,b)=1$ folgt $a^{\varphi (b)}\equiv 1{\pmod {b}}$.

Darin ist $\varphi (b)$ die Eulersche Phi-Funktion, d. h. die Anzahl der zu $b$ teilerfremden Restklassen.

Wir nehmen zur Vereinfachung an, dass der $\mathrm {ggT}$ bereits herausdividiert ist und deshalb $\mathrm {ggT} (a,b)=1$ gilt. Dann betrachtet man die Gleichung $(*)$ modulo $b$, was $ax\equiv c{\pmod {b}}$ ergibt. Der Satz von Euler liefert dann eine explizite Lösung $x$, nämlich

$x\equiv ca^{\varphi (b)-1}{\pmod {b}}$,

d. h. alle Zahlen der Form $x=ca^{\varphi (b)-1}+tb$.

Eingesetzt in die Ausgangsgleichung ergibt das

$y=c{\frac {1-a^{\varphi (b)}}{b}}-ta$,

was nach dem Satz von Euler ebenfalls eine ganze Zahl ist.

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}}$

Explizite Lösung mittels Satz von Euler

Nach dem Dividieren durch den $\mathrm {ggT} =2$ erhält man $a=3,b=5,c=50$. Mit $\varphi (5)=4$ ergibt sich folglich

$x=50\cdot 3^{3}+5t=1350+5t$  und

$y=50{\frac {1-3^{4}}{5}}-3t=-800-3t$.

Literatur

• Alexander Ossipowitsch Gelfond: Die Auflösung von Gleichungen in ganzen Zahlen (diophantische Gleichungen) (= Kleine Ergänzungsreihe zu den Hochschulbüchern für Mathematik. Band 5). Deutscher Verlag der Wissenschaften, Berlin 1973. 

Weblinks

• Online-Tool zum Lösen von linearen diophantischen Gleichungen
• Beispiel: Ein Bauer …
• Lösen von Linearen Diophantischen Gleichungen mit erweitertem Euklidschem Algorithmus