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

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=g{a}^{\prime }$ und $b=g{b}^{\prime }$ mit $g=\mathrm{ggT}(a,b)$, so ist die homogene Gleichung äquivalent zu

$a^{\prime }x=-b^{\prime }y,$

und da $a^{\prime }$ und $b^{\prime }$ teilerfremd sind, ist $x$ durch $b^{\prime }$, und $y$ durch $a^{\prime }$ teilbar. Sämtliche Lösungen der homogenen Gleichung sind also durch

$x=t{b}^{\prime },y=-t{a}^{\prime }$

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=\mathrm{ggT}(a,b)$

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

$x_0=su,y_0=sv$

eine Lösung der Gleichung $(*)$.

Gesamtheit der Lösungen

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

$x=x_0+t{b}^{\prime },y=y_0-t{a}^{\prime }$

für beliebige ganze Zahlen $t$.

Explizite Lösung mittels Satz von Euler

Der Satz von Euler lautet

Aus $\mathrm{g}\mathrm{g}\mathrm{T}(a,b)=1$ folgt $a^{\phi (b)}\equiv 1(\mathrm{mod}b)$.

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

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

$x\equiv c{a}^{\phi (b)-1}(\mathrm{mod}b)$,

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

Eingesetzt in die Ausgangsgleichung ergibt das

$y=c\frac{1-a^{\phi (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{array}{ccccc}10& =& 1\cdot 6& +& 4\\ 6& =& 1\cdot 4& +& 2& \text{(2 ist der ggT von 6 und 10)}\\ 4& =& 2\cdot 2& +& 0\end{array}$

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^{\prime }=3,b^{\prime }=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{array}{cc}t=-20:& (0,10)\\ t=-19:& (5,7)\\ t=-18:& (10,4)\\ t=-17:& (15,1)\end{array}$

Explizite Lösung mittels Satz von Euler

Nach Division durch den $\mathrm{g}\mathrm{g}\mathrm{T}=2$ erhält man $a=3,b=5,c=50$. Mit $\phi (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

• Vorlage:Literatur

Weblinks

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