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 ${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\dots +a_{n}x_{n}+c=0}$ mit ganzzahligen Koeffizienten ${\displaystyle a_{1},...,a_{n}}$ und ${\displaystyle c}$, für die nur ganzzahlige Lösungen gesucht werden.^[1] Linear bedeutet, dass die Variablen ${\displaystyle x_{1},...,x_{n}}$ nicht in Potenzen auftreten (im Gegensatz zur allgemeinen diophantischen Gleichung).

Die lineare diophantische Gleichung

${\displaystyle ax+by=c\qquad (*)}$

mit vorgegebenen ganzen Zahlen ${\displaystyle a,b,c}$ hat genau dann ganzzahlige Lösungen in ${\displaystyle x}$ und ${\displaystyle y}$, wenn ${\displaystyle c}$ durch den größten gemeinsamen Teiler (${\displaystyle g}$) von ${\displaystyle a}$ und ${\displaystyle b}$ teilbar ist. D.h. die linke Seite ist durch ${\displaystyle g}$ teilbar, also muss auch ${\displaystyle c}$ durch ${\displaystyle 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

${\displaystyle ax+by=0.\,}$

Sucht man also eine Lösung der ursprünglichen, inhomogenen Gleichung ${\displaystyle (*)}$, 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 ${\displaystyle (*)}$.

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

Schreibt man ${\displaystyle a=ga'}$ und ${\displaystyle b=gb'}$ mit ${\displaystyle g=\operatorname {ggT} (a,b)}$, so ist die homogene Gleichung äquivalent zu

${\displaystyle a'x=-b'y,}$

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

${\displaystyle x=tb',\quad y=-ta'}$

für eine beliebige ganze Zahl ${\displaystyle t}$ gegeben.

Mithilfe des erweiterten euklidischen Algorithmus kann man Zahlen ${\displaystyle u,v}$ bestimmen, so dass

${\displaystyle au+bv=g}$ mit ${\displaystyle g=\operatorname {ggT} (a,b)}$

gilt. Setzt man ${\displaystyle s=c/g,}$ so ist

${\displaystyle x_{0}=su,\quad y_{0}=sv}$

eine Lösung der Gleichung ${\displaystyle (*)}$.

Die Gesamtheit der Lösungen von ${\displaystyle (*)}$ ist gegeben durch

${\displaystyle x=x_{0}+tb',\quad y=y_{0}-ta'}$

für beliebige ganze Zahlen ${\displaystyle t}$.

Der Satz von Euler lautet

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

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

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

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

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

Eingesetzt in die Ausgangsgleichung ergibt das

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

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

Die Gleichung

${\displaystyle 6x+10y=100}$

soll gelöst werden.

Bei einfachen Zahlenbeispielen wie diesem lässt sich eine Partikularlösung leicht ablesen oder erraten, hier zum Beispiel ${\displaystyle (x,y)=(0,10)}$.

Der erweiterte euklidische Algorithmus liefert für die gegebene Gleichung

${\displaystyle {\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 ${\displaystyle 2=6-4=6-(10-6)=2\cdot 6+(-1)\cdot 10}$. Durch Multiplikation mit ${\displaystyle 100/2=50}$ ergibt sich:

${\displaystyle 100=100\cdot 6+(-50)\cdot 10,}$

also die Partikularlösung ${\displaystyle (x,y)=(100,-50).}$

Es ist ${\displaystyle a=6,b=10,g=2}$, also ${\displaystyle a'=3,b'=5}$. Die homogene Gleichung

${\displaystyle 6x+10y=0}$

hat also die Lösungen ${\displaystyle (x,y)=(5t,-3t)}$ für ganze Zahlen ${\displaystyle t.}$

Alle Lösungen ergeben sich also als

${\displaystyle (x,y)=(100+5t,-50-3t),}$

beispielsweise sind die Lösungen mit nichtnegativen ${\displaystyle x}$ und ${\displaystyle y}$

${\displaystyle {\begin{matrix}t=-20:&(0,10)\\t=-19:&(5,7)\ \ \\t=-18:&(10,4)\\t=-17:&(15,1)\end{matrix}}}$

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

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

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

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

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

1. ↑ Ilja Nikolajewitsch Bronstein, Konstantin Adolfowitsch Semendjajew: Taschenbuch der Mathematik. 5. Auflage. Verlag Harri Deutsch, 2000, ISBN 3-8171-2005-2, S. 335. 
2. ↑ E. Krätzel: Zahlentheorie. VEB Deutscher Verlag der Wissenschaften, Berlin 1981, S. 24.