Наибольший общий делитель (НОД) онлайн
Расчёт наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК) для двух и более целых чисел онлайн — с простым разложением и алгоритмом Евклида.
О калькуляторе
Страница для расчёта наибольшего общего делителя (НОД) двух целых чисел. НОД — самое большое число, на которое оба исходных делятся без остатка. Пример: НОД(12, 18) = 6, потому что 6 — максимальное число, на которое делятся и 12, и 18 (общие делители: 1, 2, 3, 6, из них 6 — наибольший). Тема из школьной программы 6 класса, но применяется и в криптографии, и в работе с дробями. Смежный расчёт наименьшего общего кратного — в режиме НОК онлайн.
Самый быстрый метод — алгоритм Евклида. Идея: заменять большее число остатком от его деления на меньшее и повторять до нулевого остатка. Последний ненулевой остаток и есть НОД. Пример для 48 и 36: 48 mod 36 = 12; 36 mod 12 = 0 — значит, НОД = 12. Ещё пример для 1071 и 462: 1071 mod 462 = 147; 462 mod 147 = 21; 147 mod 21 = 0 — НОД = 21. Всего три шага для чисел из четырёх знаков. Второй метод — разложение на простые множители: НОД равен произведению общих простых множителей в минимальных степенях. 12 = 2²·3, 18 = 2·3², общие множители: 2 (в минимальной степени 1) и 3 (в минимальной степени 1), итого НОД = 2·3 = 6.
Главное практическое применение — сокращение дробей. Дробь 18/24 сокращается делением числителя и знаменателя на НОД(18, 24) = 6: получаем 3/4 сразу, без промежуточных шагов. Если НОД = 1, числа называют взаимно простыми (например, 7 и 15) — дробь 7/15 уже несократима. Другое применение — разбиение на равные группы: если нужно разложить 24 конфет и 36 печенек в одинаковые наборы, максимальное число наборов — НОД(24, 36) = 12 (в каждом по 2 конфеты и 3 печеньки). Для более сложной работы с дробями пригодится калькулятор дробей.
Как считаем
Наибольший общий делитель — НОД(12, 18) = 6
Обозначения. НОД(a, b, …) — наибольшее натуральное число, на которое каждое из данных чисел делится без остатка. Иногда пишут gcd (greatest common divisor) или НОК-собрат: они разные, не путайте. НОД определён для положительных целых; в этом калькуляторе — минимум два числа, максимум двадцать, каждое от 1 до триллиона.
Формула: НОД(a, b) — алгоритм Евклида; НОД(a, b, c) = НОД(НОД(a, b), c)
Как посчитать пошагово.
- Разложите каждое число на простые множители: 12 = 2 × 2 × 3, 18 = 2 × 3 × 3. Общие с минимальными степенями — 2 и 3 → НОД = 6.
- Или примените алгоритм Евклида: 18 = 12 × 1 + 6; 12 = 6 × 2 + 0. Последний ненулевой остаток — это НОД. Метод работает быстро даже для больших чисел.
- Для трёх и более чисел сводите последовательно: НОД(12, 18, 24) = НОД(НОД(12, 18), 24) = НОД(6, 24) = 6. Порядок не важен — результат один и тот же.
Пример. НОД(48, 36) = 12: 48 ÷ 12 = 4, 36 ÷ 12 = 3, ни на какое большее число оба не делятся. НОД(15, 28) = 1 — числа взаимно простые, общих делителей кроме единицы нет. НОД(100, 250, 75) = 25 — цифры общего кратного разряда.
Что важно. НОД пригодится, чтобы сократить дробь до несократимой (разделите числитель и знаменатель на их НОД), упростить пропорцию или разложить набор предметов на равные группы. Если НОД равен 1 — числа взаимно просты, дробь уже несократима. Для двух чисел алгоритм Евклида делает 30–40 шагов даже для миллиардных значений — это самый быстрый способ.
Частые вопросы
Как найти НОД двух чисел вручную?
Самый быстрый способ — алгоритм Евклида: большее число делим на меньшее с остатком, потом меньшее делим на остаток, и так до нулевого остатка. Последний ненулевой остаток и есть НОД. Пример для 60 и 48: 60 mod 48 = 12; 48 mod 12 = 0 — значит, НОД = 12. Второй способ — разложение на простые множители: 60 = 2²·3·5, 48 = 2⁴·3, общие множители в минимальных степенях: 2² и 3, итого НОД = 4·3 = 12. Оба способа дают одинаковый ответ, но алгоритм Евклида короче для больших чисел.
Что такое НОД(12, 18) и почему он равен 6?
НОД(12, 18) = 6, потому что 6 — самое большое число, на которое делятся и 12, и 18 без остатка. Делители 12: 1, 2, 3, 4, 6, 12. Делители 18: 1, 2, 3, 6, 9, 18. Общие делители: 1, 2, 3, 6 — наибольший из них 6. По алгоритму Евклида это находится за один шаг: 18 mod 12 = 6, 12 mod 6 = 0 — НОД = 6. Этот результат нужен, чтобы сократить дробь 12/18: делим числитель и знаменатель на 6 → получаем 2/3.
Что если НОД двух чисел равен 1?
Числа с НОД = 1 называют взаимно простыми — у них нет общих делителей, кроме единицы. Примеры: 7 и 15, 8 и 9, 25 и 36. Взаимно простыми могут быть и составные числа (25 = 5² и 36 = 2²·3² не имеют общих простых множителей). Дроби с таким числителем и знаменателем не сокращаются: 7/15, 25/36 — уже несократимы. В этом случае НОК двух чисел равен их произведению: НОК(7, 15) = 105. Для расчёта НОК есть режим НОК онлайн.
Работает ли НОД для отрицательных чисел?
Да, но по определению НОД всегда неотрицателен — знак чисел не влияет на результат. НОД(−12, 18) = НОД(12, 18) = 6. НОД(−24, −36) = 12. Это следует из того, что если число делится на d без остатка, то и противоположное делится на d без остатка. Отдельный случай — ноль: НОД(a, 0) = |a| для любого ненулевого a, потому что 0 делится на любое число. НОД(0, 0) не определён — обычно калькулятор в этом случае выдаёт ошибку или считает по договорённости равным 0.