Bezout Koeffizienten nicht mit Euklidischem Algorithmus berechnen.

Question

Aufgabe:

Zeige zwei Lösungen für die Bezout Koeffizienten.

Problem/Ansatz:

Da ggT(a; b) = s*a + t*b , also eine Gleichung mit zwei Unbekannten, kann es mehr als eine Lösung geben.

Zum einen kann man s und t mit dem Euklidischen Algorithmus berechnen.

Wie aber kommt man zu einer weiteren Lösung?

Answer 1

Zeige zwei Lösungen für die Bezout Koeffizienten.

Ist das die gesamte Aufgabe? Keine Zahlenwerte gegeben?

Wie aber kommt man zu einer weiteren Lösung?

Nehmen wir mal an du hast ein s und ein t, sodass die Gleichung gilt:

s·a + t·b = ggT(a; b)

Dann gilt auch:

s·a + k·a·b + t·b - k·a·b = ggT(a; b)

(s + k·b)·a + (t - k·a)·b = ggT(a; b)

Du siehst dass die Gleichung dann auch für s + k·b und t - k·a gelten muss. Für k könntest du jede ganze Zahl einsetzen.

Z.B.

2·7 + (-1)·13 = 1

15·7 + (-8)·13 = 1

28·7 + (-15)·13 = 1

...