1071 mod 465 равно 141. 465 mod 141 равно 42. 141 mod 42 равно 15, 42 mod 15 равно 12, 15 mod 12 равно 3, а 12 mod 3 равно 0. Последний ненулевой остаток, 3, и есть наибольший общий делитель, и каждый шаг допустим по одной и той же причине: любое число, делящее и a, и b, делит также a − qb, так что у пары и её остатка ровно одни и те же делители. Здесь ничего не нужно раскладывать на множители, и в этом практический смысл — 3 есть ответ задолго до того, как кто-то узнает, почему 1071 равно 3·357.
Число шагов — то, на что стоит смотреть. Ламе доказал в 1844 году, что алгоритму Евклида для пары целых чисел никогда не нужно больше примерно пятикратного числа десятичных знаков меньшего и что худшие случаи — соседние числа Фибоначчи, поэтому 141, 42, 15, 12, 3 на этой странице убывают быстро: ничто здесь не сосед Фибоначчи. Расширенная версия той же таблицы остатков даёт ещё и коэффициенты с 3 = 1071s + 465t — ингредиент любой процедуры модульного деления в системе компьютерной алгебры.
Ответ
3
Как его читать
15 mod 12 — последний ненулевой остаток. Первые две ссылки — начальные шаги, 1071 mod 465 = 141 и 465 mod 141 = 42.
Источник
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
Пересчитать в калькуляторе
Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.