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

Что считает калькулятор

Введите два или больше натуральных чисел — калькулятор сразу выдаст:

• НОД — наибольший общий делитель: самое большое число, на которое все введённые числа делятся без остатка;
• НОК — наименьшее общее кратное: самое маленькое число, которое делится на каждое из введённых.

Числа можно разделять пробелом, запятой, точкой с запятой или переносом строки. Годятся только целые числа больше нуля.

НОД и алгоритм Евклида

Наибольший общий делитель удобнее всего искать алгоритмом Евклида: большее число делят на меньшее с остатком, затем меньшее — на остаток, и так пока остаток не станет нулём. Последний ненулевой делитель и есть НОД.

НОД(48, 18):
48 = 18 × 2 + 12
18 = 12 × 1 + 6
12 = 6 × 2 + 0   →  НОД = 6

Этот способ не требует раскладывать числа на простые множители и работает мгновенно даже для очень больших чисел.

НОК через НОД

Наименьшее общее кратное двух чисел выражается через их НОД:

НОК(a, b) = a · b / НОД(a, b)

Например, НОК(48, 18) = 48 · 18 / 6 = 144. Для списка из нескольких чисел и НОД, и НОК считаются попарно: берут первые два, затем результат комбинируют со следующим числом, и так далее.

Где это нужно

• Сложение дробей — общий знаменатель удобно брать как НОК знаменателей.
• Сокращение дробей — числитель и знаменатель делят на их НОД.
• Задачи на периодичность — «через сколько дней события совпадут снова» решается через НОК периодов.
• Распределение поровну — на сколько одинаковых групп можно разбить наборы, считается через НОД.

Связь НОД и НОК

Для любой пары чисел произведение их НОД и НОК равно произведению самих чисел:

НОД(a, b) · НОК(a, b) = a · b

Калькулятор показывает эту проверку для пары чисел — удобно убедиться, что расчёт верный.