Что это и что показывает
НОД (наибольший общий делитель) двух чисел — самое большое число, на которое оба делятся без остатка. НОК (наименьшее общее кратное) — наименьшее число, которое делится на оба. Калькулятор находит обе величины: НОД нужен для сокращения дробей, НОК — для приведения дробей к общему знаменателю.
Формула и откуда она
НОД находят алгоритмом Евклида: НОД(a, b) = НОД(b, a mod b), повторяя, пока второе число не станет нулём; тогда первое — это НОД. Идея: общий делитель чисел a и b делит и их остаток, поэтому замена пары (a, b) на (b, остаток) сохраняет НОД, но уменьшает числа.
НОК выражается через НОД: НОК(a, b) = a · b / НОД(a, b). Это работает, потому что произведение a·b учитывает каждый общий простой множитель дважды, а деление на НОД убирает лишнюю копию.
Как посчитать вручную (по шагам)
- Возьмите большее число
aи меньшееb. - Найдите остаток от деления
aнаb. - Замените пару: новое
a = b, новоеb = остаток. - Повторяйте, пока остаток не станет 0; последний ненулевой делитель — это НОД.
- Для НОК умножьте исходные числа и разделите на найденный НОД.
Разбор примера
Найдём НОД и НОК чисел 48 и 36.
Алгоритм Евклида: 48 mod 36 = 12 → 36 mod 12 = 0. Остаток ноль, значит НОД(48, 36) = 12.
НОК: НОК = 48 · 36 / 12 = 1728 / 12 = 144.
Проверка: 144 / 48 = 3 и 144 / 36 = 4 — оба делятся нацело ✓.
Где применяется
НОД сокращает дроби (36/48 = 3/4 после деления на 12), НОК даёт общий знаменатель при сложении дробей. В задачах ОГЭ это «через сколько дней события совпадут» (НОК) и распределение поровну (НОД). В программировании алгоритм Евклида — классика. В IB и AP — основа теории чисел, простых множителей и работы с рациональными выражениями.
Частые ошибки
- Путают НОД и НОК: НОД ≤ меньшего числа, НОК ≥ большего.
- В алгоритме Евклида берут частное вместо остатка.
- Считают НОК как простое произведение
a·b, забывая разделить на НОД. - Останавливают алгоритм при остатке 1, хотя НОД тогда равен 1 (числа взаимно простые) — это валидный ответ.