Der Euklidische Algorithmus ist sehr hilfreich zur Bestimmung des größten gemeinsamen Teilers (ggT).
Allgemeine mathematische Schreibweise
Das ganze noch in einer allgemeinen mathematischen Schreibweise:
Man nehme an, dass größer als ist:
Rechnung | Beschreibung |
|---|---|
und sind dabei Zahlen, die aus der Rechnung (mit Rest) hervorkommen. ist also der Rest der Division der Zahlen von und . | |
und sind dabei Zahlen, die aus der Rechnung (mit Rest) hervorkommen. ist also der Rest der Division der Zahlen und . | |
und sind dabei Zahlen, die aus der Rechnung (mit Rest) hervorkommen. ist also der Rest der Division der Zahlen und . |
Führe dies so oft durch, bis bei einer Rechnung Rest herauskommt.
Man kann hier ein Schema erkennen:
Die Zahl ist dann der von und . |
Erklärung am Beispiel
Man hat die zwei Zahlen und .
Rechnung | Beschreibung |
|---|---|
| Die Zahlen und errechnet man mit schriftlicher Division mit Rest: damit ist und |
| Die Zahlen und errechnet man so: damit ist und |
| Die Zahlen und errechnet man so: damit ist und |
Also ist der größte gemeinsame Teiler von und :
Eingebetteter Serlo-Inhalt