Wenn man in der Schule das erste Mal mit dem Bruchrechnen konfrontiert wird, kann das verwirrend sein. Es ist zum Beispiel nicht sofort intuitiv, warum Brüche mit unterschiedlichen Nennern nicht einfach addiert werden können. Und auch das Kürzen von Brüchen braucht Übung. Auf den ersten Blick zu erkennen, dass etwa der Bruch 252/105 auch viel einfacher als 12/5 dargestellt werden kann, kann schwierig sein. Wenn man aber weiß, was der »größte gemeinsame Teiler« ist, ist die Rechnung kein Problem mehr:

Hat man zwei ganze, positive Zahlen a und b, dann betrachtet man alle Zahlen, die a und b ohne Rest teilen, und die größte dieser Zahlen ist der größte gemeinsame Teiler d. Das Konzept ist nicht schwer zu verstehen – doch wie findet man den ggT? Dazu gibt es ein einfaches Rezept: Wenn b kleiner als a ist, dann subtrahiere b von a, und zwar so oft, bis das Ergebnis x der Subtraktion kleiner als b ist. Jetzt subtrahiere x von b, bis das Ergebnis y kleiner als x ist. Dann ziehe y von x ab, und so weiter, bis man irgendwann bei zwei genau gleich großen Zahlen landet. Das ist der größte gemeinsame Teiler. Im konkreten Fall von 252 und 105 müssen wir also 252 – 105 rechnen. Das Ergebnis ist 147 und immer noch größer als 105. Also rechnen wir noch einmal 147 – 105 = 42, und das ist jetzt kleiner als 105. Wir wechseln zur Subtraktion 105 – 42 = 63 und 63 – 42 = 21. Wir wechseln wieder und rechnen 42 – 21 = 21 und sind am Ziel: 21 ist der größte gemeinsame Teiler von 252 und 105, und damit können wir den Bruch leicht zu 12/5 vereinfachen.

Dieses Verfahren ist der »euklidische Algorithmus« und zirka 2300 Jahre alt. Der griechische Mathematiker Euklid hat es in §2 von Buch VII seines berühmten Werks »Elemente« geschrieben: »Es seien AB, CD die beiden gegebenen Zahlen, so dass die größere, AB, von der kleineren, CD, nicht genau gemessen werden. Nimm immer die kleinere von der größeren weg, bis ein Rest kommt, welcher die nächstvorgehende Zahl genau misst. Dieser Rest ist das größte gemeinschaftliche Maß der beiden gegebenen Zahlen.»

Dieses Verfahren ist der älteste uns bekannte Algorithmus und wird heute immer noch verwendet. Man hat ihn nur ein wenig modifiziert und die wiederholten Subtraktionen durch eine Division mit Rest ersetzt. Man teilt a durch b und das Ergebnis ist eine ganze Zahl q mit Rest r. Im nächsten Schritt wird die Zahl a durch b ersetzt und b durch den Rest r. Das wiederholt man so lange, bis ein Rest r = 0 bleibt, und die Zahl b, bei der das der Fall ist, ist der größte gemeinsame Teiler. Im Beispiel von 252 durch 105 erhalten wir das Ergebnis 2 und einen Rest von 42. 105 durch 42 ergibt 84 mit Rest 21 und 42 geteilt durch 21 geht ohne Rest auf.

Der euklidische Algorithmus basiert auf der Tatsache, dass jeder gemeinsame Teiler von a und b auch gleichzeitig ein Teiler der Differenz a – b sein muss. Und man muss auch nicht lange überlegen, um zu erkennen, dass man den euklidischen Algorithmus nicht nur zum Bruchrechnen verwenden kann. Die Sicherheit moderner Verschlüsselungsverfahren wie des RSA-Kryptosystems basieren auf »Schlüsseln«, die man erhält, wenn man zwei teilerfremde Zahlen multipliziert (deren ggT also gleich 1 ist). Der euklidische Algorithmus erlaubt eine schnelle Prüfung durch die Bestimmung des größten gemeinsamen Teilers – und ist dabei deutlich schneller als etwa eine Primfaktorenzerlegung.

An die Verschlüsselung von Daten hat Euklid damals mit Sicherheit nicht gedacht, als er seine »Elemente« niedergeschrieben hat. Ihm ging es um eine systematische Betrachtung von Geometrie und Zahlen. Aber man weiß nie, was die Zahlen offenbaren, wenn man nur intensiv genug über sie nachdenkt. Genau das macht die Mathematik so faszinierend.