Berechnen Sie g: ggT(1111,333) und stellen Sie g als Linearkombination von 1111 und 333 dar.

Question

Aufgabe: Berechnen Sie g: ggT(1111,333) und stellen Sie g als Linearkombination von 1111 und 333 dar.

Problem/Ansatz:

1111 = 3 * 333 + 112

333 = 2 * 112 + 109

112 = 1 * 109 + 3

109 = 36 * 3 + 1

3 = 3 * 1 + 0

Also gilt. ggT(1111,333) = 1.

1111 und 333 als Linearkombination darstellen:

1 = 109 - 36 * 3

= 109 - 36 * (112- 109)

= 109 - -36 * (109 - 112)

= 37 * 109 - 36 * 112

= 37 * (333 - 2 * 112)  - 36 * 112

= 37 * 333 - 100 * 112.

Ist das so richtig?

Answer 1

Der ggT stimmt, aber bei der Linearkombination müsste aber doch 1 rauskommen.

= 109 - 36 * (112- 109)  ✓

= 109 +36 * (109 - 112) ✓

= 37 * 109 - 36 * 112  ✓

= 37 * (333 - 2 * 112)  - 36 * 112 ✓

= 37 * 333 - 110 * 112      !!!

= 37 * 333 - 110 * (1111-3*333)

=367*333-110*1111

Comments

Weißt du, in welchem Schritt mein Fehler ist?

Ich muss mich bei der Linearkombination doch nach der Reihenfolge von unten nach oben arbeiten und immer die Zahlen ersetzen, oder?

---

Du hattest dich einmal verrechnet. Habs korrigiert !

Answer 2

Hallo,

die letzte Zeile ist falsch.

So geht es weiter:

37 * (333 - 2 * 112) - 36 * 112

=37•333-110•112

=37•333-110•(1111-3•333)

=37•333-110•1111+330•333

=367•333-110•1111=1

:-)