Наименьшее общее кратное (НОК): как найти

Начнём с простого. Допустим, конфеты продаются в пачках по 4 штуки. Сколько конфет ты можешь купить? $4$, $8$, $12$, $16$, $20$... — только числа, которые делятся на 4. Такие числа называют кратными числа 4.

Кратное числа $a$ — это любое натуральное число, которое делится на $a$ без остатка. Здесь $a$ — просто буква, обозначающая любое число. Все кратные получаются умножением: $a\cdot 1$, $a\cdot 2$, $a\cdot 3$ и так далее — поэтому их бесконечно много.

Выпишем кратные двух чисел:

• кратные числа 4: $4,8,12,16,20,24,\dots$
• кратные числа 6: $6,12,18,24,30,\dots$

Видишь числа, которые попали в оба списка? Это $12,24,36,\dots$ — их называют общими кратными чисел 4 и 6. Их тоже бесконечно много, но среди них всегда есть самое маленькое. Вот оно-то нам и нужно!

Наименьшее общее кратное (коротко — НОК) нескольких чисел — это самое маленькое натуральное число, которое делится на каждое из них. Записывают так: $\text{НОК}(a,b)$, где $a$ и $b$ — наши числа.

В примере выше $\text{НОК}(4,6)=12$: число 12 делится и на 4, и на 6, и меньше такого числа не найти.

Полезные факты про НОК:

1. НОК не бывает меньше самого большого из чисел: $\text{НОК}(a,b)\ge \max (a,b)$. Тут $\max$ — это просто «наибольшее из» (от слова «максимум»). Логично: НОК должен делиться на большое число, значит, он хотя бы такой же.
2. Если одно число делится на другое — НОК равен большему. Например, $\text{НОК}(12,4)=12$: ведь 12 уже делится и на 12, и на 4. Искать дальше нечего!
3. Порядок не важен: $\text{НОК}(a,b)=\text{НОК}(b,a)$.
4. У НОК есть «брат» — НОД, наибольший общий делитель. Они связаны красивой формулой: $\text{НОК}(a,b)\cdot \text{НОД}(a,b)=a\cdot b$. Перемножь НОК и НОД — получишь произведение самих чисел.

Самый простой способ для небольших чисел. Выписываем кратные большего числа по порядку и каждый раз проверяем, делится ли оно на меньшее. Первое подходящее число и есть НОК.

Пример. Найдём $\text{НОК}(6,8)$. Кратные 8: $8$ (на 6 не делится), $16$ (не делится), $24$ (делится: $24:6=4$). Значит, $\text{НОК}(6,8)=24$.

Почему начинаем с большего числа? Его кратные идут реже, поэтому шагов меньше. Для 6 и 8 хватило трёх шагов, а по кратным 6 пришлось бы дойти до четвёртого.

Для больших чисел, например 84 и 90, перебор затянется. Тогда выручает разложение на простые множители.

Это главный способ — работает с любыми числами, даже большими.

Пример. Найдём $\text{НОК}(12,18)$.

$12=2^2\cdot 318=2\cdot 3^2$ Двойка встречается в степенях $2$ и $1$ — берём $2^2$. Тройка встречается в степенях $1$ и $2$ — берём $3^2$. Перемножаем:

$\text{НОК}(12,18)=2^2\cdot 3^2=4\cdot 9=36$

Почему именно наибольшая степень? НОК обязан делиться на оба числа. Чтобы делиться на 12, внутри НОК должны «сидеть» две двойки и одна тройка. Чтобы делиться на 18 — одна двойка и две тройки. Берём по максимуму из обоих требований: две двойки и две тройки. Если взять меньше — на одно из чисел НОК делиться перестанет.

Если ты уже нашёл НОД двух чисел (наибольший общий делитель), НОК вычисляется в одно действие:

$\text{НОК}(a,b)=\frac{a\cdot b}{\text{НОД}(a,b)}$ Откуда это берётся? Из свойства $\text{НОК}(a,b)\cdot \text{НОД}(a,b)=a\cdot b$: просто делим обе части на НОД.

Пример. Снова найдём $\text{НОК}(12,18)$, но по-новому. НОД чисел 12 и 18 равен 6 (это самое большое число, на которое делятся оба). Тогда:

$\text{НОК}(12,18)=\frac{12\cdot 18}{6}=\frac{216}{6}=36$ Тот же ответ — способы дружат между собой.

Когда выбирать этот способ? Когда НОД виден сразу или уже посчитан — тогда выйдет быстрее, чем раскладывать. А если чисел три или больше, действуй по шагам: сначала найди НОК первых двух, потом НОК результата с третьим числом, и так далее.

Бывают числа-«незнакомцы»: у них нет ни одного общего делителя, кроме единицы. Такие числа называют взаимно простыми — их НОД равен 1. Например, 8 и 15: у восьмёрки делители $1,2,4,8$, у пятнадцати — $1,3,5,15$. Общая только единица.