euklidischer Algorithmus

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 r₁