В арифметике и теории чисел наименьшее общее кратное, наименьшее общее кратное или наименьшее общее кратное двух целых чисел a и b, обычно обозначаемых lcm (a, b) - наименьшее положительное целое число, которое делится на как на a, так и на b. Поскольку деление целых чисел на ноль не определено, это определение имеет смысл, только если a и b оба отличны от нуля. Однако некоторые авторы определяют lcm (a, 0) как 0 для всех a, что является результатом принятия lcm как наименьшей верхней границы в решетке делимости.
lcm - это «наименьший общий знаменатель » (lcd), который можно использовать перед тем, как дроби можно будет сложить, вычесть или сравнить. Lcm более двух целых чисел также четко определено: это наименьшее положительное целое число, которое делится на каждое из них.
A кратное числа - это произведение этого числа на целое число. Например, 10 делится на 5, потому что 5 × 2 = 10, поэтому 10 делится на 5 и 2. Поскольку 10 - это наименьшее положительное целое число, которое делится как на 5, так и на 2, оно является наименьшим общим кратным 5 и 2. По тому же принципу, 10 также является наименьшим общим кратным −5 и −2.
Наименьшее общее кратное двух целых чисел a и b обозначается как lcm (a, b). В некоторых старых учебниках используется [a, b], а в языке программирования J используется a *.b
.
Умножение на 4:
Кратное 6:
Общие кратные 4 и 6 числа есть в обоих списках:
В этом списке наименьшее число - 12, следовательно, наименьшее общее кратное - 12.
При сложении, вычитании или сравнении простых дробей используется наименьшее общее кратное знаменателей (часто называемое наименьшим общим знаменателем ), поскольку каждая из дробей может быть выражается в виде дроби с этим знаменателем. Например,
где был использован знаменатель 42, потому что это наименьшее общее кратное 21 и 6.
Предположим, есть два зацепляющие шестерни в машине, имеющие m и n зубьев, соответственно, и шестерни отмечены отрезком линии, проведенным от центра первой шестерни к центру второй шестерни. Когда шестерни начинают вращаться, количество оборотов, которые должна выполнить первая шестерня, чтобы перестроить сегмент линии, можно рассчитать с помощью . Первая передача должна совершить оборотов для перенастройки. К этому времени вторая шестерня совершит оборотов.
Предположим, что вокруг звезды вращаются три планеты, которым требуется l, m и n единиц времени, соответственно, для завершения своего обращения. Предположим, что l, m и n - целые числа. Если предположить, что планеты начали движение вокруг звезды после начального линейного выравнивания, все планеты снова достигают линейного выравнивания после единиц времени. В это время первая, вторая и третья планеты завершили , и соответственно вращается вокруг звезды.
Следующая формула сводит проблему вычисления наименьшего общего кратного к проблеме вычисления наибольшего общего делителя (gcd), также известного как наибольший общий делитель:
Эта формула также действительна, когда ровно одно из и b равно 0, поскольку gcd (a, 0) = | a |. Однако, если и a, и b равны 0, эта формула вызовет деление на ноль ; lcm (0, 0) = 0 - особый случай.
Существуют быстрые алгоритмы для вычисления gcd, не требующие факторизации чисел, например, алгоритм Евклида. Чтобы вернуться к приведенному выше примеру,
Поскольку gcd (a, b) является делителем как a, так и b, более эффективно вычислять lcm путем деления перед умножением:
Это уменьшает размер одного ввода как для деления, так и для умножения, а также уменьшает необходимое хранилище, необходимое для промежуточных результатов (то есть переполнение в вычисление a × b). Поскольку gcd (a, b) является делителем как a, так и b, деление гарантированно дает целое число, поэтому промежуточный результат может быть сохранен в виде целого числа. Реализованный таким образом предыдущий пример выглядит следующим образом:
Теорема уникальности факторизации указывает, что любое положительное целое число больше 1 может быть записано только в в одну сторону как произведение простых чисел. Простые числа можно рассматривать как атомарные элементы, которые при объединении составляют составное число.
. Например:
Здесь получается составное число 90 состоит из одного атома простого числа 2, двух атомов простого числа 3 и одного атома простого числа 5.
Этот факт можно использовать для определения lcm набора чисел.
Пример: lcm (8,9,21)
Разложите каждое число на множители и выразите его как произведение простого числа степени.
lcm будет произведением наивысшей степени каждого простого числа вместе. Наивысшая степень трех простых чисел 2, 3 и 7 равна 2, 3 и 7 соответственно. Таким образом,
Этот метод не так эффективен, как приведение к наибольшему общему делителю, так как нет известный общий эффективный алгоритм для целочисленной факторизации.
Тот же метод можно также проиллюстрировать с помощью диаграммы Венна, как показано ниже, с простой факторизацией каждого из двух чисел. в каждом круге и всех общих факторах на пересечении. Тогда lcm можно найти, умножив все простые числа на диаграмме.
Вот пример:
совместное использование двух " Общие 2 "s и" 3 ":
Это также работает для наибольшего общего делителя (НОД), за исключением того, что вместо умножения всех чисел на диаграмме Венна умножаются только простые множители, находящиеся на пересечении. Таким образом, НОД 48 и 180 равно 2 × 2 × 3 = 12.
Этот метод легко работает для нахождения lcm нескольких целых чисел.
Пусть имеется конечная последовательность натуральных чисел X = (x 1, x 2,..., x n), n>1. Алгоритм работает по шагам следующим образом: на каждом шаге m он проверяет и обновляет последовательность X = (x 1, x 2,..., x n), X = X, где X - m-я итерация X, то есть X на шаге m алгоритма и т. Д. Цель проверки - выбрать наименьший (возможно, один из многих) элемент последовательности X. Предполагая, что x k0является выбранным элементом, последовательность X определяется как
Другими словами, наименьший элемент увеличивается на соответствующий x, тогда как остальные элементы переходят от X к X без изменений.
Алгоритм останавливается, когда все элементы в последовательности X равны. Их обычное значение L равно 1 см (X).
Например, если X = X = (3, 4, 6), шаги алгоритма производят:
Этот метод работает для любого количества чисел. Первый начинается с перечисления всех чисел по вертикали в таблице (в этом примере 4, 7, 12, 21 и 42):
Процесс начинается с деления всех чисел на 2. Если 2 делит любое из них на равные части, запишите 2 в новом столбце вверху таблицы и результат деления на 2 каждого числа в пространстве справа в этом новом столбце. Если число не делится без остатка, просто перепишите его заново. Если 2 не делится равномерно ни на одно из чисел, повторите эту процедуру со следующим по величине простым числом, 3 (см. Ниже).
x | 2 |
---|---|
4 | 2 |
7 | 7 |
12 | 6 |
21 | 21 |
42 | 21 |
Теперь, предполагая, что 2 действительно делило по крайней мере одно число (как в этом примере), проверьте, есть ли 2 снова делится:
x | 2 | 2 |
---|---|---|
4 | 2 | 1 |
7 | 7 | 7 |
12 | 6 | 3 |
21 | 21 | 21 |
42 | 21 | 21 |
Один раз 2 больше не делит любое число в текущем столбце, повторите процедуру, разделив на следующее большее простое число, 3. Как только 3 больше не делится, попробуйте следующие большие простые числа, 5, затем 7 и т. д. Процесс заканчивается, когда все числа были уменьшены до 1 (столбец под последним простым делителем состоит только из единиц).
x | 2 | 2 | 3 | 7 |
---|---|---|---|---|
4 | 2 | 1 | 1 | 1 |
7 | 7 | 7 | 7 | 1 |
12 | 6 | 3 | 1 | 1 |
21 | 21 | 21 | 7 | 1 |
42 | 21 | 21 | 7 | 1 |
Теперь умножьте числа в верхний ряд для получения lcm. В данном случае это 2 × 2 × 3 × 7 = 84.
Как общий вычислительный алгоритм, описанный выше довольно неэффективен. Никогда бы не захотелось реализовать это в программном обеспечении: это требует слишком много шагов и требует слишком много места для хранения. Гораздо более эффективный численный алгоритм может быть получен путем использования алгоритма Евклида для вычисления сначала НОД, а затем получения НКМ путем деления.
Согласно основной теореме арифметики, положительное целое число является произведением простых чисел, и это представление уникально с точностью до порядка простых чисел:
где показатели n 2, n 3,... - неотрицательные целые числа; например, 84 = 2 3 5 7 11 13...
Даны два целых положительных числа и их наименьшее общее кратное и Наибольший общий делитель дается формулой
и
Поскольку
это дает
Фактически, каждое рациональное число может быть однозначно записано как произведение простых чисел, если отрицательные показатели разрешается. Когда это будет сделано, приведенные выше формулы останутся в силе. Например:
Положительные целые числа могут быть частично упорядочены по делимости: если a делит b (то есть, если b является целым числом, кратным числа a), напишите a ≤ b (или, что эквивалентно, b ≥ a). (Обратите внимание, что обычное определение ≤, основанное на величине, здесь не используется.)
При таком порядке положительные целые числа становятся решеткой, где соответствует, заданному формулой gcd и соединяют, заданные lcm. Доказательство простое, хотя и немного утомительное; это равносильно проверке того, что lcm и gcd удовлетворяют аксиомам встречи и соединения. Включение lcm и gcd в этот более общий контекст устанавливает двойственность между ними:
Следующие пары двойственных формул являются частными случаями общих теоретико-решеточных тождеств.
Также можно показать, что эта решетка дистрибутивна ; то есть lcm распределяется по gcd, а gcd распределяется по lcm:
Это тождество самодвойственный:
Тогда
где абсолютные черты || обозначают мощность множества.
Наименьшее общее кратное в общем случае может быть определено над коммутативными кольцами следующим образом: Пусть a и b элементы коммутативного кольца R. Общее кратное aa nd b - это элемент m из R такой, что как a, так и b делят m (то есть существуют элементы x и y из R такие, что ax = m и by = m). Наименьшее общее кратное для a и b является минимальным общим кратным в том смысле, что для любого другого общего кратного n для a и b, m делит n.
В общем, два элемента в коммутативном кольце не могут иметь наименьшего общего кратного или иметь более одного. Однако любые два наименьших общих кратных одной и той же пары элементов являются ассоциированными. В уникальной области факторизации любые два элемента имеют наименьшее общее кратное. В области главных идеалов наименьшее общее кратное a и b может быть охарактеризовано как генератор пересечения идеалов, порожденных a и b (пересечение набора идеалов всегда является идеалом).