Euklids Algorithmus erreicht mit 1071 und 465 den ggT 3 über die Reste 141, 42, 15, 12

Nehmen Sie Reste, bis einer null ist; der letzte von Null verschiedene Rest ist der größte gemeinsame Teiler.

Gleichungen und Algebra · Niveau: Klassisches Ergebnis · Aktualisiert am 2026-11-10

1071 mod 465 ist 141. 465 mod 141 ist 42. 141 mod 42 ist 15, 42 mod 15 ist 12, 15 mod 12 ist 3, und 12 mod 3 ist 0. Der letzte von Null verschiedene Rest, 3, ist der größte gemeinsame Teiler, und jeder Schritt ist aus demselben Grund zulässig: Jede Zahl, die sowohl a als auch b teilt, teilt auch a − qb, das Paar und sein Rest haben also genau dieselben Teiler. Hier muss nichts faktorisiert werden, und das ist der praktische Punkt – 3 ist die Antwort, lange bevor jemand weiß, warum 1071 gleich 3·357 ist.

Die Zahl der Schritte ist das, worauf man achten sollte. Lamé bewies 1844, dass der euklidische Algorithmus für ein Paar ganzer Zahlen nie mehr als etwa das Fünffache der Zahl der Dezimalstellen der kleineren braucht und dass die schlimmsten Fälle aufeinanderfolgende Fibonacci-Zahlen sind – weshalb 141, 42, 15, 12, 3 auf dieser Seite schnell schrumpfen: Nichts hier ist ein Fibonacci-Nachbar. Die erweiterte Version derselben Resttabelle liefert auch Koeffizienten mit 3 = 1071s + 465t, die Zutat jeder Routine für modulare Division in einem Computeralgebrasystem.

Antwort

3

So lesen Sie sie

15 mod 12, der letzte von Null verschiedene Rest. Die ersten beiden Links sind die Anfangsschritte, 1071 mod 465 = 141 und 465 mod 141 = 42.

Quelle

Euclid, Elements VII.1-2 describes antanairesis — repeatedly subtracting the lesser from the greater until a common measure is reached; the remainder form used here is the same procedure written with division, and 1071 = 3²·7·17 against 465 = 3·5·31 confirms the answer the remainders give

Im Rechner durchrechnen

Diese Links öffnen den passenden Rechner mit den bereits eingegebenen Zahlen dieser Aufgabe. Die Zeile darüber ist das, was der Bildschirm anzeigen sollte – prüfen Sie selbst.

Dies ist eine unabhängige Tool-Website eines Drittanbieters. Sie ist weder mit Casio, Texas Instruments oder deren Vertriebspartnern verbunden noch von ihnen gesponsert oder autorisiert. Modell- und Produktnamen sind Marken der jeweiligen Inhaber und erscheinen hier nur zur Identifizierung der Geräte.

Die Tastenfolgen in diesen Handbüchern wurden aus den eigenen Layoutdaten dieser Website erstellt — denselben Daten, die der Online-Rechner darstellt — sowie aus öffentlich verfügbaren Produktinformationen. Spezifikationen und regionale Konfigurationen werden am physischen Gerät und anhand der neuesten Unterlagen des Herstellers überprüft.