НОД и НОК

⭐ — формулы, которые чаще всего встречаются на экзамене.

Определения

• ⭐ НОД (наибольший общий делитель) — наибольшее натуральное число, на которое делятся все данные числа.
• ⭐ НОК (наименьшее общее кратное) — наименьшее натуральное число, которое делится на все данные числа.
• Если $\text{НОД}(a, b) = 1$, то $a$ и $b$ взаимно простые. Например, $\text{НОД}(8, 15) = 1$.

Способ разложения на простые множители

Раскладываем числа на простые множители:

• ⭐ НОД — произведение общих простых множителей в наименьших степенях.
• ⭐ НОК — произведение всех простых множителей в наибольших степенях.

Пример. $36 = 2^2 \cdot 3^2$ и $48 = 2^4 \cdot 3$.

$\text{НОД}(36, 48) = 2^2 \cdot 3 = 12 \qquad \text{НОК}(36, 48) = 2^4 \cdot 3^2 = 144$

Важная связь

• ⭐ Для двух чисел: $\text{НОД}(a, b) \cdot \text{НОК}(a, b) = a \cdot b$
• Проверка: $12 \cdot 144 = 1\,728 = 36 \cdot 48$ ✓
• Эта связь верна только для двух чисел; для трёх чисел она не работает.

Алгоритм Евклида (для НОД)

Делим $a$ на $b$ с остатком, затем $b$ на остаток, и так далее, пока остаток не станет равен нулю. Последний ненулевой остаток — НОД.

• $\text{НОД}(a, b) = \text{НОД}(b, r)$, где $r$ — остаток от деления $a$ на $b$.
• Пример: $\text{НОД}(84, 36)$: $84 = 2 \cdot 36 + 12$, $\; 36 = 3 \cdot 12 + 0$. Ответ: $12$.

Применение

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