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 <math>a_1x_1 + a_2x_2 + \dots + a_nx_n + c = 0</math> mit ganzzahligen Koeffizienten <math>a_1,..., a_n</math> und <math>c</math>, für die nur ganzzahlige Lösungen gesucht werden.<ref>{{#invoke:Vorlage:Literatur|f}}</ref> Linear bedeutet, dass die Variablen <math>x_1,...,x_n</math> nicht in Potenzen auftreten (im Gegensatz zur allgemeinen diophantischen Gleichung).

Auflösung von Gleichungen mit zwei Variablen

Die lineare diophantische Gleichung

<math> ax + by = c \qquad (*)</math>

mit vorgegebenen ganzen Zahlen <math>a,b,c</math> hat nach dem Lemma von Bézout genau dann ganzzahlige Lösungen in <math>x</math> und <math>y</math>, wenn <math>c</math> durch den größten gemeinsamen Teiler (<math>g</math>) von <math>a</math> und <math>b</math> teilbar ist. D.h. die linke Seite ist durch <math>g</math> teilbar, also muss auch <math>c</math> durch <math>g</math> 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

Sucht man also eine Lösung der ursprünglichen, inhomogenen Gleichung <math>(*)</math>, 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 <math>(*)</math>.

Geometrisch interpretiert sind <math> P:=(x,y)</math> Gitterpunkte mit ganzzahligen Koordinaten in der Euklidischen Ebene, die auf der durch <math>(*)</math> definierten Geraden liegen.

Lösungen der homogenen Gleichung

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

und da <math>a'</math> und <math>b'</math> teilerfremd sind, ist <math>x</math> durch <math>b'</math>, und <math>y</math> durch <math>a'</math> teilbar. Sämtliche Lösungen der homogenen Gleichung sind also durch

für eine beliebige ganze Zahl <math>t</math> gegeben.

Auffinden einer Partikularlösung

Mithilfe des erweiterten euklidischen Algorithmus kann man Zahlen <math>u,v</math> bestimmen, so dass

<math>au+bv=g</math> mit <math>g=\operatorname{ggT}(a,b)</math>

gilt. Setzt man <math>s=c/g,</math> so ist

eine Lösung der Gleichung <math>(*)</math>.

Gesamtheit der Lösungen

Die Gesamtheit der Lösungen von <math>(*)</math> ist gegeben durch

für beliebige ganze Zahlen <math>t</math>.

Explizite Lösung mittels Satz von Euler

Der Satz von Euler lautet

Aus <math>\mathrm{ggT}(a,b)= 1</math> folgt <math>a^{\varphi(b)} \equiv 1 \pmod b </math>.

Darin ist <math>\varphi(b)</math> die Eulersche Phi-Funktion, d. h. die Anzahl der zu <math>b</math> teilerfremden Restklassen.

Wir nehmen zur Vereinfachung an, dass der <math>\mathrm{ggT}</math> bereits herausdividiert ist und deshalb <math>\mathrm{ggT}(a,b)= 1</math> gilt.<ref>{{#invoke:Vorlage:Literatur|f}}</ref> Dann betrachtet man die Gleichung <math>(*)</math> modulo <math>b</math>, was <math>ax \equiv c \pmod b</math> ergibt. Der Satz von Euler liefert dann eine explizite Lösung <math>x</math>, nämlich

<math>x \equiv c a^{\varphi(b)-1} \pmod b</math>,

d. h. alle Zahlen der Form <math>x = c a^{\varphi(b)-1} + tb</math>.

Eingesetzt in die Ausgangsgleichung ergibt das

<math>y = c\frac {1- a^{\varphi(b)}} b - ta </math>,

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

Berechnungsbeispiel

Die Gleichung

soll gelöst werden.

Partikularlösung

Bei einfachen Zahlenbeispielen wie diesem lässt sich eine Partikularlösung leicht ablesen oder erraten, hier zum Beispiel <math>(x,y) = (0,10)</math>.

Der erweiterte euklidische Algorithmus liefert für die gegebene Gleichung

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

also die Partikularlösung <math>(x,y)=(100,-50).</math>

Lösungen der homogenen Gleichung

Es ist <math>a=6,b=10,g=2</math>, also <math>a'=3,b'=5</math>. Die homogene Gleichung

hat also die Lösungen <math>(x,y)=(5t,-3t)</math> für ganze Zahlen <math>t.</math>

Gesamtheit der Lösungen

Alle Lösungen ergeben sich also als

beispielsweise sind die Lösungen mit nichtnegativen <math>x</math> und <math>y</math>

<math>\begin{matrix}

t=-20:&(0,10)\\ t=-19:&(5,7)\ \ \\ t=-18:&(10,4)\\ t=-17:&(15,1) \end{matrix}</math>

Explizite Lösung mittels Satz von Euler

Nach Division durch den <math>\mathrm{ggT} = 2 </math> erhält man <math>a = 3, b = 5, c = 50</math>. Mit <math>\varphi(5) = 4</math> ergibt sich folglich

<math>x = 50\cdot 3^3 + 5t = 1350 + 5t</math> und

<math>y = 50\frac{1-3^4}5 -3t = -800 - 3t</math>.

Literatur

{{#invoke:Vorlage:Literatur|f}}

Weblinks

Einzelnachweise