1071 mod 465, 141 eder. 465 mod 141, 42 eder. 141 mod 42, 15 eder; 42 mod 15, 12 eder; 15 mod 12, 3 eder ve 12 mod 3, 0 eder. Son sıfır olmayan kalan, 3, en büyük ortak bölen'dir ve her adım aynı nedenle meşrudur: hem a'yı hem b'yi bölen her sayı a − qb'yi de böler; dolayısıyla çift ve kalanı tam olarak aynı bölenlere sahiptir. Burada hiçbir şey çarpanlara ayırmayı gerektirmez, ki pratik nokta budur: 3, kimse 1071'in neden 3·357 olduğunu bilmeden çok önce cevaptır.
İzlenecek şey adım sayısıdır. Lamé 1844'te, bir tamsayı çifti üzerinde Öklid algoritmasının asla küçüğün ondalık basamak sayısının yaklaşık beş katından fazlasını gerektirmediğini ve en kötü durumların ardışık Fibonacci sayıları olduğunu kanıtladı: bu sayfadaki 141, 42, 15, 12, 3'ün hızlı daralmasının nedeni budur, burada hiçbir şey bir Fibonacci komşusu değildir. Aynı kalan tablosunun genişletilmiş sürümü, 3 = 1071s + 465t ile katsayıları da döndürür; bir bilgisayar cebir sistemindeki her modüler bölme rutininin bileşeni.
Cevap
3
Nasıl okunur
15 mod 12, son sıfır olmayan kalan. İlk iki bağlantı başlangıç adımlarıdır, 1071 mod 465 = 141 ve 465 mod 141 = 42.
Kaynak
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
Hesap makinesinde çözün
Bu bağlantılar, bu problemin sayıları zaten yazılmış olarak doğru hesap makinesini açar. Yukarıdaki satır, ekranın göstermesi gereken şeydir — kendiniz kontrol edin.