Что такое наибольший общий делитель?
Наибольший общий делитель (НОД) двух целых чисел — это самое большое положительное число, на которое оба числа делятся без остатка. Например, НОД чисел 48 и 36 равен 12, ведь 12 — самое большое число, на которое нацело делятся и 48, и 36. Этот калькулятор НОД мгновенно вычислит нужное значение, а заодно покажет наименьшее общее кратное (НОК).
Как пользоваться калькулятором
Введите два целых числа в поля A и B и посмотрите на результат. Калькулятор берёт модуль каждого числа, поэтому отрицательные значения тоже обрабатываются правильно. Если для одного из чисел указать 0, то НОД будет равен второму числу — ведь на ноль делится любое целое число.
Как работает алгоритм Евклида
В основе калькулятора лежит алгоритм Евклида — один из старейших алгоритмов, которым пользуются до сих пор. Он опирается на простое свойство: \(\gcd(a, b) = \gcd(b, a \bmod b)\). Большее число раз за разом заменяется остатком от деления, пока остаток не станет равен 0. Последний ненулевой делитель и есть искомый НОД. Такой подход не требует раскладывать числа на множители и работает молниеносно даже для очень больших значений.
Разбор примера
Найдём НОД(48, 36):
$$48 \bmod 36 = 12 \rightarrow \gcd(36,\ 12)$$$$36 \bmod 12 = 0 \rightarrow \gcd(12,\ 0) = \mathbf{12}$$Тогда НОК равен $$\text{НОК} = \frac{|48 \times 36|}{12} = \frac{1728}{12} = \mathbf{144}$$
Частые вопросы
Чем отличаются НОД и HCF? Ничем — это одно и то же значение под разными названиями. «Наибольший общий делитель» (GCD) — привычный термин в США, а «highest common factor» (HCF) чаще встречается в Великобритании. В русскоязычной математике используется аббревиатура НОД.
Чему равен НОД взаимно простых чисел? Всегда 1. Например, у чисел 8 и 15 нет общих делителей, кроме единицы, — такие числа называют взаимно простыми.
Может ли НОД быть больше меньшего из чисел? Нет. НОД никогда не превышает меньшее из двух чисел и в точности равен ему тогда, когда меньшее число нацело делит большее.
