GCD Calculator

Найдите наибольший общий делитель любых чисел

Наибольший общий делитель (НОД) — самое большое число, которое делит все заданные числа без остатка. Введите два или больше чисел через запятую — и НОД будет вычислен мгновенно с помощью алгоритма Евклида.

Определение и примеры

• НОД(12, 18) = 6 — потому что 6 это наибольшее число, которое делит и 12, и 18.
• НОД(48, 36, 24) = 12 — наибольшее число, делящее все три числа.
• НОД(7, 13) = 1 — эти числа взаимно простые (у них нет общего делителя, кроме 1).

Алгоритм Евклида

Самый известный метод вычисления НОД — алгоритм Евклида, описанный самим Евклидом около 300 года до нашей эры в его "Началах". Алгоритм утверждает, что НОД(a, b) = НОД(b, a mod b), и повторяется, пока b не станет равным 0. Например: НОД(48, 36) → НОД(36, 12) → НОД(12, 0) = 12.

Упрощение дробей

Самое частое повседневное применение НОД — приведение дробей к простейшему виду. Чтобы упростить 48/72, вычислите НОД(48, 72) = 24, затем разделите оба числа на 24: получится 2/3. Результат полностью сокращён, поскольку числитель и знаменатель теперь взаимно простые.

Криптография

Шифрование RSA — алгоритм, обеспечивающий безопасность большей части интернет-коммуникаций, — фундаментально опирается на теорию чисел, связанную с НОД и взаимно простыми числами. Алгоритм генерации ключей RSA требует выбора двух больших простых чисел, которые всегда взаимно просты друг с другом и со своим произведением.

Разделение на равные группы

Очень практичное применение НОД — разбиение коллекций разного размера на наибольшее возможное число одинаковых групп без остатка. Если у вас есть 48 яблок и 36 апельсинов, и вы хотите собрать одинаковые фруктовые корзины, используя все фрукты без остатка, наибольшее число корзин, которое можно собрать, — это НОД(48, 36) = 12, каждая по 4 яблока и 3 апельсина. Та же логика применима к разрезанию отрезов ткани или досок на равные куски, расстановке стульев равными рядами в помещениях разного размера или распределению бюджета между отделами максимально крупными равными частями.

Инженерия

В машиностроении НОД числа зубьев двух шестерён определяет, как часто одна и та же пара зубьев встречается снова. Если у шестерни A 48 зубьев, а у шестерни B — 36, то НОД(48, 36) = 12, а значит, каждые 12 зубьев шестерни A зацепляются с каждыми 12 зубьями шестерни B.

Как пользоваться калькулятором

Введите числа в поле через запятую — два числа или сколько угодно. Нажмите кнопку расчёта, и НОД всего набора появится немедленно, вместе с пошаговым разложением по алгоритму Евклида, чтобы вы видели, как именно был получен ответ, а не воспринимали его как чёрный ящик. Ввод одного числа или чисел, не имеющих общего делителя, кроме 1, обрабатывается корректно: во втором случае инструмент просто сообщит НОД, равный 1, подтверждая, что числа взаимно простые.

Почему алгоритм Евклида настолько эффективен

До метода Евклида найти НОД означало перечислить все делители каждого числа и выбрать наибольший из общих — работоспособно для маленьких чисел, но безнадёжно медленно для больших. Алгоритм Евклида вместо этого многократно заменяет большее число остатком от деления его на меньшее, быстро сжимая задачу. Для двух чисел любого реалистичного размера он обычно завершается менее чем за пятьдесят шагов, поэтому он остаётся стандартным методом, который преподают до сих пор, и тем, что встроено практически в любой калькулятор, функцию электронной таблицы и библиотеку языка программирования, вычисляющую НОД.

Расширение на большее число чисел

Когда вы вводите три или больше чисел, калькулятору не нужен новый алгоритм — он просто применяет случай двух чисел последовательно. НОД целого списка равен НОД первых двух чисел, объединённому с третьим, и так далее: НОД(a, b, c) = НОД(НОД(a, b), c). Это работает, потому что любое число, делящее a, b и c, обязано делить и НОД любой их пары, поэтому сокращение списка по два числа за раз никогда не теряет информацию. Хорошая иллюстрация того, как простой строительный блок — НОД двух чисел — аккуратно масштабируется на список произвольной длины.

Взаимно простые числа и что говорит НОД, равный 1

Когда калькулятор сообщает НОД, равный 1, введённые вами числа называются взаимно простыми, то есть у них нет общего делителя больше 1, даже если у каждого по отдельности может быть много делителей. Например, 8 и 15 взаимно просты, хотя 8 = 2×2×2, а 15 = 3×5 — они просто не имеют общих простых "строительных блоков". Взаимная простота постоянно встречается в теории чисел и криптографии, поскольку многие алгоритмы опираются на выбор чисел, гарантированно не имеющих скрытой общей структуры.

Разобранный пример шаг за шагом

Проследим работу алгоритма Евклида для НОД(48, 18). Сначала 48 = 2×18 + 12, значит задача сводится к НОД(18, 12). Далее 18 = 1×12 + 6, значит сводится к НОД(12, 6). Наконец, 12 = 2×6 + 0, остаток становится нулём, и последний ненулевой остаток, 6, — это и есть НОД. Каждый шаг алгоритма быстро уменьшает участвующие числа, именно поэтому он завершается всего за несколько шагов даже для очень больших чисел, в отличие от перечисления всех делителей, которое быстро замедляется по мере роста чисел.

Приватно и мгновенно

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