Наименьшее общее кратное и его применение¶

Наименьшее общее кратное (НОК) двух или нескольких целых чисел — это наименьшее положительное целое число, которое делится без остатка на каждое из этих чисел. НОК является одним из базовых понятий элементарной теории чисел наряду с наибольшим общим делителем (НОД) и широко применяется при работе с дробями, в задачах на периодичность, в криптографии и в программировании. Для целых чисел \(a\) и \(b\) наименьшее общее кратное обычно обозначается \(\operatorname{lcm}(a, b)\) (от англ. least common multiple) или \([a, b]\).

¶Определение и основные свойства

Формально НОК чисел \(a_1, a_2, \dots, a_n\) определяется как наименьшее положительное число \(m\), такое что \(m\) делится на каждое из \(a_i\) без остатка. Для двух чисел справедливо фундаментальное соотношение, связывающее НОК и НОД:

\[ \operatorname{lcm}(a, b) = \frac{|a \cdot b|}{\gcd(a, b)} \]

где \(\gcd(a, b)\) — наибольший общий делитель. Из этой формулы следуют важные свойства:

• НОК всегда существует для любого конечного набора ненулевых целых чисел.
• Если числа взаимно просты (их НОД равен 1), то их НОК равен их произведению.
• НОК не меньше каждого из чисел набора и не больше их произведения.
• \(\operatorname{lcm}(a, b) = \operatorname{lcm}(b, a)\) — операция коммутативна, а также ассоциативна, что позволяет распространять её на любое число аргументов.

¶Способы вычисления

¶Разложение на простые множители

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

• \(12 = 2^2 \cdot 3\)
• \(18 = 2 \cdot 3^2\)

НОК равен \(2^2 \cdot 3^2 = 36\). Этот метод нагляден, но требует факторизации, что для больших чисел вычислительно затратно.

¶Через наибольший общий делитель

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

¶Последовательное вычисление

Для набора из нескольких чисел НОК вычисляется пошагово:

\[ \operatorname{lcm}(a, b, c) = \operatorname{lcm}(\operatorname{lcm}(a, b), c) \]

Такой приём позволяет свести задачу к многократному применению формулы для двух чисел.

¶Применение

¶Арифметика дробей

Наиболее распространённое применение НОК — приведение дробей к общему знаменателю. Чтобы сложить или вычесть дроби с разными знаменателями, необходимо найти их наименьший общий знаменатель, который равен НОК исходных знаменателей. Например, для \(\frac{5}{12} + \frac{7}{18}\) общий знаменатель равен 36, что даёт \(\frac{15}{36} + \frac{14}{36} = \frac{29}{36}\). Использование именно наименьшего общего знаменателя упрощает вычисления и сокращает промежуточные числа.

¶Задачи на периодичность и синхронизацию

Если два события повторяются с периодами \(a\) и \(b\), то момент их одновременного наступления определяется НОК этих периодов. Классический пример — задача о двух автобусах, отправляющихся от остановки с интервалами 12 и 18 минут: они встретятся вновь через 36 минут. Аналогично решаются задачи о вращающихся шестернях, совпадении стрелок часов, расписаниях и циклических процессах.

¶Дискретная математика и программирование

В программировании НОК применяется при работе с массивами, синхронизацией потоков, планированием задач и в алгоритмах, связанных с периодическими структурами. Типовая реализация на языках программирования опирается на формулу через НОД:

`` lcm(a, b) = a / gcd(a, b) * b ``

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

¶Теория чисел и криптография

НОК используется в теореме о китайской теореме об остатках, при анализе мультипликативных групп вычетов, в построении циклических подгрупп. В ряде криптографических схем (например, в алгоритме RSA при генерации ключей) фигурирует функция Кармайкла, тесно связанная с НОК и определяющая наименьший универсальный показатель степени для группы.

¶Музыка и теория ритма

В музыкальной теории НОК применяется для определения наименьшего общего периода полиритмических фигур. Если один инструмент играет с ритмическим делением на 3, а другой — на 4, полный цикл совпадения составит 12 долей.

¶Примеры

¶Связь с другими понятиями

НОК и НОД образуют двойственную пару в решётке делимости: НОД соответствует точной нижней грани, а НОК — точной верхней грани множества чисел, упорядоченных по делимости. Это делает их частным случаем общих алгебраических конструкций — решёток и булевых алгебр. В кольце целых чисел НОК всегда существует, поскольку \(\mathbb{Z}\) является областью с однозначным разложением на множители. В более общих кольцах (например, в кольце многочленов над полем) понятие НОК также определено и играет аналогичную роль.

¶Обобщения

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