# 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 nach dem Lemma von Bézout 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 Division 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$.