ggT - euklidischen Algorithmus

Question

Aufgabe: Finden Sie x und y mit 102x + 86y = 2

ich dachte, ich habe verstanden wie man den euklidischen Algorithmus anwendet aber ich bin nun etwas verwirrt und habe Fragen.

Beispiel.:

102 = 1*86 + 16

86 = 5*16 +6

...

4 = 2*2 + 0

nun, wir beweisen mit der obigen Rechnung das für alle ggT das Ergebnis 2 gilt(?):

ggT(102,86) = ggT(86,16) = ... = ggT(4,2) = 2

...

weiter:

102 = 1*86 + 16 > 16 = 102 - 86
86 = 5*16 +6 > 6 = 86 - 5*16
...
6 = 1*4 + 2 > 2 = 6 - 4
4 = 2*2 + 0

meine Frage: wieso die Rechnung hinter dem Pfeil? Wollen wir damit etwas beweisen?

oder kann man so das Ergebnis berechnen?

...

weiter:

ggT(102,86)

2 = 6 - 4

   = 6 - (16-2*4)

   = 1*6 - 16 * 6 - 2 * 4

...

  = -17 * 86 + 5 * 102 - 5 * 86 - 2 * 4

  = -22 * 86 + 5 * 102 - 2 * 4

ich weiss, das man mit dieser Rechnung x und y herausfinden kann aber dann frage ich mich, für was braucht man die obige Rechnung? Wieso bis 0 rechnen, wenn man das Ergebnis nicht herausbekommt?

Vielen Dank schonmal!

Answer 1

Ersteinmal wäre es gut wenn du erwähnen würdest, dass die ganzzahligen Lösungen der diophantischen Gleichung gesucht sind.

Die eine fehlende Zeile vom euklidischen Algorithmus hättest du auch noch mit hinschreiben können:

$$\begin{aligned} 102&= 1\cdot 86 +16 &&\Leftrightarrow& 16 &= 102-1\cdot 86\\ 86&= 5\cdot 16+6 &&\Leftrightarrow& 6&= 86-5\cdot 16\\ 16&= 2\cdot 6 +4 &&\Leftrightarrow& 4&= 16-2\cdot 6\\ 6&= 1\cdot 4+2&&\Leftrightarrow& 2&= 6-1\cdot 4\\ 4&= 2\cdot 2 +0 \end{aligned}$$

Soweit sah es ja eigentlich ganz gut aus - du rechnest bist zum Rest 0 damit du weisst, dass der euklidische Algorithmus abgeschlossen ist und der Rest der vorherigen Zeile der ggT(102;86) ist.

Die Umformungen auf der rechten Seite macht man, damit jetzt rückwärts wieder eingesetzt werden kann.

Also in der letzten Zeile die vorletzte Zeile einsetzen und umformen, dann die vorvorletzte Zeile einsetzen usw.:

$$\begin{aligned} 2&= 6-1\cdot 4&&|\quad 4= 16-2\cdot 6\\ 2&= 6-1\cdot (16-2\cdot 6)\\ 2&= 6-1\cdot 16+2\cdot 6\\ 2&= -1\cdot 16+3\cdot 6&&|\quad 6= 86-5\cdot 16\\ 2&= -1\cdot 16+3\cdot (86-5\cdot 16)\\ 2&= -1\cdot 16+3\cdot 86-15\cdot 16\\ 2&= 3\cdot 86-16\cdot 16&&|\quad 16 = 102-1\cdot 86\\ 2&= 3\cdot 86-16\cdot (102-1\cdot 86)\\ 2&= 3\cdot 86-16\cdot 102+16\cdot 86\\ 2&= -16\cdot 102+19\cdot 86\\ \end{aligned}$$

Damit hat man eine Lösung gefunden: \(x_0=-16\) und \(y_0=19\).

Die Lösungsmenge ist dann:

$$\mathbb{L}=\left\{\left(-16+43z;19-51z\right)|z\in\mathbb{Z}\right\}$$

Answer 2

Zunächst führst du den Euklidischen Algorithmus durch

102 = 1·86 + 16
86 = 5·16 + 6
16 = 2·6 + 4
6 = 1·4 + 2
4 = 2·2 + 0

Sind dabei fragen ? Jeden Rest in einer Zeile kannst du auch als Subtraktion ausdrücken,

z.B. 16 = 2·6 + 4 → 4 = 16 - 2·6

Das brauchen wir jetzt für den Erweiterten Euklidischen Algorithmus für den wir in der Vorletzten Zeile beginnen

2 = 1·6 - 1·4
2 = 1·6 - 1·(16 - 2·6)
2 = - 1·16 + 3·6
2 = - 1·16 + 3·(86 - 5·16)
2 = 3·86 - 16·16
2 = 3·86 - 16·(102 - 1·86)
2 = - 16·102 + 19·86

Du siehst wir ersetzen immer nur den Rest durch den Ausdruck der darüberliegenden Zeile und vereinfachen den Ausdruck. Die letzte Zeile liefert und dann eine Lösung dieser Gleichung.

Ist das dann so klar ?