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?