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}+a_{3}x_{3}+\dots +a_{n}x_{n}+c=0}$ mit ganzzahligen Koeffizienten ${\displaystyle a_{i}}$, bei der man sich nur für ganzzahlige Lösungen interessiert. Linear bedeutet, dass die Variablen ${\displaystyle x_{i}}$ nicht in Potenzen auftreten (Im Gegensatz zur allgemeinen diophantischen Gleichung).

Auflösung von Gleichungen mit zwei Variablen

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.

Lösungen der homogenen Gleichung

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.

Auffinden einer Partikularlösung

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

Gesamtheit der Lösungen

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

Explizite Lösung mittels Satz von Euler

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

Berechnungsbeispiel

Die Gleichung

${\displaystyle 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 ${\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).}$

Lösungen der homogenen Gleichung

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

Gesamtheit der Lösungen

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

Explizite Lösung mittels Satz von Euler

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

Weblinks

• Facharbeit zu linearen diophantischen Gleichungen (PDF; 397 kB)
• Beispiel: Ein Bauer …
• Online-Tool zum Lösen von linearen diophantischen Gleichungen

Einzelnachweise

1. ↑ E. Krätzel: Zahlentheorie. VEB Deutscher Verlag der Wissenschaften, Berlin 1981, S. 24.