Калькулятор НОД и НОК
Расчёт наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК) для двух и более целых чисел онлайн — с простым разложением и алгоритмом Евклида.
Выберите операцию
Как считаем
Наибольший общий делитель — НОД(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 шагов даже для миллиардных значений — это самый быстрый способ.
Наименьшее общее кратное — НОК(12, 18) = 36
Обозначения. НОК(a, b, …) — наименьшее натуральное число, которое делится на каждое из данных без остатка. По-английски — lcm (least common multiple). Как и НОД, определён для положительных целых. Между НОД и НОК есть связь: a × b = НОД(a, b) × НОК(a, b) — этой формулой и пользуется калькулятор.
Формула: НОК(a, b) = |a × b| ÷ НОД(a, b); НОК(a, b, c) = НОК(НОК(a, b), c)
Как посчитать пошагово.
- Найдите НОД пары чисел (алгоритм Евклида — сверху). Для 12 и 18 НОД = 6.
- Перемножьте пару и разделите на НОД: 12 × 18 ÷ 6 = 216 ÷ 6 = 36. Это и есть НОК.
- Для трёх и более чисел сводите последовательно: НОК(12, 18, 24) = НОК(НОК(12, 18), 24) = НОК(36, 24) = 72.
Пример. НОК(4, 6) = 12: и 4, и 6 делят 12 (12 ÷ 4 = 3, 12 ÷ 6 = 2), меньшего общего кратного нет. НОК(7, 5) = 35 — для взаимно простых чисел НОК равен их произведению. НОК(10, 20, 25) = 100 — минимальное число, делящееся на все три.
Что важно. НОК нужен, когда надо привести дроби к общему знаменателю (общий знаменатель = НОК исходных знаменателей — минимальный, дальше делить нечего). Или найти момент, когда события снова совпадут: если два поезда отправляются раз в 12 и 18 минут, оба одновременно уйдут через НОК(12, 18) = 36 минут. При очень больших числах произведение a × b может превысить 10¹⁸, но алгоритм всё равно работает — калькулятор использует арифметику произвольной точности.
Частые вопросы
Чем НОД отличается от НОК?
НОД (наибольший общий делитель) — самое большое число, на которое делятся оба числа без остатка. НОК (наименьшее общее кратное) — самое маленькое число, которое делится на оба без остатка. Пример: для 12 и 18 НОД = 6 (это максимальное число-делитель обоих), а НОК = 36 (это минимальное число, кратное обоим). Связаны формулой: a·b = НОД(a,b)·НОК(a,b). НОД используют при сокращении дробей, НОК — при приведении дробей к общему знаменателю. Работа с дробями — в калькуляторе дробей.
Что такое алгоритм Евклида и как он работает?
Алгоритм Евклида — самый быстрый способ найти НОД двух чисел. Идея: НОД(a, b) = НОД(b, a mod b), то есть большее число заменяем остатком от его деления на меньшее и повторяем, пока остаток не станет нулём. Последний ненулевой остаток и есть НОД. Пример для 48 и 18: 48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0 — значит, НОД = 6. Работает за считанные шаги даже для очень больших чисел, поэтому применяется в криптографии (например, в RSA). Изучают в школе в 6 классе.
Как найти НОК через НОД?
По формуле: НОК(a, b) = a·b / НОД(a, b). Пример для 4 и 6: НОД = 2, поэтому НОК = 4·6/2 = 12. Для 12 и 18: НОД = 6, НОК = 12·18/6 = 36. Формула работает всегда и она быстрее, чем перебор кратных. Для трёх и более чисел применяется последовательно: сначала НОК первой пары, потом НОК полученного результата и следующего числа — и так до конца списка. Порядок значения не имеет: НОК(a, b, c) = НОК(НОК(a, b), c).
Зачем НОД нужен при сокращении дробей?
Дробь сокращается делением числителя и знаменателя на их НОД — за один шаг до несократимого вида. Пример: 18/24. НОД(18, 24) = 6, значит 18/24 = (18/6) / (24/6) = 3/4. Если делить на общий делитель меньше НОД, придётся сокращать несколько раз: 18/24 → 9/12 → 3/4. НОД = 1 у взаимно простых чисел (например, 7 и 15) — такая дробь уже несократима. Готовое сокращение дробей — в калькуляторе дробей.
Можно ли считать НОД и НОК для трёх и более чисел?
Да, обе операции ассоциативны — считаются последовательно. НОД(a, b, c) = НОД(НОД(a, b), c). Пример: НОД(12, 18, 24). Сначала НОД(12, 18) = 6, потом НОД(6, 24) = 6 — ответ. Аналогично НОК(4, 6, 8): НОК(4, 6) = 12, НОК(12, 8) = 24. Такой расчёт нужен при приведении трёх и более дробей к общему знаменателю или при планировании циклических событий (когда несколько процессов с разными периодами совпадут в одной точке). Порядок чисел не важен — результат один и тот же.