Enzyklopädie

Enzyklopädie
Login

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

Quellenangabe

Kostenlos testen
  • redaktionell geprüfte und verlässliche Inhalte

  • altersgerecht aufbereitet im Schullexikon

  • monatlich kündbar

oder
Sie sind Lehrkraft? Starten Sie Ihren kostenlosen Test hier.