Bestimme den größten gemeinsamen Teiler

Question

hallo allerseits,

kann  mir jemand erklären, wie ich folgende Aufgabe lösen kann?

Bestimme den größten gemeinsamen Teiler der Zahlen a := 245 und b := 28, sowie eine Darstellung ggT(a, b) = ka + rb mit k, r ∈ ℤ.

Answer 1

Verwende den erweiterten euklidischen Algorithmus.

Answer 2

Den größten gemeinsamen Teiler können wir mit Hilfe des euklidischen Algorithmus bestimmen ( https://de.wikipedia.org/wiki/Euklidischer_Algorithmus#Moderner_euklidischer_Algorithmus ).

Comments

Und wie bestimme ich die Darstellung ggT(a, b) = ka + rb mit k, r ∈ ℤ?

---

Dazu benutzen wir auch den euklidischen Algorithmus. Nachdem wir den größten gemeinsamen Teiler gefunden haben, lesen wir die Gleichungen rückwärts und stellen den Rest jeweils als Differenz der beiden anderen Terme da und setzten diese Restdarstellungen rekursiv ineinander ein. So ergeben sich verschiedene Darstellungen. 

Zum Beispiel: a=99 und b=78 

$$99=1\cdot 78+21 \\ 78=3\cdot 21+15 \\  21=1\cdot 15+6 \\ 15=2\cdot 6+3 \\ 6=2\cdot 3=0$$

Da 3 ein Teiler von 6 ist, haben wir dass ggT(99,78)=3.

Dann machen wir folgendes:

$$3=15-2\cdot 6 \\ = 15 - 2\cdot (21-1\cdot 15)=-2\cdot 21+3\cdot 15\\ =-2\cdot 21+3\cdot (78-3\cdot 21)=3\cdot 78-11\cdot 21 \\ = 3\cdot 78-11\cdot (99-1\cdot 78)=14\cdot 78-11\cdot 99$$

Wir haben also dass $$\text{ggT}(99, 78)=3=14\cdot 78-11\cdot 99$$