Algorithmen zur ggT-Berechnung

Die Qual der Wahl!

Zur Bestimmung des größten gemeinsamen Teilers gibt es unterschiedliche Verfahren.

Beim Wechselwegnahme-Algorithmus wird stets die kleinere von der größeren Zahl abgezogen:

Beim klassischen Euklidischen Algorithmus wird mit der Anweisung r = x % y wiederholt der Rest bei der ganzzahligen Division von x durch y bestimmt. Dieser Rest wird dann bei der weiteren Berechnung benutzt.

Aufgabe 1

(a) Bestimme mit beiden Algorithmen den größten gemeinsamen Teiler von a = 44 und b = 8.

(b) Der größte gemeinsame Teiler von a = 3642431875 und b = 15 soll mit einem der beiden Algorithmen bestimmt werden. Für welchen sollte man sich entscheiden? Begründe deine Entscheidung.

Aufgabe 2

Begründe: Der Euklidische Algorithmus benutzt dieselbe Strategie zur ggT-Berechnung wie der Wechselwegnahme-Algorithmus. Er macht das nur effizienter.