Что такое наибольший общий делитель?
Наибольший общий делитель (НОД) — это самое большое целое положительное число, на которое без остатка делятся оба заданных целых числа. В англоязычной литературе его обозначают как GCF (greatest common factor), GCD (greatest common divisor) или HCF (highest common factor) — это просто разные названия одной и той же величины. Например, НОД чисел 48 и 36 равен 12, потому что 12 — наибольшее число, на которое нацело делятся оба. Этот калькулятор мгновенно находит НОД, а заодно вычисляет и наименьшее общее кратное (НОК).
Как пользоваться калькулятором
Введите два неотрицательных целых числа в поля a и b и нажмите кнопку расчёта. Калькулятор выдаст наибольший общий делитель и наименьшее общее кратное. Порядок чисел не важен — \(\text{НОД}(48, 36)\) равен \(\text{НОД}(36, 48)\).
Как это работает: формула
В основе расчёта лежит алгоритм Евклида — изящный метод, известный ещё со времён Древней Греции. Он опирается на простой факт: НОД двух чисел делит и их остаток от деления. Пару \((a, b)\) последовательно заменяют на \((b, a \bmod b)\) до тех пор, пока второе число не станет равным нулю; оставшееся первое число и есть искомый НОД. Наименьшее общее кратное затем находится по формуле
$$\text{НОК}(a, b) = \frac{a \times b}{\text{НОД}(a, b)}$$
Разбор примера
Найдём НОД чисел 48 и 36. Шаг 1: \(48 \bmod 36 = 12\), значит пара превращается в \((36, 12)\). Шаг 2: \(36 \bmod 12 = 0\), и пара становится \((12, 0)\). Поскольку второе число равно 0, НОД равен 12. Наименьшее общее кратное:
$$\text{НОК} = \frac{48 \times 36}{12} = \frac{1728}{12} = 144$$Часто задаваемые вопросы
Чему равен НОД, если одно из чисел равно 0? По определению \(\text{НОД}(a, 0) = a\). А \(\text{НОД}(0, 0)\) равен 0.
Это то же самое, что HCF или GCD? Да. GCF, GCD и HCF — это разные обозначения одной и той же величины, которую в русском языке называют НОД.
Что будет, если у чисел нет общих делителей? Тогда НОД равен 1, а сами числа называют взаимно простыми.
