Erweiterter Euklidische. Algorithmus?
Ich verstehe nicht wie ich diese Aufgabe lösen kann. Weder Tutorials noch ChatGPT waren in der Lage mich bei der Aufgabe so anzuleiten damit ich jeden schritt verstehen und reproduzieren kann.
Ich hoffe unter euch findet sich jemand der so hilfsbereit ist mir zu helfen.
Vielen Dank im Voraus
2 Antworten
Zuerst erkläre ich mal den euklidischen Algorithmus.
Mit dem euklidischen Algorithmus kannst du den größten gemeinsamen Teiler (kurz ggT) zweier natürlichen Zahlen a und b bestimmen. Der ggT ist die größte natürliche Zahl, die beide Zahlen a und b teilen kann.
Beispiele:
ggT(12, 6) = 6
ggT(100, 125) = 25
ggT(1, n) = 1
ggT(n, n) = n
ggT(12, 9) = 3
Für kleine Zahlen ist es einfach, den ggT direkt bzw. durch Primfaktorzerlegung anzugeben. Bei großen Zahlen wird es aber schwierig. Was ist zum Beispiel ggT(103872, 167376)? Hier kommt der euklidische Algorithmus zum Einsatz. Ich versuche mal anhand eines Beispiels zu erklären, wie er funktioniert.
Wir suchen ggT(120, 132). Zuerst schauen wir, wie oft die kleinere der beiden Zahlen in die größere "reinpasst".
132 / 120 = 1 Rest 12
Die 120 passt genau einmal in die 132 rein und übrig bleiben 12. Wenn wir nun wissen, wie oft die 12 in die 120 passt, dann wissen wir auch, wie oft sie in die 132 passt. Warum wollen wir das wissen? Naja, die 120 passt offensichtlich nicht in die 132, also ist 120 kein Teiler von 132. Wenn aber die 12 ein Teiler von 120 ist, dann ist 12 auch ein Teiler von 132. Also schauen wir, ob 12 passt.
120 / 12 = 10 Rest 0
Die 12 passt genau 10 mal in die 120. Also haben wir einen Teiler von 120 und damit auch einen von 132. Tatsächlich ist es auch der größte gemeinsame Teiler. Es gilt also
ggT(132, 120) = 12.
Hier noch ein weiteres Rechenbeispiel:
ggT(1204, 340) = ?
1204 / 340 = 3 Rest 184
340 / 184 = 1 Rest 156
184 / 156 = 1 Rest 28
156 / 28 = 5 Rest 16
28 / 16 = 1 Rest 12
16 / 12 = 1 Rest 4
12 / 4 = 3 Rest 0
=> ggT(1204, 340) = 4
Nun das, worum es eigentlich gehen soll: Der erweiterte euklidische Algorithmus.
Der erweiterte euklidische Algorithmus gibt ganze Zahlen x und y an, für die
ggT(a, b) = x • a + y • b.
Betrachten wir wieder die Zahlen a = 132 und b = 120. Dann gilt ja ggT(132, 120) = 12, denn
132 / 120 = 1 Rest 12,
120 / 12 = 10 Rest 0.
Formen wir das mal etwas um:
132 = 1 • 120 + 12
120 = 10 • 12 + 0
Wenn wir die erste Gleichung umformen, erhalten wir
1 • 132 – 1 • 120 = 12
also ist x = 1 und y = –1.
Nun zu unserem zweiten Rechenbeispiel. Zuerst stellen wir die Gleichungen wieder um:
1204 = 3 • 340 + 184
340 = 1 • 184 + 156
184 = 1 • 156 + 28
156 = 5 • 28 + 16
28 = 1• 16 + 12
16 = 1 • 12 + 4
12 = 3 • 4 + 0
Hier reicht es nicht nur die erste Gleichung umzuformen. Wir formen die vorletzte Gleichung um, da hier der ggT (=4) auftaucht.
4 = 16 – 1 • 12
Nun setzen wir die Gleichung darüber in diese Gleichung ein (diese formen wir nach dem, was bei der Division der Rest wäre, also 12, um: 28 – 1 • 16 = 12):
4 = 16 – 1 • (28 – 1 • 16)
4 = 2 • 16 – 1 • 28
Das selbe mit der Gleichung darüber usw. (156 – 5 • 28 = 16):
4 = 2 • (156 – 5 • 28) – 1 • 28
4 = 2 • 156 – 11 • 28
Nächste Gleichung (184 – 1 • 156 = 28):
4 = 2 • 156 – 11 • (184 – 1 • 156)
4 = 13 • 156 – 11 • 184
Nächste Gleichung (340 – 1 • 184 = 156):
4 = 13 • (340 – 1 • 184) – 11 • 184
4 = 13 • 340 – 24 • 184
Nächste Gleichung (1204 – 3 • 340 = 184):
4 = 13 • 340 – 24 • (1204 – 3 • 340)
4 = 85 • 340 – 24 • 1204
Und damit x = 85 und y = –24.
So haben wir eine Linearkombination von 340 und 1204 für den ggT von 4 bekommen.
Das können wir auf die Übungsaufgabe anwenden.
ggT(259, 38) = ?
259 / 38 = 6 Rest 31
38 / 31 = 1 Rest 7
31 / 7 = 4 Rest 3
7 / 3 = 2 Rest 1
3 / 1 = 3 Rest 0
=> ggT(259, 38) = 1
Also können wir mit dem erweiterten euklidischen Algorithmus tatsächlich eine Linearkombination für den ggT angeben.
Zuerst stellen wir die Gleichungen wieder um und setzen dann wieder rückwärts ein:
259 = 6 • 38 + 31
38 = 1 • 31 + 7
31 = 4 • 7 + 3
7 = 2 • 3 + 1
3 = 3 • 1 + 0
_____
1 = 7 – 2 • 3
1 = 7 – 2 • (31 – 4 • 7)
1 = 9 • 7 – 2 • 31
1 = 9 • (38 – 1 • 31) – 2 • 31
1 = 9 • 38 – 11 • 31
1 = 9 • 38 – 11 • (259 – 6 • 38)
1 = 75 • 38 – 11 • 259
Und damit s = –11 und t = 75.
Hier noch zwei Videos:
Hallo,
mit dem erweiteten eukl. Algorithmus berechnet man den größten gemeinsamen Teiler (ggT) zweier natürlicher Zahlen. Der ggT von 259 und 38 ist 1, d.h. sie sind teilerfremd, d.h. es existieren ganze Zahlen s und t, welche die Gleichung der Aufgabe erfüllen.
Schau dir mal hier die folgenden Rechenbeispiele an. Damit müsstest du es hinkriegen.
Gruß