Наименьший общий множитель - Least common multiple

А Диаграмма Венна показывает наименьшее общее кратное для комбинаций 2, 3, 4, 5 и 7 (6 пропускается, так как это 2 × 3, оба из которых уже представлены).
Например, для карточной игры, в которой карты должны быть разделены поровну между 5 игроками, требуется не менее 60 карт, число на пересечении 2, 3, 4 и 5 наборов, но не 7 наборов.

В арифметика и теория чисел, то наименьший общий множитель, наименьшее общее кратное, или же наименьшее общее кратное из двух целые числа а и б, обычно обозначаемый lcm (аб), является наименьшим положительным целым числом, которое делимый обоими а и б.[1][2][3] С деление целых чисел на ноль не определено, это определение имеет смысл, только если а и б оба отличны от нуля.[4] Однако некоторые авторы определяют lcm (а, 0) как 0 для всех а, что является результатом принятия lcm за наименьшая верхняя граница в решетка делимости.

Lcm - это "наименьший общий знаменатель "(ЖК-дисплей), который можно использовать перед фракции можно складывать, вычитать или сравнивать. Lcm более двух целых чисел также четко определено: это наименьшее положительное целое число, которое делится на каждое из них.[2]

Обзор

А несколько числа - это произведение этого числа на целое число. Например, 10 делится на 5, потому что 5 × 2 = 10, поэтому 10 делится на 5 и 2. Поскольку 10 - это наименьшее положительное целое число, которое делится как на 5, так и на 2, это наименьшее общее кратное 5 и 2. По тому же принципу, 10 также является наименьшим общим кратным −5 и −2.

Обозначение

Наименьшее общее кратное двух целых чисел а и б обозначается как lcm (а, б).[1][2] В некоторых старых учебниках используется [а, б],[4][5] а язык программирования J использует а * .b .

Пример

Кратное 4:

Кратное 6:

Общие кратные числа 4 и 6 находятся в обоих списках:

В этом списке наименьшее число - 12, поэтому наименьший общий множитель 12 лет.

Приложения

При добавлении, вычитании или сравнении простые дроби, наименьшее общее кратное знаменателей (часто называемое наименьший общий знаменатель ), потому что каждая дробь может быть выражена как дробь с этим знаменателем. Например,

где был использован знаменатель 42, так как это наименьшее общее кратное 21 и 6.

Проблема с шестернями

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

Планетарное выравнивание

Предположим, что вокруг звезды вращаются три планеты, которые л, м и п единиц времени, соответственно, чтобы завершить свои орбиты. Предположить, что л, м и п целые числа. Если предположить, что планеты начали двигаться вокруг звезды после первоначального линейного выравнивания, все планеты снова достигают линейного выравнивания после единиц времени. В это время первая, вторая и третья планеты будут завершены. , и орбиты соответственно вокруг звезды.[6]

Расчет

Использование наибольшего общего делителя

Следующая формула сводит проблему вычисления наименьшего общего кратного к проблеме вычисления наибольший общий делитель (НОД), также известный как наибольший общий фактор:

Эта формула также верна, когда ровно одно из а и б равно 0, так как gcd (а, 0) = |а|, Однако если оба а и б равны 0, эта формула вызовет деление на ноль; lcm (0, 0) = 0 - особый случай.

Есть быстрые алгоритмы для вычисления gcd, которые не требуют, чтобы числа были учтенный, такой как Евклидов алгоритм. Чтобы вернуться к приведенному выше примеру,

Поскольку gcd (а, б) является делителем обоих а и б, более эффективно вычислить НКМ, разделив перед умножение:

Это уменьшает размер одного ввода как для деления, так и для умножения, а также уменьшает требуемую память, необходимую для промежуточных результатов (то есть переполнение в а×б вычисление). Поскольку gcd (а, б) является делителем обоих а и б, при делении гарантированно будет целое число, поэтому промежуточный результат можно сохранить в виде целого числа. Реализованный таким образом предыдущий пример выглядит следующим образом:

Использование разложения на простые множители

В уникальная теорема факторизации указывает, что каждое положительное целое число больше 1 может быть записано только одним способом как произведение простые числа. Простые числа можно рассматривать как атомарные элементы, которые, будучи объединены вместе, составляют составное число.

Например:

Здесь составное число 90 состоит из одного атома простого числа 2, двух атомов простого числа 3 и одного атома простого числа 5.

Этот факт можно использовать для нахождения Lcm набора чисел.

Пример: lcm (8,9,21)

Разложите каждое число на множители и выразите его как произведение простого числа. полномочия.

Lcm будет произведением наибольшей степени каждого простого числа. Наибольшая степень трех простых чисел 2, 3 и 7 равна 2.3, 32, и 71, соответственно. Таким образом,

Этот метод не так эффективен, как приведение к наибольшему общему делителю, поскольку не существует известного общего эффективного алгоритма для целочисленная факторизация.

Тот же метод можно проиллюстрировать с помощью Диаграмма Венна следующим образом, с простые множители каждого из двух чисел, показанных в каждом круге, и все общие факторы на пересечении. Тогда lcm можно найти, умножив все простые числа на диаграмме.

Вот пример:

48 = 2 × 2 × 2 × 2 × 3,
180 = 2 × 2 × 3 × 3 × 5,

разделяя две общие цифры "2" и "3":

Наименьшее общее multiple.svg
Наименьшее общее кратное = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720
Наибольший общий делитель = 2 × 2 × 3 = 12

Это также работает для наибольший общий делитель (НОД), за исключением того, что вместо умножения всех чисел на диаграмме Венна умножаются только простые множители, которые находятся в пересечении. Таким образом, НОД 48 и 180 составляет 2 × 2 × 3 = 12.

Используя простой алгоритм

Этот метод легко позволяет найти lcm нескольких целых чисел.[нужна цитата ]

Пусть имеется конечная последовательность натуральных чисел Икс = (Икс1, Икс2, ..., Иксп), п > 1. Алгоритм работает поэтапно: на каждом шаге м он проверяет и обновляет последовательность Икс(м) = (Икс1(м), Икс2(м), ..., Иксп(м)), Икс(1) = Икс, куда Икс(м) это мй итерация Икс, то есть, Икс на шаге м алгоритма и т. д. Цель проверки - выбрать наименьший (возможно, один из многих) элемент последовательности Икс(м). Предполагая Иксk0(м) выбранный элемент, последовательность Икс(м+1) определяется как

Иксk(м+1) = Иксk(м), kk0
Иксk0(м+1) = Иксk0(м) + Иксk0(1).

Другими словами, наименьший элемент увеличивается на соответствующий Икс тогда как остальные элементы переходят от Икс(м) к Икс(м+1) без изменений.

Алгоритм останавливается, когда все элементы в последовательности Икс(м) равны. Их общая ценность L ровно lcm (Икс).

Например, если Икс = Икс(1) = (3, 4, 6), шаги алгоритма производят:

Икс(2) = (6, 4, 6)
Икс(3) = (6, 8, 6)
Икс(4) = (6, 8, 12) - выбрав вторую 6
Икс(5) = (9, 8, 12)
Икс(6) = (9, 12, 12)
Икс(7) = (12, 12, 12), поэтому lcm = 12.

Использование табличного метода

Этот метод работает для любого количества чисел. Сначала нужно перечислить все числа по вертикали в таблице (в этом примере 4, 7, 12, 21 и 42):

4
7
12
21
42

Процесс начинается с деления всех чисел на 2. Если 2 делит любое из них поровну, запишите 2 в новом столбце в верхней части таблицы, а результат деления на 2 каждого числа в пространстве справа в этот новый столбец. Если число не делится без остатка, просто перепишите его заново. Если 2 не делится равномерно ни на одно из чисел, повторите эту процедуру со следующим по величине простым числом, 3 (см. Ниже).

Икс2
42
77
126
2121
4221

Теперь, предполагая, что 2 действительно делило хотя бы одно число (как в этом примере), проверьте, делится ли 2 снова:

Икс22
421
777
1263
212121
422121

Как только 2 больше не делит какое-либо число в текущем столбце, повторите процедуру, разделив на следующее большее простое число, 3. Как только 3 больше не делится, попробуйте следующие большие простые числа: 5, затем 7 и т. Д. Процесс завершается, когда все числа числа уменьшены до 1 (столбец под последним простым делителем состоит только из единиц).

Икс2237
42111
77771
126311
21212171
42212171

Теперь умножьте числа в верхнем ряду, чтобы получить lcm. В данном случае это 2 × 2 × 3 × 7 = 84.

Как общий вычислительный алгоритм вышеупомянутый довольно неэффективен. Никогда бы не захотелось реализовать это в программном обеспечении: это требует слишком много шагов и требует слишком много места для хранения. Гораздо более эффективный численный алгоритм можно получить, используя Алгоритм Евклида сначала вычислить gcd, а затем получить lcm делением.

Формулы

Основная теорема арифметики

Согласно основная теорема арифметики, положительное целое число - произведение простые числа, и это представление уникально с точностью до порядка простых чисел:

где показатели п2, п3, ... - целые неотрицательные числа; например, 84 = 22 31 50 71 110 130 ...

Учитывая два положительных целых числа и их наименьшее общее кратное и наибольший общий делитель даются формулами

и

С

это дает

Фактически, каждое рациональное число может быть однозначно записано как произведение простых чисел, если допускаются отрицательные показатели. Когда это будет сделано, приведенные выше формулы останутся в силе. Например:

Теоретико-решеточный

Положительные целые числа могут быть частично заказанный по делимости: если а разделяет б (то есть, если б является целое кратное из а) записывать аб (или эквивалентно, ба). (Обратите внимание, что обычное определение ≤, основанное на величине, здесь не используется.)

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

Если формула, включающая целочисленные переменные, gcd, lcm, ≤ и ≥ верна, то формула, полученная путем переключения gcd на lcm и переключения ≥ на ≤, также верна. (Помните, что ≤ определяется как делит).

Следующие пары двойственных формул являются частными случаями общих теоретико-решеточных тождеств.

Коммутативные законы
    
Ассоциативные законы
    
Законы поглощения
Идемпотентные законы
    
Определите деления в lcm и gcd

Это также может быть показано[7] что эта решетка распределительный; то есть lcm распределяет через gcd, а gcd распределяет через lcm:

Эта идентичность самодвойственна:

Другой

потом[8]

где абсолютные столбцы || обозначают мощность множества.

  • Если ни один из равно нулю, то
[9][10]

В коммутативных кольцах

Наименьшее общее кратное можно определить в целом по коммутативные кольца следующим образом: Пусть а и б быть элементами коммутативного кольца р. Общее кратное а и б это элемент м из р так что оба а и б разделять м (то есть существуют элементы Икс и у из р такой, что топор = м и к = м). Наименьшее общее кратное а и б является минимальным общим кратным в том смысле, что для любого другого общего кратного п из а и б, м разделяетп.

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

Смотрите также

Примечания

  1. ^ а б «Исчерпывающий список символов алгебры». Математическое хранилище. 2020-03-25. Получено 2020-08-30.
  2. ^ а б c Вайсштейн, Эрик В. "Наименьший общий множитель". mathworld.wolfram.com. Получено 2020-08-30.
  3. ^ Харди и Райт, § 5.1, с. 48
  4. ^ а б Длинный (1972 г., п. 39)
  5. ^ Петтофреццо и Биркит (1970, п. 56)
  6. ^ "НАСА космосматик" (PDF).
  7. ^ Следующие три формулы взяты из Ландау, Исх. III.3, стр. 254
  8. ^ Crandall & Pomerance, ex. 2.4, п. 101.
  9. ^ Длинный (1972 г., п. 41)
  10. ^ Петтофреццо и Биркит (1970, п. 58)

Рекомендации