Наименьшее общее кратное трёх чисел

Что такое НОК трёх чисел

Наименьшее общее кратное трёх чисел — это наименьшее натуральное число, которое делится на каждое из них без остатка. Оно существует всегда: произведение трёх чисел уже само является общим кратным, — и никогда не бывает меньше наибольшего из них.

Откуда берётся формула

Любое целое число больше единицы раскладывается в произведение простых, причём единственным способом. Число делится на a ровно тогда, когда содержит каждый простой множитель числа a не меньше раз, чем содержит его само a. Чтобы делиться сразу на все три, число обязано содержать каждый простой множитель в наибольшей из трёх степеней — а если взять ровно столько и не больше, оно и окажется наименьшим таким числом.

У формулы для двух чисел — НОК(a, b) = a × b ÷ НОД(a, b) — нет аналога для трёх. Для 4, 6 и 10 произведение равно 240, наибольший общий делитель равен 2, и 240 ÷ 2 = 120, тогда как настоящий НОК равен 60: у трёх чисел общий простой множитель вычитается больше одного раза.

Как считать: три шага

1. Разложите все три числа на простые множители, например 12 = 2² × 3, 18 = 2 × 3² и 30 = 2 × 3 × 5.
2. Для каждого простого множителя, встречающегося хотя бы в одном числе, оставьте наибольшую степень: 2², 3² и 5.
3. Перемножьте эти наибольшие степени: 4 × 9 × 5 = 180. Это и есть наименьшее общее кратное.

Разложение против попарного хода: разбор на одном примере

К одному и тому же ответу ведут два пути, и их стоит увидеть рядом на числах 12, 18 и 30. Первый раскладывает степени простых в таблицу и читает максимум каждого столбца:

Второй путь не раскладывает ничего. Он опирается на ассоциативность — НОК(a, b, c) = НОК(НОК(a, b), c) — и дважды применяет формулу для двух чисел:

Какой путь выбрать — вопрос чисел, а не вкуса. Таблица быстрее, пока разложения видны глазом, и вдобавок показывает, почему ответ именно такой. Попарный ход остаётся быстрым и на числах, раскладывать которые уже неподъёмно: наибольший общий делитель там находит алгоритм Евклида, который только делит с остатком и ничего не факторизует.

Ходовые тройки и их НОК

Где три числа встречаются на практике

• Сложение трёх дробей — общий знаменатель для 1/6 + 1/8 + 1/9 это НОК чисел 6, 8 и 9, то есть 72
• Повторяющиеся расписания — три автобуса с интервалами 12, 18 и 30 минут снова сойдутся через 180 минут
• Шестерни и ремни — три колеса с 12, 18 и 30 зубьями вернутся в исходное положение через 180 шагов
• Раскрой и упаковка — наименьший квадрат, который без остатка выкладывается полосами 12 см, 18 см и 30 см, имеет сторону 180 см
• Модульная арифметика — период трёх одновременно идущих циклов равен НОК их длин
• Школьные задачи — «найдите наименьшее число, делящееся на 3, 4 и 5» — это дословно данное вычисление

Границы применимости и оговорки

• Порядок чисел не важен. НОК(3, 4, 5), НОК(5, 3, 4) и НОК(4, 5, 3) — одно и то же число 60, поэтому у калькулятора одна страница на неупорядоченную тройку.
• Единица не меняет ничего — на 1 делится любое целое, поэтому НОК(1, 2, 3) = НОК(2, 3) = 6.
• Повтор тоже ничего не меняет — уже учтённая степень простого множителя второй раз не учитывается: НОК(2, 4, 4) = НОК(2, 4) = 4.
• Попарная взаимная простота — не то же самое, что взаимная простота в совокупности. У 6, 10 и 15 нет множителя, общего сразу для всех трёх, но у каждой пары он есть — и НОК равен 30, а не 900.
• Ответ растёт очень быстро. Три числа около миллиарда дают НОК из 27 цифр — поэтому страница держит его точным целым и никогда не числом с плавающей точкой.