Aufgepasst! Wir machen Folgendes als erstes. Ich bringe mal einen komplett neuen Begriff, den wir bislang noch nicht hatten und eure Überlegung wird übrigens später sein, warum oder fangen wir mal an. Ja, jetzt sind wir so weit, dass wir uns einen schönen Algorithmus anschauen können, mit dem man den größten gemeinsamen Teil der zweier Zahl bestimmen kann, nämlich den euklidischen Algorithmus.

Und zwar führe ich euch den mal vor, anhand der Zahlen 156 und 66, die hatten wir ja schon mal. Und eure Aufgabe wird später sein, neben dem Üben des Algorithmus natürlich, euch zu überlegen, warum funktioniert der denn. Okay, was machen wir als allererstes?

Wir machen die Vision mit Rest. Wir teilen den 156 durch 66 mit Rest. So, schreiben wir das mal folgendermaßen hier hin. 156 ist gleich, wie oft geht die 66 in die 156 rein? 2 mal, das ist 2 mal 66, plus, also 2 mal 66 ist 132, was bleibt dann übrig? 24, 24 ist der Rest.

So, jetzt macht man das Folgende. Man nimmt die 66 und schreibt sie hier hin und man nimmt die 24 und schreibt sie hier hin.

66 ist gleich, wie viel mal 24 plus Rest, also die Vision mit Rest, 66 durch 24. Wie oft geht die 24 in die 66?

Naja, die geht auch 2 mal rein, 2 mal 24 ist 48, und was bleibt als Rest? 18. So, und wieder 24 und 18 nehmen und wir teilen die 24 mit Rest durch die 18.

24 ist gleich 1 mal 18 plus 6, und wir nehmen wieder diese beiden hier, 18 und 6. 18 ist gleich 3 mal 6 plus 0. Hier unten ist die erste Stelle, bei der die Division aufgeht, wir haben keinen Rest.

So, und wenn das der Fall ist, dann kann man den GGT ablesen. Der steht nämlich, hier ist ein Mal, wer hat denn hier ein Plus hingeschrieben? Mensch, Gott sei Dank noch gesehen, mal, mal, 3 mal 6 plus 0, genau, der GGT steht hier oder hier.

Schön, der GGT von 156 und 66 ist 6, mit dem öklidischen Algorithmus rausgekriegt.

Ok, relativ knackig, relativ kurz kann man das machen. Es geht noch schöner und noch kürzer und noch schneller, man schreibt nämlich zu viel hier. Machen wir es mal folgendermaßen. Wir haben hier ja die Division mit Rest gemacht.

Wir haben also geschaut, wir haben zwei Zahlen, A und B, wie oft geht B in A rein und welcher Rest bleibt? A ist gleich Q mal B plus R, wir hatten A und B, das Q gesucht, sodass Q mal B A ergibt oder gerade noch kleiner ist und den Rest ermittelt.

Was man alles nicht aufschreiben muss eigentlich ist Q und das Gleichheitszeichen. Also eigentlich können wir eine schöne einfache Tabelle machen, A, B und R.

Am Anfang stehen hier die beiden Zahlen drin, deren GGT man ermitteln muss, 106, 5 und 66. Wir teilen A durch B mit Rest, 50 durch 66 ist 2, Rest 24. Sehen wir diese beiden Zahlen, schreiben sie hier hin, 66 ist gleich 2 mal 24 plus 18, die beiden Zahlen hier rübernehmen.

24 ist gleich 1 mal 18 plus 6, die beiden Zahlen hier rüber genommen, 18 ist gleich 3 mal 6 plus 0, fertig, das ist der GGT.