Du hast gerade ggT(385, 252) an die Tafel geschrieben. Zwei Schülerinnen in der dritten Reihe teilen alle Teiler von 385 auf, eine andere Gruppe macht dasselbe für 252 — und dann vergleichen alle. Das klappt, aber es dauert. Und spätestens bei ggT(1547, 1189) verliert jeder die Lust.
Genau hier kommt ein Verfahren ins Spiel, das Euklid um 300 v. Chr. in seinen „Elementen“ beschrieben hat: der euklidische Algorithmus. Es braucht keine vollständige Teilerauflistung, keine langen Primfaktorzerlegungen — nur immer wieder Division mit Rest. Das Ergebnis ist immer korrekt, der Prozess endet garantiert, und Schülerinnen und Schüler können das Verfahren nicht nur ausführen, sondern auch verstehen. Dieser Beitrag zeigt dir, wie du das im Unterricht gewinnbringend einsetzt.
Was steckt hinter dem Verfahren?
Die Grundidee des euklidischen Algorithmus ist so simpel, dass man sie in einem Satz beschreiben kann:
Teile die größere Zahl durch die kleinere, nimm den Rest — und wiederhole das Ganze, bis kein Rest mehr übrig bleibt. Der letzte Nicht-Null-Rest ist der ggT.
Am konkreten Beispiel sieht das so aus. Gesucht: .
Der letzte Nicht-Null-Rest ist , also gilt .
Was macht dieses Beispiel so wertvoll für den Unterricht? Schülerinnen und Schüler sehen unmittelbar: Die Reste werden streng kleiner — 133, 119, 14, 7, 0. Das Verfahren endet also zwingend nach endlich vielen Schritten. Diese Beobachtung ist der Einstieg in echtes algorithmisches Denken: Nicht „funktioniert das hier?“, sondern „warum funktioniert das immer?“ (vgl. Hromkovič, 2011).
Ein typischer Schülerfehler: die Division falsch aufstellen, also zum Beispiel 252=1⋅385+??? — was keinen sinnvollen Rest ergibt. Kurz darauf hinweisen, dass immer die größere durch die kleinere Zahl geteilt wird, reicht meistens aus.
Warum stimmt das Ergebnis immer?
Hier liegt das mathematische Herzstück — und es ist überraschend zugänglich. Die entscheidende Beobachtung: Wenn , dann hat jeder gemeinsame Teiler von und auch als Teiler. Und umgekehrt: Jeder gemeinsame Teiler von und ist auch ein gemeinsamer Teiler von .
Das bedeutet: . Die Menge der gemeinsamen Teiler ändert sich nicht, wenn wir das Paar durch ersetzen. Der Algorithmus rechnet also nicht irgendwas aus — er bewahrt die Information, die wir suchen, und verschiebt das Problem auf immer kleinere Zahlenpaare, bis das Ergebnis offensichtlich ist.
Für die Oberstufe lässt sich das als knapper Beweis formulieren. In der Sek I reicht die intuitive Erklärung: „Wer Teiler von und ist, muss auch teilen, denn .“ Das ist Mathematik, die verstanden werden kann — nicht nur ausgeführt.
So setzt du es konkret im Unterricht ein
Für den Unterricht eignet sich der euklidische Algorithmus auf mehreren Ebenen.
Einstieg (Sek I, ab Klasse 7): Lass Schülerinnen und Schüler das Verfahren zunächst an kleinen Beispielen ausprobieren — , . Das geht schnell und zeigt sofort, dass das Verfahren zuverlässig funktioniert. Anschließend können sie ihr Ergebnis mit der Primfaktorzerlegung überprüfen (→ thematisch verwandt mit dem Beitrag über ggT und kgV mit Primfaktoren).
Vertiefung (Sek II oder Differenzierung): Der Pseudocode ist ein ideales Bindeglied zwischen Mathematik und Informatik:
Eingabe: a, b mit a, b > 0
Solange b ≠ 0:
x ← b
b ← a mod b
a ← x
Ausgabe: a
Diese Schreibweise ist kurz, präzise und für viele Schülerinnen und Schüler überraschend elegant. Wer mag, kann das Verfahren anschließend in Python, Scratch oder einer anderen Sprache implementieren (vgl. Wing, 2006, zu Computational Thinking).
Materialvorschlag: Arbeitsblatt mit drei Aufgabenniveaus — geführt (Schritt-für-Schritt mit Lücken), selbstständig (Ergebnisse überprüfen) und vertiefend (Pseudocode aufschreiben und als Schleife beschreiben). Wer das Blatt auf Papier löst, übt Division mit Rest; wer den Pseudocode übersetzt, trainiert algorithmisches Denken. Beides auf demselben Blatt, ohne Umwege (→ Division mit Rest als Grundlage).
Effizienzvergleich als Aufgabe: Wie viele Schritte braucht das naive Verfahren (alle Teiler auflisten) bei ? Und wie viele braucht der euklidische Algorithmus? Diese Frage regt echte mathematische Neugier an und zeigt, warum Algorithmen in der Mathematik mehr sind als Rechenkochrezepte.
Zwei Jahrtausende Geschichte — und kein bisschen veraltet
Euklid beschrieb den Algorithmus um 300 v. Chr. in seinen „Elementen“ — damit ist er einer der ältesten bekannten Algorithmen der Menschheitsgeschichte, noch älter als das Wort „Algorithmus“ selbst (das leitet sich vom Namen des Mathematikers al-Chwarizmi aus dem 9. Jahrhundert ab). Dieser historische Kontext begeistert viele Schülerinnen und Schüler, denn er zeigt: Mathematik ist keine Erfindung von Schulbuchverlagen. Sie hat eine Geschichte, und diese Geschichte ist spannend.
Besonders wirkungsvoll: Der euklidische Algorithmus steckt heute noch in modernen Kryptosystemen — RSA nutzt ihn zum Beispiel für die Berechnung von modularen Inversen.
Der historische Kontext ist kein schmückendes Beiwerk — er ist ein didaktisches Werkzeug. Er macht Mathematik menschlich, situiert sie in Zeit und Raum und eröffnet den Schülerinnen und Schülern eine Perspektive jenseits des Schulstoffs.
Fazit
Der euklidische Algorithmus ist ein Juwel des Mathematikunterrichts: mathematisch elegant, didaktisch vielseitig und mit einer historischen Tiefe, die Schülerinnen und Schüler echte Neugier entwickeln lässt. Ob du ihn im ggT-Kontext der Sek I einsetzt, algorithmisches Denken in der Mittelstufe entwickelst oder den Brückenschlag zur Informatik wagst — er passt fast überall. Probier es aus und schreib mir in den Kommentaren, wie deine Klasse reagiert hat!
Quellen
Bruder, R., Hefendehl-Hebeker, L., Schmidt-Thieme, B., & Weigand, H.-G. (Hrsg.). (2015). Handbuch der Mathematikdidaktik. Springer Spektrum. https://doi.org/10.1007/978-3-642-35119-8
Hromkovič, J. (2011). Berechenbarkeit: Logik, Berechenbarkeit, Komplexität, Algorithmen, Automaten, Grammatiken. Vieweg+Teubner. https://doi.org/10.1007/978-3-8348-8237-9
Wing, J. M. (2006). Computational thinking. Communications of the ACM, 49(3), 33–35. https://doi.org/10.1145/1118178.1118215
