Алгоритм Евклида находит наибольший общий делитель двух положительных целых чисел последовательным делением с остатком. Заменяйте пару (a, b) на (b, r), где r — остаток от деления a на b; последний ненулевой остаток и есть НОД. Для отрицательных входов берут модули, а НОД(a, 0) = |a|.
Алгоритму Евклида больше двух тысяч лет, а его идеи по-прежнему используются в вычислениях с целыми числами. Расширенная версия помогает находить обратные элементы по модулю — операция нужна, например, при создании ключей в RSA. Современные защищённые соединения используют разные алгоритмы, но этот древний метод остаётся важной частью вычислительной теории чисел.
Если коротко: алгоритм Евклида — это способ найти наибольший общий делитель (НОД) двух чисел за несколько шагов деления с остатком. Большее число делим на меньшее, потом меньшее на остаток — и так, пока остаток не станет нулём.
Расширенный алгоритм Евклида используют в RSA, чтобы находить число, обратное по модулю. Это конкретная связь школьной задачи о НОД с криптографией — без утверждения, будто все современные защищённые соединения работают только на RSA.
Простой пример: как разделить конфеты по-честному
Представьте: у вас 12 шоколадных конфет и 8 карамелек. Вы хотите разложить их в одинаковые подарочные пакеты так, чтобы в каждом было одинаковое число шоколадок и одинаковое число карамелек, и при этом не осталось ни одной лишней. Сколько пакетов получится максимум?
Ответ — 4 пакета: в каждом по 3 шоколадки и 2 карамельки. Число 4 здесь — это НОД чисел 12 и 8. Именно его и ищет алгоритм Евклида. Когда вы делите пиццу на детей поровну или раскладываете карточки игры по стопкам — вы интуитивно решаете задачу, которую Евклид формализовал.
Как работает алгоритм: пошагово
Идея алгоритма гениально простая. Возьмём два числа — например, 252 и 105. Большее делим на меньшее с остатком: 252 = 2·105 + 42. Остаток 42 — это уже число поменьше. Теперь делим 105 на 42: 105 = 2·42 + 21. Остаток снова уменьшился. Делим 42 на 21: 42 = 2·21 + 0. Остаток ноль — значит, последний ненулевой остаток (21) и есть НОД.
Почему это работает? Любой общий делитель двух чисел делит и их разность. А деление с остатком — это, по сути, многократное вычитание. Так что общие делители «переходят по наследству» к остатку, и в конце концов мы добираемся до самого большого из них.
Идея одна — уменьшать пару чисел, не меняя их общий делитель. Сделать это можно делением с остатком или повторным вычитанием; сравним маршруты.
Два способа применять алгоритм
Способ 1. С остатками от деления (быстрый)
Это современная форма. На каждом шаге заменяем пару (a, b) на пару (b, a mod b), где «a mod b» — остаток от деления a на b. Когда второе число становится нулём, первое — и есть НОД.
Пример для 462 и 1071:
- 1071 ÷ 462 = 2 (остаток 147)
- 462 ÷ 147 = 3 (остаток 21)
- 147 ÷ 21 = 7 (остаток 0)
НОД(1071, 462) = 21. Всего три шага.
Способ 2. Вычитанием (исторический)
Именно так алгоритм описан в «Началах» Евклида. На каждом шаге из большего числа вычитаем меньшее, пока числа не сравняются. Их общее значение и есть НОД.
Пример для 18 и 24: 24 − 18 = 6. Теперь пара (18, 6). 18 − 6 = 12, (12, 6). 12 − 6 = 6, (6, 6). Числа равны — НОД(18, 24) = 6.
Этот способ медленнее (для пары 1000 и 1 потребуется 999 шагов!), но интуитивно понятнее. Деление с остатком — это то же вычитание, только «сжатое».
Когда шаги алгоритма понятны, становится видно, почему он пережил две тысячи лет: НОД нужен всякий раз, когда требуется согласовать целые циклы или восстановить взаимную простоту.
Где это работает в реальной жизни
Криптография и банковские карты
В системах, где применяют RSA, расширенный алгоритм Евклида помогает вычислить закрытую экспоненту — обратный элемент по модулю. Но конкретное банковское приложение или HTTPS-соединение может использовать и другие современные криптографические схемы.
Музыка и ритмика
В музыке алгоритм Евклида генерирует ритмы. Если у вас 5 ударов нужно равномерно распределить на 13 долей — алгоритм даёт оптимальный паттерн. Евклидова конструкция воспроизводит ритмические рисунки, встречающиеся во фламенко, кубинской музыке и некоторых африканских традициях; это не утверждение об их историческом происхождении. Исследователь Годфрид Туссен сопоставил евклидову конструкцию с более чем сорока традиционными ритмическими рисунками; это сильное совпадение моделей, а не утверждение о происхождении почти всей мировой музыки.
Календари и приливы
Календарям приходится приближённо согласовывать несоизмеримые периоды: тропический год, синодический месяц и сутки. Для поиска хороших рациональных приближений используют цепные дроби, связанные с шагами алгоритма Евклида. Метонов 19-летний цикл и правила високосных лет требуют отдельных астрономических наблюдений и календарных соглашений — один НОД их не выводит.
Задачи для самопроверки
Задача 1. Найдите НОД(48, 36) алгоритмом Евклида
Показать решение
48 ÷ 36 = 1 (остаток 12). Теперь делим 36 на 12: 36 ÷ 12 = 3 (остаток 0). Последний ненулевой остаток — 12.
Ответ: НОД(48, 36) = 12.
Задача 2. Найдите НОД(91, 65)
Показать решение
91 ÷ 65 = 1 (остаток 26). 65 ÷ 26 = 2 (остаток 13). 26 ÷ 13 = 2 (остаток 0).
Ответ: НОД(91, 65) = 13.
Задача 3. Можно ли разрезать торт 36×24 см на одинаковые квадратные куски без остатка? Какой будет сторона самого большого такого куска?
Показать решение
Нужно найти НОД(36, 24). 36 ÷ 24 = 1 (остаток 12). 24 ÷ 12 = 2 (остаток 0). НОД = 12.
Ответ: сторона самого большого квадратного куска — 12 см. Всего получится 6 кусков (3 в длину, 2 в ширину).
Откуда взялся алгоритм
Алгоритм описан в седьмой книге «Начал» Евклида — самой влиятельной математической работы в истории, написанной около 300 года до н.э. в Александрии. Евклид рассуждал о целых числах как о множествах единиц и часто иллюстрировал их отрезками; близкий алгоритм поиска общей меры для геометрических величин изложен отдельно. Если бок о бок укладывать меньший отрезок вдоль большего и потом «остаток» вдоль меньшего — рано или поздно один отрезок уложится в другом целое число раз.
Идеи последовательного вычитания и измерения общей части встречались в древней математике, но надёжно связывать шульба-сутры именно с алгоритмом Евклида нельзя. В дошедшем тексте Евклида дано строгое обоснование того, что метод заканчивается за конечное число шагов. Это одно из древнейших дошедших до нас строгих изложений алгоритма и его завершения.
Самое удивительное: связь с золотым сечением
Какие числа «хуже всего» для алгоритма Евклида — то есть требуют максимума шагов? Оказывается, это соседние числа Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89… Попробуйте применить алгоритм к 89 и 55 — потребуется 9 шагов, хотя сами числа невелики.
А отношение соседних чисел Фибоначчи стремится к золотому сечению φ ≈ 1,618. Получается удивительная связь: самые «упрямые» для древнегреческого алгоритма пары чисел — это те, чьё отношение ближе всего к идеальной пропорции, описанной самим же Евклидом в шестой книге «Начал». Алгоритм, золотое сечение и числа Фибоначчи оказались сплетены в одной красивой математической истории, которую мы только начали распутывать в XIX веке.
Часто задаваемые вопросы
Что такое алгоритм Евклида простыми словами?
Это способ найти самое большое число, на которое без остатка делятся два других числа. Большее делим на меньшее, потом меньшее на остаток — и так пока не получится ровно. Последний ненулевой остаток и есть ответ.
Зачем нужен НОД?
НОД помогает сокращать дроби, делить предметы поровну, согласовывать целые циклы и выполнять некоторые операции в криптографии.
Работает ли алгоритм Евклида для трёх и более чисел?
Да, но применяем его попарно: сначала находим НОД двух чисел, потом НОД результата с третьим числом, и так далее. НОД(12, 18, 24) = НОД(НОД(12, 18), 24) = НОД(6, 24) = 6.
Что быстрее: вычитание или деление с остатком?
Вариант с остатками обычно требует значительно меньше итераций, особенно когда одно число намного больше другого. Для пары (1000, 7) повторному вычитанию потребуется около 142 шагов, а алгоритму с остатками — три деления: остатки 6, 1 и 0. Современные библиотеки используют дополнительно «двоичный алгоритм Евклида», который ещё быстрее для компьютеров.
Что такое расширенный алгоритм Евклида?
Это усиленная версия, которая помимо НОД(a, b) находит ещё два целых числа x и y такие, что a·x + b·y = НОД(a, b). Коэффициенты Безу позволяют находить обратный элемент по модулю; эта операция используется, в частности, при вычислении закрытой экспоненты RSA.
Читайте также
- Признаки делимости: как за секунды понять, делится ли число
- НОД и НОК: что это, формулы и 3 способа найти
- Двоичная система счисления: как работает и где применяется
- Великая теорема Ферма: 358 лет ожидания и 129 страниц доказательства
- Евклид: математик, который написал учебник на 2300 лет вперёд
Короткий ответ: итог
Работайте с неотрицательными модулями чисел. Пока второй элемент пары не равен нулю, находите остаток и заменяйте (a, b) на (b, r). Если b уже равен нулю, ответ равен |a|; для двух нулей НОД обычно не определяют.
Проверьте себя
Найдите НОД(48, 18) алгоритмом Евклида.
48 = 18 * 2 + 12; 18 = 12 * 1 + 6; 12 = 6 * 2 + 0, НОД = 6.
Какой последний ненулевой остаток в этой задаче?
6.
Почему алгоритм заканчивается?
Потому что остатки уменьшаются и не могут убывать бесконечно среди неотрицательных целых чисел.
Что изучать дальше
Закрепите алгоритм на нескольких парах чисел и каждый раз объясняйте, почему замена (a, b) на (b, r) не меняет НОД. перейти к интерактивным урокам.
Интерактивная практика
В калькуляторе НОД вводите пары с разным числом шагов и следите не только за ответом, но и за последовательностью остатков.
1 комментарий к “Алгоритм Евклида: как найти НОД за несколько шагов”