Алгоритм Евклида для 1071 и 465 достигает НОД 3 через остатки 141, 42, 15, 12

Берите остатки, пока один не станет нулём; последний ненулевой остаток и есть наибольший общий делитель.

Уравнения и алгебра · Уровень: Классический результат · Обновлено 2026-11-10

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

Пересчитать в калькуляторе

Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.

Это независимый сторонний информационный сайт. Он не связан с Casio, Texas Instruments или их дистрибьюторами, не спонсируется ими и не имеет их авторизации. Названия моделей и продуктов — товарные знаки соответствующих правообладателей; они приведены здесь только для идентификации устройств.

Последовательности нажатий клавиш в этих справочниках составлены на основе собственных данных о раскладке этого сайта — тех же данных, которые отображает онлайн-калькулятор, — а также общедоступных сведений о продуктах. Характеристики и региональные конфигурации проверяются на реальном устройстве и по последним материалам производителя.