Euklidischer Algorithmus
Euklidischer Algorithmus [nach Euklid], Verfahren zur Bestimmung des größten gemeinsamen Teilers zweier natürlicher Zahlen a, b (a > b > 0), das ohne Primfaktorzerlegung auskommt.
Ausgenutzt wird die Tatsache, dass der größte gemeinsame Teiler von a und b gleich dem größten gemeinsamen Teiler von b und dem bei der Division a : b bleibenden Rest r1 ist. Das gleiche Argument lässt sich auf den größten gemeinsamen Teiler von b und r1 anwenden usw.; das Verfahren besteht also
Informationen zum Artikel
Quellenangabe