Softonic

Калькулятор НОД

Шаг 1 / 2 Наибольший общий делитель (GCF/GCD)
Далее

Наибольший общий делитель (по-английски GCD или HCF), это наибольшее целое число, которое делит без остатка каждое число из заданного набора. Введите два или более положительных целых числа, и этот калькулятор сразу вернёт их наибольший общий делитель, вычисленный по алгоритму Евклида. Результат можно использовать, чтобы проверить домашнее задание или сократить дробь, например 84/144 до 7/12.

Как найти НОД

  1. 1

    Введите целые числа

    Два или более положительных целых числа, разделённых запятыми, пробелами или переносами строк.

  2. 2

    Инструмент применяет алгоритм Евклида

    Пара (a, b) многократно заменяется на (b, a mod b), пока остаток не станет равен нулю.

  3. 3

    Прочитайте НОД

    Показанный результат, это наибольший общий делитель ваших чисел, вычисленный по алгоритму Евклида.

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

Чтобы найти gcd(a, b), где a ≥ b > 0:

while b ≠ 0:
    (a, b) ← (b, a mod b)
return a

Для более чем двух чисел применяется тождество gcd(a, b, c) = gcd(gcd(a, b), c).

Разобранный пример: НОД(84, 144)

Шаг Деление Остаток
1 144 ÷ 84 = 1 r 60 60
2 84 ÷ 60 = 1 r 24 24
3 60 ÷ 24 = 2 r 12 12
4 24 ÷ 12 = 2 r 0 0

Последний ненулевой остаток равен 12, поэтому gcd(84, 144) = 12, а дробь 84/144 сокращается до 7/12.

Когда НОД равен 1

Если gcd(a, b) = 1, числа взаимно просты. Числа 15 и 28 взаимно просты, хотя ни одно из них не является простым; именно это свойство не позволяет сократить дробь 15/28.

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

gcd(a, b) × lcm(a, b) = |a × b|. Поэтому, зная одно из них, вы сразу получаете и другое.

Типичные случаи применения

  • Сокращение дробей до несократимого вида.
  • Поиск наибольшего одинакового размера плитки, которой можно покрыть прямоугольник.
  • Упрощение передаточных отношений и диаметров шкивов.
  • Модульная арифметика: взаимно простые пары обратимы по модулю друг друга.

Часто задаваемые вопросы

Это три названия одной и той же величины. GCF (greatest common factor) распространён в школах США, GCD (greatest common divisor), в математике и информатике, а HCF (highest common factor), в учебных программах Великобритании. По-русски всем им соответствует НОД (наибольший общий делитель).

Он пропускает отрицательные числа: в расчёт берутся только положительные целые числа. Чтобы включить отрицательное число, введите его абсолютное значение, например 84 вместо -84.

Он равен n (для положительного n). Ноль делится на любое целое число, поэтому наибольший общий делитель числа n с нулём, это само n. Значение gcd(0, 0) обычно определяют как 0.

Нет, числа не сохраняются. Они отправляются на наш сервер только для вычисления результата и могут также попасть в ссылку на страницу при переходе между шагами.

Сопутствующие инструменты

Калькулятор балясин

Введите свободный пролёт перил, ширину балясины и максимально допустимый зазор, чтобы получить точное количество необходимых балясин и равный промежуток между каждой стойкой, не превышающий нормативный предел.

Калькулятор делительной окружности отверстий

Рассчитайте PCD, угловой шаг и точные координаты X/Y равномерных отверстий с поворотом, смещением центра и экспортом CSV.

Калькулятор длительности

Рассчитайте длительность между двумя часами в формате HH:MM, десятичных часах, минутах и секундах.

Калькулятор производительности осушителя воздуха

Оцените производительность переносного осушителя по площади и сырости помещения в литрах и американских пинтах в сутки.

Калькулятор юбки-солнце

Рассчитайте радиусы талии и низа для четверти, половины, трёх четвертей или полного круга с прибавками и припусками.

Калькулятор перцентиля ребенка

Введите возраст, пол и вес ребенка, чтобы увидеть примерный диапазон перцентиля веса и референсный диапазон для этого возраста, от рождения до 24 месяцев.

Инструмент доступен на других языках