НОД и НОК

Q: Зачем связаны НОД и НОК?

Произведение НОД и НОК двух чисел равно их произведению: НОД(a,b)·НОК(a,b)=a·b . Поэтому НОК легко найти как a·b/НОД(a,b) , не раскладывая на множители.

GCD & LCM

Наибольший общий делитель и наименьшее общее кратное.

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

Что считает: НОД (наибольший общий делитель) двух чисел — самое большое число, на которое оба делятся без остатка. НОК (наименьшее общее кратное) — наименьшее число, которое делится на оба. Калькулятор находит обе величины: НОД нужен для сокращения дробей, НОК — для приведения дробей к общему знаменателю.
Раздел: ∑ Математика
Что на выходе: Результат + формула + пошаговое решение + разбор примера
Стоимость: Бесплатно, без регистрации, прямо в браузере

Как это работает

НОД находится алгоритмом Евклида, НОК — через НОК(a,b)=a·b/НОД(a,b).

Что это и что показывает

Формула и откуда она

НОД находят алгоритмом Евклида: НОД(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 (числа взаимно простые) — это валидный ответ.

Частые вопросы

Как работает алгоритм Евклида?

Большее число заменяют на остаток от его деления на меньшее и повторяют, пока остаток не станет нулём. Последний ненулевой остаток и есть НОД. Это намного быстрее перебора делителей.

Зачем связаны НОД и НОК?

Произведение НОД и НОК двух чисел равно их произведению: НОД(a,b)·НОК(a,b)=a·b. Поэтому НОК легко найти как a·b/НОД(a,b), не раскладывая на множители.

Чему равен НОД взаимно простых чисел?

Единице. Например, у 8 и 15 общих делителей, кроме 1, нет, поэтому НОД=1, а их НОК равен самому произведению — 120.

Где на практике нужны НОД и НОК?

НОД — чтобы сократить дробь до несократимой, НОК — чтобы привести дроби к общему знаменателю или найти, когда совпадут два периодических события.

Проекты сети