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.^[1] 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.^[2] 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).$