Нахождение наибольшего общего делителя

Что такое наибольший общий делитель

Наибольший общий делитель (сокращённо НОД) двух натуральных чисел — это самое большое число, на которое делятся без остатка оба заданных числа. Например, НОД чисел 12 и 18 равен 6, потому что 6 — наибольшее число, делящее и 12, и 18. Эту задачу элегантно и быстро решает древний алгоритм Евклида, придуманный более двух тысяч лет назад и до сих пор широко применяемый.

Идея алгоритма Евклида

Алгоритм основан на важном свойстве: НОД двух чисел не меняется, если большее число заменить на остаток от его деления на меньшее. Это действие повторяют снова и снова, пока одно из чисел не станет нулём. Тогда второе, ненулевое число и есть искомый НОД. С каждым шагом числа уменьшаются, поэтому алгоритм всегда завершается, причём очень быстро.

Разбор на примере

Найдём НОД чисел 48 и 18 способом с остатками, выписывая каждый шаг.

Шаг	a	b	a mod b
1	48	18	12
2	18	12	6
3	12	6	0

Как только остаток стал нулём, ответом является последнее ненулевое число — 6. Действительно, 6 делит и 48, и 18, и большего общего делителя у них нет.

Запись алгоритма

В виде команд алгоритм Евклида записывается компактно:

пока b <> 0 r = a mod b a = b b = r конец { ответ хранится в a }

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

Связь с наименьшим общим кратным

Зная НОД, легко найти и наименьшее общее кратное (НОК) тех же чисел. Их связывает простое соотношение: произведение двух чисел равно произведению их НОД и НОК. Отсюда НОК получают делением: НОК = a * b / НОД. Поэтому алгоритм Евклида ценен вдвойне — он открывает путь сразу к двум важным величинам, которые постоянно встречаются при работе с дробями и делимостью. Например, чтобы сократить обыкновенную дробь, числитель и знаменатель делят на их НОД, а чтобы привести дроби к общему знаменателю, удобно использовать их НОК.

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

Кратко о главном

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