Worksheet

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche

Druckversion


Motivation

Wir haben neulich festgestellt, dass es sich mit Gleichungen folgender Form etwas seltsam verhält:

  1. 2\cdot x + 1\cdot y = 1: Diese Gleichung hat unendlich viele Lösungen, nämlich z.B.: ______________________________
  2. 6\cdot x + 9\cdot y = 18: Diese hat _____________________ Lösungen.
  3. 6\cdot x + 9\cdot y = 14: Diese hat _____________________ Lösungen.

Wann gibt es Lösungen für solche Gleichungen? Und wie findet man die?


Erweiterter Euklidischer Algorithmus

Wir beschäftigen uns zunächst mit speziellen diophantischen Gleichungen, und zwar wollen wir wissen, ob eine Lösung für die Gleichung a\cdot x + b\cdot y = ggT(a,b) existiert. Alternative Frage: Ist der ggT(a,b) immer als Linearkombination von a und b darstellbar?

Wir schauen erst einmal an einem konkreten Beispiel, was da zu machen ist. Wir berechnen den ggT(128,34) mit dem Euklidischen Algorithmus:











Der ggT(128,34) ist also 2. Wir wollen also nun versuchen, x und y zu finden derart, dass 2 = 128\cdot x + 34\cdot y.

Das gelingt durch Rückwärtsarbeiten. Schreibe die Rechnungen, mit denen man x und y findet:























Das klappt auf diese Weise natürlich immer. Betrachten wir das mal allgemein, und zwar zwei aufeinanderfolgende Schritte im Euklidischen Algorithmus:

  • ...
  • a_i = q_i\cdot b_i + r_i
  • a_{i+1} = q_{i+1}\cdot b_{i+1} + r_{i+1}
  • ...

Das Rückwärtsarbeiten wie oben hat uns folgende Gleichung beschert:

ggT(a,b) = x_{i+1}\cdot a_{i+1} + y_{i+1}\cdot b_{i+1}

Außerdem wissen wir, dass a_{i+1} = b_{i} ist, und dass b_{i+1} = r_i = a_i-q_i\cdot b_i

Einsetzen, umstellen und freuen: ggT(a,b) = x_{i+1}\cdot b_i + y_{i+1}\cdot (a_i-q_i\cdot b_i) = y_{i+1}\cdot a_i + (x_{i+1} - q_i\cdot y_{i+1})\cdot b_i

Also ergibt sich folgende Regel: x_i=y_{i+1} und y_i=x_{i+1} - q_i\cdot y_{i+1}.

Dies resultiert im erweiterten Euklidischen Algorithmus, der in Tabellenform einfach und schnell durchzuführen ist:

a b q r x y
128 34       
34 26 1 8 -3 1-1\cdot(-3)=4
26 8 3 2 1 0-3\cdot 1 = -3
8 2 4 0 0 1

Die allgemeine Umformung lässt deutlich werden: Das klappt immer. Insofern können wir aus diesem konstruktiven Beweis folgern:

Satz

Der ggT(a,b) kann als Linearkombination von a und b geschrieben werden. Die Gleichung a\cdot x + b\cdot y = ggT(a,b) ist also lösbar.


Lösbarkeit linearer diophantischer Gleichungen

Satz: Lineare diophantische Gleichungen der Form a\cdot x + b\cdot y = c mit a,b,c\in \mathbb{Z} sind genau dann lösbar, wenn ggT(a,b)|c.

Beweis:

1. Sei (x_0, y_0) eine Lösung der Gleichung. Dann gilt a\cdot x_0 + b\cdot y_0 = c. Sei d=ggT(a,b). Weil d die linke Seite der Gleichung teilt, muss d auch die rechte Seite der Gleichung teilen, also ggT(a,b)|c.

2. Es gelte ggT(a,b)|c, somit existiert ein z\in\mathbb{Z} mit c=z\cdot ggT(a,b). Wir wissen mittlerweile, dass es ein Paar (x_0, y_0) gibt mit a\cdot x_0 + b\cdot y_0 = ggT(a,b). Wir multiplizieren beide Seiten der Gleichung mit z, dann ergibt sich: a\cdot (z\cdot x_0) + b\cdot (z\cdot y_0) = z\cdot ggT(a,b). Also haben wir mit (z\cdot x_0, z\cdot y_0) eine Lösung gefunden.


Hieraus lässt sich direkt ableiten:

  • Der ggT(a,b) ist die kleinste natürliche Zahl, die als Linearkombination von a und b darstellbar ist.
  • Die diophantische Gleichung a\cdot x + b\cdot y = 1 ist genau dann lösbar, wenn a und b teilerfremd sind.
  • Damit gilt auch: Wenn a und b teilerfremd sind, dann ist jede ganze Zahl als Linearkombination von a und b darstellbar.

Lösungen linearer diophantischer Gleichungen

Wir wissen nun, wann eine lineare diophantische Gleichung lösbar ist, und wir können auch eine Lösung einfach über den erweiterten Euklidischen Algorithmus finden. Gibt es aber weitere Lösungen? Die Antwort lautet: Ja, und zwar unendlich viele. Wenn man eine Lösung (x_0, y_0) gefunden hat, dann findet man die gesamte Lösungsmenge mit: \{(x_0+\frac{z\cdot b}{ggT(a,b)}, y_0-\frac{z\cdot a}{ggT(a,b)})|z\in\mathbb{Z}\}.

Beweis: Sei z\in\mathbb{Z}. Dann ist (x_0+\frac{z\cdot b}{ggT(a,b)}, y_0-\frac{z\cdot a}{ggT(a,b)}) tatsächlich eine Lösung, denn: a\cdot (x_0+\frac{z\cdot b}{ggT(a,b)}) + b\cdot (y_0-\frac{z\cdot a}{ggT(a,b)}) = a\cdot x_0 + \frac{z\cdot a\cdot b}{ggT(a,b)} + b\cdot y_0 - \frac{z\cdot a\cdot b}{ggT(a,b)} = a\cdot x_0 + b\cdot y_0 = c

Es ist auch tatsächlich jede Lösung von dieser Form, wie folgende Überlegung zeigt:

Sei (x,y) eine weitere Lösung. Wir wissen also: a\cdot x + b\cdot y = c und a\cdot x_0 + b\cdot y_0 = c . Die Subtraktion der beiden Gleichungen liefert

a\cdot (x-x_0) + b\cdot (y-y_0) = 0

also

a\cdot (x-x_0) = b\cdot (y_0-y)

Wir können außerdem beide Seiten durch ggT(a,b) teilen:

\frac{a}{ggT(a,b)}\cdot (x-x_0) = \frac{b}{ggT(a,b)}\cdot (y_0-y)

Wir wissen, dass \frac{a}{ggT(a,b)} und \frac{b}{ggT(a,b)} teilerfremd sind, also muss gelten \frac{b}{ggT(a,b)}|(x-x_0), somit existiert ein z\in\mathbb{Z} mit (x-x_0)=z\cdot \frac{b}{ggT(a,b)}.In die Gleichung eingesetzt ergibt sich:

\frac{a}{ggT(a,b)}\cdot z\cdot \frac{b}{ggT(a,b)} = \frac{b}{ggT(a,b)}\cdot (y_0-y)

Somit ist (y_0-y)=z\cdot \frac{a}{ggT(a,b)}

Wenn man jeweils nach x und y umformt, ergibt sich gerade die oben genannte Form.

Beispiel

Wir wollen wissen, ob die Gleichung 168x+238y=126 lösbar ist, und wenn ja, für welche (x,y).

Wir müssen zunächst einmal den ggT(168,238) bestimmen und testen, ob dieser die Zahl 126 teilt (ansonsten könnten wir sofort aufhören).

Der erweiterte Euklidische Algorithmus ergibt:

a b q r x y
238 168 1 70 5 -7
168 70 2 28 -2 5
70 28 2 14 1 -2
28 14 2 0 0 1

Somit ist ggT(168,238)=14=168\cdot(-7)+238\cdot 5.

Außerdem gilt: 14|126, nämlich 126=14\cdot 9.

Wir müssen also die Gleichung mit 9 multiplizieren und erhalten:

126=168\cdot(-63)+238\cdot 45.

Allgemein sind die Lösungen: x=-63+\frac{z\cdot 238}{14}=-63+17z und y=45-\frac{z\cdot 168}{14}=45-12z

Fragen

Hast du noch Fragen? Notiere sie dir hier, damit du sie in deiner Lerngruppe, in der Übungsstunde oder in der nächsten Plenumssitzung klären kannst!