Der Euklidische Algorithmus
- Theorem
- Seien mit . Dann existieren eindeutige Zahlen mit , so dass gilt
- Die ganze Zahl heißt der Quotient und der Rest.
Z.B. für die Zahlen gilt
wobei und ist.
- Theorem
- Seien mit . Dann ist
Dieser Satz ist die Grundlage des Euklidischen Algorithmus.
Euklidischer Algorithmus
Der Euklidische Algorithmus ist einer der ältesten und berühmtesten Algorithmen
überhaupt. Er dient zur Bestimmung des größten gemeinsamen Teilers zweier positiver
ganzer Zahlen und mit .
Der Algorithmus funktioniert wie folgt:
- Man dividiert durch und erhält einen Rest
- Ist , ist .
- Ist , wird der Wert von zugewiesen und der Wert von . Man wiederhole dann den Zyklus ab Schritt 1 bis der Rest ist. Der entsprechende Wert von ist dann der gesuchte .
Man setzt . Dann ist
wobei . Die Reste bilden eine Reihe von abnehmenden natürlichen Zahlen
und so erhält man irgendwann einen Nullwert . Der gesuchte ist .
Der Algorithmus funktioniert, da wegen des obigen Satzes
ist.
- Beispiel
Bestimmung von :
Der letzte Rest, der nicht ist, ist . Also ist . Es gilt
Kettenbrüche
Schreibt man die Zeilen des obigen Beispiels in der Form
führt das zu einer ungewohnten Art der Darstellung eines Bruches:
Also ist
Die rechte Seite der Gleichung ist ein sogenannter Kettenbruch, d.h. ein Bruch, dessen
Nenner immer ein weiterer Bruch ist. Bei einer rationalen Zahl wie hier bricht die
Kettenbruchentwicklung ab.
In Form von den Quotienten im Euklidischen Algorithmus ist die Kettenbruchentwicklung des Bruches gegeben durch