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}+a_{3}x_{3}+\dots +a_{n}x_{n}+c=0$ mit ganzzahligen Koeffizienten $a_{i}$ , bei der man sich nur für ganzzahlige Lösungen interessiert. Linear bedeutet, dass die Variablen $x_{i}$ 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.^[1] 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