1071 mod 465 to 141. 465 mod 141 to 42. 141 mod 42 to 15, 42 mod 15 to 12, 15 mod 12 to 3, a 12 mod 3 to 0. Ostatnia niezerowa reszta, 3, to największy wspólny dzielnik, a każdy krok jest uprawniony z tego samego powodu: każda liczba dzieląca zarówno a, jak i b dzieli też a − qb, więc para i jej reszta mają dokładnie te same dzielniki. Nic tutaj nie potrzebuje rozkładu na czynniki — i to praktyczny sens: 3 jest odpowiedzią na długo przed tym, jak ktokolwiek wie, dlaczego 1071 to 3·357.
Liczba kroków to rzecz, na którą warto patrzeć. Lamé udowodnił w 1844 roku, że algorytm Euklidesa na parze liczb całkowitych nigdy nie trwa dłużej niż około pięciokrotność liczby cyfr dziesiętnych mniejszej, a najgorsze przypadki to kolejne liczby Fibonacciego — dlatego 141, 42, 15, 12, 3 na tej stronie kurczą się szybko: nic tutaj nie jest sąsiadem Fibonacciego. Rozszerzona wersja tej samej tabeli reszt zwraca też współczynniki z 3 = 1071s + 465t, składnik każdej procedury dzielenia modularnego w systemie algebry komputerowej.
Odpowiedź
3
Jak to czytać
15 mod 12, ostatnia niezerowa reszta. Pierwsze dwa linki to kroki otwierające, 1071 mod 465 = 141 i 465 mod 141 = 42.
Źródło
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
Rozwiąż w kalkulatorze
Te linki otwierają właściwy kalkulator z już wpisanymi liczbami tego zadania. Powyższa linia to to, co powinien pokazać ekran — sprawdź sam.