Diophantische Gleichungen

Von Alltagsproblemen sind Aufgaben folgender Art bekannt:

• Beispiel 1: Für fünf Euro sollen zwei Sorten Kuchen zu $70ct$bzw. zu $90ct$ gekauft werden.
• Beispiel 2: Für zehn Euro sind Briefmarken zu $56ct$ und $51ct$ von der Post mitzubringen.
• Beispiel 3: Kann man für 25 Euro Socken zu vier Euro und zu sechs Euro kaufen?

In allen Fällen kommen nur natürliche Zahlen als Lösungen infrage (falls das Problem überhaupt lösbar ist). Ein Rest darf nicht auftreten. Es sind somit spezielle lineare Gleichungen zu lösen.

• Eine Gleichung der Form
  $ax+by=c\left(\ast \right)$
  mit ganzzahligen Koeffizienten a, b und c, für die ganze Zahlen x und y als Lösungen gesucht sind, heißt eine (lineare) diophantische Gleichung in zwei Unbekannten.

Anmerkung: Entsprechend heißen Gleichungen der Form $a_1{x}_1+a_2{x}_2+\mathrm{...}+a_n{x}_n=c$ diophantische Gleichungen mit n Unbekannten.

Die diophantische Gleichung $(\ast )$ lässt sich auch als lineare Kongruenz schreiben, denn aus $ax=c-by=c+bg$ ergibt sich mit $g=-y$:
$ax\equiv c\mathrm{mod}b\left(\ast \ast \right)$

Wir beweisen den folgenden Satz:

• Die diophantische Gleichung $(\ast )$ bzw. die lineare Kongruenz $\left(\ast \ast \right)$ ist genau dann lösbar, wenn der größte gemeinsame Teiler von a und b auch ein Teiler von c ist, wenn also gilt: $ggT\left(a,b\right)=d\left(mitd|c\right)$

Beweis:
(1) $d=ggT\left(a,b\right)$ sei Teiler von c.
Der größte gemeinsame Teiler von a und b lässt sich stets als Linearkombination von a und b mit ganzen Zahlen u und v schreiben:
$d=ua+vb$
Die Voraussetzung $d|c$ bedeutet, dass es eine ganze Zahl w gibt, mit $c=dw$. Multipliziert man obige Gleichung mit w, erhält man $c=dw=\left(wu\right)a+\left(wv\right)b.$. Somit sind $x_0=wuund{y}_0=wv$(spezielle) Lösungen der Gleichung $(\ast )$.

(2) Sei umgekehrt die Gleichung $(\ast )$ lösbar mit x und y aus $\mathbb{Z}$ und $d=ggT\left(a,b\right)$.
Der größte gemeinsame Teiler d ist auch Teiler von jeder Linearkombination von a und b, also auch von $ax+by=c$. Damit gilt $d|c$.

Das eingangs angegebene Beispiel 3 führt zur diophantischen Gleichung $4x+6y=25$. Da aber $ggT\left(\mathrm{4,}6\right)=2$ ist und 2 kein Teiler von 25 ist, ist die Aufgabe nicht lösbar.

Für die weiteren Betrachtungen sei $ggT\left(a,b\right)=1$ vorausgesetzt, da jede lösbare diophantische Gleichung nach Division durch d darauf zurückzuführen ist.
Ist das Paar $\left(x_0;y_0\right)$ eine spezielle Lösung von $(\ast )$, so erhält man daraus die Gesamtheit aller Lösungen wie folgt:
$\begin{array}{c}x=x_0+gb\\ y=y_0-ga\left(g\in \mathbb{Z}\right)\end{array}$

Geht man von der zugehörigen linearen Kongruenz $\left(\ast \ast \right)$ aus, so ergibt sich daraus die folgende Restklassengleichung $\mathrm{mod}b\text{:}$
$\left[a\right]\cdot \left[x\right]=\left[c\right]bzw.\left[x\right]={\left[a\right]}^{-1}\cdot \left[c\right]$

Wegen der Voraussetzung $ggT\left(a,b\right)=1$ existiert das inverse Element zur Restklasse $\mathrm{mod}b.$

Die Klasse $\left[x_0\right]={\left[a\right]}^{-1}\cdot \left[c\right]$ ist eine Lösung der Restklassengleichung und damit auch der linearen Kongruenz. Alle Elemente x dieser Klasse haben die Form $x=x_0+gb\left(mitg\in \mathbb{Z}\right).$

Den zugehörigen Wert y als allgemeine Lösung von $(\ast )$ erhält man durch Einsetzen:
$\begin{array}{c}c=ax+by=a\left(x_0+gb\right)+by=a{x}_0+agb+by\\ by=c-a{x}_0-agb\\ \Rightarrow y=\frac{c-a{x}_0}{b}-ag\end{array}$
$\frac{c-a{x}_0}{b}$ ist die zu $x_0$ gehörende spezielle Lösung $y_0$ von $(\ast )$, d.h. $y=y_0-agmitg\in \mathbb{Z}$.

Lösungsmethoden

Jede lösbare diophantische Gleichung $(\ast )$ bzw. lineare Kongruenz $\left(\ast \ast \right)$ besitzt eine unendliche Menge von Lösungspaaren. Zum Auffinden spezieller Lösungen gibt es verschiedene Methoden.

1. Systematisches Probieren

Lösen durch systematisches Probieren bietet sich vor allem für den Fall an, dass die Zahlen a oder b „klein“ sind. Dann lassen sich in der linearen Kongruenz die Zahlen systematisch durch einen kleineren Repräsentanten ersetzen.

Wir betrachten dazu das oben gegebene Beispiel 1:

$\begin{array}{lll}9x+62y=8\hfill & 62y\equiv 8\mathrm{mod}9\hfill & bzw.\hfill \\ \hfill & 8y\equiv 8\mathrm{mod}9\hfill & also{y}_0=1\hfill \\ \begin{array}{l}9x+62=8\\ Al\lg emeineLösung:\\ \end{array}\hfill & \begin{array}{c}{x}_0=-6\\ x=-6+62g\\ y=1-9g\end{array}\hfill & \hfill \end{array}$

2. Methode der korrespondierenden Kongruenzen

Die Methode der korrespondierenden Kongruenzen verwendet mehrfach die Umwandlung von diophantischen Gleichungen in lineare Kongruenzen und umgekehrt, wobei jedes Mal nach dem kleineren Modul reduziert wird.

Am Beispiel 2 soll das Verfahren demonstriert werden:

$\begin{array}{ll}\begin{array}{c}51x+56y=1000\\ 56y\equiv 1000\mathrm{mod}51\\ 56y-51y\equiv \left(1000-19\cdot 51\right)\mathrm{mod}51\\ 5y\equiv 31\mathrm{mod}51\\ \end{array}\hfill & \begin{array}{c}5y+51z=31\\ 51z\equiv 31\mathrm{mod}5\\ 51z-50z\equiv \left(31-6\cdot 5\right)\mathrm{mod}5\\ z\equiv 1\mathrm{mod}5\\ z=1+5g\end{array}\hfill \\ \begin{array}{l}\\ 5y+51\cdot \left(1+5g\right)=31\\ 5y=-20-255g\\ y=-4-51g\end{array}\hfill & \begin{array}{c}\\ 51x+56\cdot \left(-4-51g\right)=1000\\ 51x=1224+51\cdot 56g\\ x=24+56g\end{array}\hfill \end{array}$

Obwohl die diophantische Gleichung lösbar ist, gibt es keine Lösung für die vorgegebene Problemstellung, da für jedes $g\in \mathbb{Z}$ entweder x oder y negativ wird.

3. Formale Bruchschreibweise

Beim Lösen mittels formaler Bruchschreibweise geht man von der linearen Kongruenz $ax\equiv c\mathrm{mod}b$ zu dem formalen Bruch $x\equiv \frac{c}{a}\mathrm{mod}b$ über.Danach ersetzt man c oder a durch andere Repräsentanten $\mathrm{mod}b$, bis man durch Kürzen zu einem ganzzahligen Wert gelangt.

Oben gegebenes Beispiel 1 wird mit dieser Methode gelöst:

$70x+90y=500$
Wegen $ggT\left(\mathrm{70,}90\right)=10und10|500$ ist die Gleichung lösbar und führt zu folgender der gekürzter Gleichung:
$\begin{array}{ll}\begin{array}{c}7x+9y=50\\ x\equiv \frac{50}{7}\mathrm{mod}950\equiv 5\mathrm{mod}9\\ x\equiv \frac{5}{7}\mathrm{mod}97\equiv 25\mathrm{mod}9\\ x\equiv \frac{5}{25}=\frac{1}{5}\mathrm{mod}91\equiv 10\mathrm{mod}9\\ x\equiv \frac{10}{5}=2\mathrm{mod}9\end{array}\hfill & \begin{array}{l}\\ \\ \end{array}\hfill \end{array}$
Für y erhält man durch Einsetzen von $x=2+9g$ in die diophantische Gleichung $y=4-7g$. Der Aufgabenstellung entsprechen die Werte $x=2undy=4.$

4. Euklidischer Algorithmus

Eine weitere Möglichkeit, diophantische Gleichungen lösen, ist das Lösen mithilfe des euklidischen Algorithmus.

Man bestimmt die Linearkombination von $1=ggT\left(a;b\right)$ und formt um, wie im nachfolgend wiederum am Beispiel 1 gezeigt wird:
$7x+9y=50$
Die Linearkombination des größten gemeinsamen Teilers 1 von 7 und 9 ergibt sich wie folgt:

$\begin{array}{c}9=1\cdot 7+2und7=3\cdot 2+1\\ \Rightarrow 1=7-3\cdot 2=7-3\cdot \left(9-7\right)=4\cdot 7-3\cdot 9\end{array}$
Multipliziert mit 50, so erhält man $50=200\cdot 7-150\cdot 9.$ Damit sind $x_0=200und{y}_0=-150$ spezielle Lösungen.
Die allgemeine Lösung ist gegeben durch:
$\begin{array}{c}x=200+9g\\ y=-150-7g\end{array}$
An diesem Beispiel erkennt man, dass beim euklidischen Algorithmus relativ große Zahlen als spezielle Lösungen auftreten können. Nur für $g=22$ erhält man mit $x=2undy=4$ eine Lösung, die der Aufgabenstellung genügt.

Weitere Lösungsverfahren gibt es unter Verwendung der eulerschen $\varphi \text{-}Funktion$ und mithilfe von Kettenbrüchen.