0 Daumen
200 Aufrufe

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 ∈ ℤ.


von

2 Antworten

0 Daumen
von 77 k 🚀
0 Daumen

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


von 6,9 k

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$$

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community