НОД и НОК: как найти наибольший общий делитель и наименьшее кратное
НОД нужен для сокращения дробей, НОК — для приведения к общему знаменателю. Оба находятся через разложение на простые множители.
Через разложение на множители
НОД — произведение общих множителей в наименьшей степени. НОК — произведение всех множителей в наибольшей степени.
Пример: 24 и 36. 24 = 2 · 2 · 2 · 3 36 = 2 · 2 · 3 · 3 Общие: 2 · 2 · 3 = 12, это НОД. Все: 2 · 2 · 2 · 3 · 3 = 72, это НОК.
Алгоритм Евклида — быстрее для больших чисел
Делим большее на меньшее с остатком, потом делитель на остаток, и так пока остаток не станет нулём. Последний ненулевой остаток и есть НОД.
НОД(48, 18): 48 = 18 · 2 + 12 18 = 12 · 1 + 6 12 = 6 · 2 + 0 НОД = 6
Связь НОД и НОК
НОД(a, b) · НОК(a, b) = a · b
Значит, найдя одно, второе можно получить делением: НОК = a · b / НОД
Для 24 и 36: НОК = 24 · 36 / 12 = 72. Сходится.
Где применяется
НОД — для сокращения дробей: 24/36 сокращаем на НОД 12, получаем 2/3.
НОК — для сложения дробей: чтобы сложить 1/24 и 1/36, приводим к знаменателю 72.
Частые вопросы
Чему равен НОД взаимно простых чисел?
Единице. Например, НОД(8, 15) = 1 — общих делителей, кроме 1, у них нет.