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.