Euklidischer Algorithmus

Der größte gemeinsame Teiler (kurz: ggT) zweier natürlicher Zahlen $a$ und $b$ ist die größte natürliche Zahl, die sowohl $a$ als auch $b$ teilt. Der ggT ist z.B. beim Kürzen von Brüchen $a/b$ wichtig, da dies die größte Zahl ist, durch die man Zähler und Nenner kürzen kann. Man kann den ggT zweier Zahlen für kleine Zahlen oft relativ schnell erraten, für größere Zahlen ist jedoch ein algorithmisches Vorgehen notwendig. Wir bezeichnen den ggT von $a$ und $b$ kurz mit $\mbox{ggT}(a,b)$. Ein sehr effizienter Algorithmus zur Berechnung des ggT ist der so genannte _Euklidische Algorithmus_. Hierbei wird durch sukzessives Abspalten von Resten iterativ der ggT bestimmt. Es gelte o.B.d.A $a\geq b$. Die Hauptidee des Algorithmus ist die folgende:

Entweder geht $b$ ohne Rest in $a$ auf, dann ist $b$ der gesuchte $\mbox{ggT}(a,b)$.
Andernfalls gilt $a=k\cdot b+r$ für ein $r

Aus dieser Erkenntnis lässt sich wahlweise ein iterativer oder ein rekursiver Algorithmus aufbauen. Rekursiv läßt sich eine ggT Funktion z.B. folgendermaßen definieren:


   ggT(a,b):= {
      r=mod(a,b);                //Der Rest von a beim Teilen durch b;
      if (r==0)
         return b;               //Wir haben den ggT gefunden
      else
         return ggT(b,r);        //Wir müssen iterieren
   }

Das folgende Applet verdeutlicht (rechte Seite) tabellarisch die Berechnung des ggT. Die Zahlen $a$ und $b$ lassen sich mit der Maus einstellen.

Die Grafik auf der linken Seite gibt eine geometrische Interpretation des Euklidischen Algorithmus an. Ausgehend von einem Rechteck mit Kantenlängen $a$ und $b$ beginnt man, an der kürzeren Seite (angenommen dies sei $b$) Quadrate der Größe $b\cdot b$ abzuspalten. Entweder geht dieser Prozess auf oder es verbleibt ein Rechteck, dessen längere Kante die Länge $b$ hat. Mit diesem Rechteck verfährt man iterativ so weiter. Sofern $a$ und $b$ ganze Zahlen sind, stoppt dieser iterative Prozess spätestens bei einem $1\cdot 1$ Quadrat. Die Kantenlänge des letzten Quadrates ist der gesuchte ggT.

Man kann den Prozess des Auffindens des ggT auch komplett geometrisch interpretieren. Gegeben seien zwei Längen $a$ und $b$. Gesucht ist ein größtmöglicher Maßstab mit Länge $l$, so dass ich sowohl $a$ als auch $b$ durch Hintereinanderlegen von Maßstäben der Länge $l$ exakt vermessen lassen. Es soll also gelten $a=s\cdot l$ und $b=t\cdot l$ für geeignete ganze Zahlen $s$ und $t$. Strecken, für die dieses möglich ist, nennt man kommensurabel. Strecken, für die dieses nicht möglich ist, nennt man inkommensurabel. Das Verhältnis von $a$ zu $b$ ist in diesem Fall irrational.

Eine kleine Fingerübung:
Es sei $\tau$ der Goldene Schnitt, also (per Definition) ein Zahlenverhältnis $a/b$ mit der Eigenschaft, dass ${a\over b}= {a+b\over a}$ gilt. (In Prosa: Die Strecke $a+b$ wird so unterteilt, dass das Verhältnis ihrer Gesamtlänge zur größeren Teilstrecke $a$ gleich dem Verhältnis der größeren zur kleineren Teilstrecke ist.) Man Zeige (ohne Rechnen!!), dass der Goldene Schnitt irrational ist.