Наименьший общий множитель - 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 .

Пример

${\displaystyle \operatorname {lcm} (4,6)}$

Кратное 4:

${\displaystyle 4,8,12,16,20,24,28,32,36,40,44,48,52,56,60,64,68,72,76,...}$

Кратное 6:

${\displaystyle 6,12,18,24,30,36,42,48,54,60,66,72,...}$

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

${\displaystyle 12,24,36,48,60,72,...}$

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

Приложения

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

${\displaystyle {2 \over 21}+{1 \over 6}={4 \over 42}+{7 \over 42}={11 \over 42}}$

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

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

Предположим, есть два зацепляющие шестерни в машина, имея м и п зубья, соответственно, и шестерни отмечены отрезком линии, проведенным от центра первой шестерни к центру второй шестерни. Когда шестерни начинают вращаться, количество оборотов, которые должна выполнить первая шестерня, чтобы перестроить сегмент линии, можно рассчитать с помощью ${\displaystyle \operatorname {lcm} (m,n)}$. Первая передача должна завершиться ${\displaystyle \operatorname {lcm} (m,n) \over m}$ вращения для перестройки. К тому времени вторая шестерня будет ${\displaystyle \operatorname {lcm} (m,n) \over n}$ вращения.

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

Смотрите также: Планетарное выравнивание

Предположим, что вокруг звезды вращаются три планеты, которые л, м и п единиц времени, соответственно, чтобы завершить свои орбиты. Предположить, что л, м и п целые числа. Если предположить, что планеты начали двигаться вокруг звезды после первоначального линейного выравнивания, все планеты снова достигают линейного выравнивания после ${\displaystyle \operatorname {lcm} (l,m,n)}$ единиц времени. В это время первая, вторая и третья планеты будут завершены. ${\displaystyle \operatorname {lcm} (l,m,n) \over l}$, ${\displaystyle \operatorname {lcm} (l,m,n) \over m}$ и ${\displaystyle \operatorname {lcm} (l,m,n) \over n}$ орбиты соответственно вокруг звезды.^[6]

Расчет

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

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

${\displaystyle \operatorname {lcm} (a,b)={\frac {|a\cdot b|}{\gcd(a,b)}}.}$

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

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

${\displaystyle \operatorname {lcm} (21,6)={21\cdot 6 \over \gcd(21,6)}={21\cdot 6 \over \gcd(3,6)}={21\cdot 6 \over 3}={\frac {126}{3}}=42.}$

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

${\displaystyle \operatorname {lcm} (a,b)=\left({|a| \over \gcd(a,b)}\right)\cdot |b|=\left({|b| \over \gcd(a,b)}\right)\cdot |a|.}$

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

${\displaystyle \operatorname {lcm} (21,6)={21 \over \gcd(21,6)}\cdot 6={21 \over \gcd(3,6)}\cdot 6={21 \over 3}\cdot 6=7\cdot 6=42.}$

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

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

Например:

${\displaystyle 90=2^{1}\cdot 3^{2}\cdot 5^{1}=2\cdot 3\cdot 3\cdot 5.}$

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

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

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

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

${\displaystyle {\begin{aligned}8&=2^{3}\\9&=3^{2}\\21&=3^{1}\cdot 7^{1}\end{aligned}}}$

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

${\displaystyle \operatorname {lcm} (8,9,21)=2^{3}\cdot 3^{2}\cdot 7^{1}=8\cdot 9\cdot 7=504.}$

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

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

Вот пример:

48 = 2 × 2 × 2 × 2 × 3,

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

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

Наименьшее общее кратное = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720

Наибольший общий делитель = 2 × 2 × 3 = 12

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

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

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

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

Икс_k^(м+1) = Икс_k^(м), k ≠ k₀

Икс_k0^(м+1) = Икс_k0^(м) + Икс_k0⁽¹⁾.

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

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

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

Икс⁽²⁾ = (6, 4, 6)

Икс⁽³⁾ = (6, 8, 6)

Икс⁽⁴⁾ = (6, 8, 12) - выбрав вторую 6

Икс⁽⁵⁾ = (9, 8, 12)

Икс⁽⁶⁾ = (9, 12, 12)

Икс⁽⁷⁾ = (12, 12, 12), поэтому lcm = 12.

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

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

4

7

12

21

42

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

Икс	2
4	2
7	7
12	6
21	21
42	21

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

Икс	2	2
4	2	1
7	7	7
12	6	3
21	21	21
42	21	21

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

Икс	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.

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

Формулы

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

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

${\displaystyle n=2^{n_{2}}3^{n_{3}}5^{n_{5}}7^{n_{7}}\cdots =\prod _{p}p^{n_{p}},}$

где показатели п₂, п₃, ... - целые неотрицательные числа; например, 84 = 2² 3¹ 5⁰ 7¹ 11⁰ 13⁰ ...

Учитывая два положительных целых числа ${\displaystyle \;a=\prod _{p}p^{a_{p}}}$ и ${\displaystyle \;b=\prod _{p}p^{b_{p}}}$ их наименьшее общее кратное и наибольший общий делитель даются формулами

${\displaystyle \gcd(a,b)=\prod _{p}p^{\min(a_{p},b_{p})}}$

и

${\displaystyle \operatorname {lcm} (a,b)=\prod _{p}p^{\max(a_{p},b_{p})}.}$

С

${\displaystyle \min(x,y)+\max(x,y)=x+y,}$

это дает

${\displaystyle \gcd(a,b)\operatorname {lcm} (a,b)=a\,b.}$

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

${\displaystyle {\begin{array}{llll}4=2^{2}3^{0},&6=2^{1}3^{1},&\gcd(4,6)=2^{1}3^{0}=2,&\operatorname {lcm} (4,6)=2^{2}3^{1}=12.\\[8pt]{\tfrac {1}{3}}=2^{0}3^{-1}5^{0},&{\tfrac {2}{5}}=2^{1}3^{0}5^{-1},&\gcd({\tfrac {1}{3}},{\tfrac {2}{5}})=2^{0}3^{-1}5^{-1}={\tfrac {1}{15}},&\operatorname {lcm} ({\tfrac {1}{3}},{\tfrac {2}{5}})=2^{1}3^{0}5^{0}=2,\\[8pt]{\tfrac {1}{6}}=2^{-1}3^{-1},&{\tfrac {3}{4}}=2^{-2}3^{1},&\gcd({\tfrac {1}{6}},{\tfrac {3}{4}})=2^{-2}3^{-1}={\tfrac {1}{12}},&\operatorname {lcm} ({\tfrac {1}{6}},{\tfrac {3}{4}})=2^{-1}3^{1}={\tfrac {3}{2}}.\end{array}}}$

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

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

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

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

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

Коммутативные законы ${\displaystyle \operatorname {lcm} (a,b)=\operatorname {lcm} (b,a),}$ ${\displaystyle \gcd(a,b)=\gcd(b,a).}$

Ассоциативные законы ${\displaystyle \operatorname {lcm} (a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\operatorname {lcm} (a,b),c),}$ ${\displaystyle \gcd(a,\gcd(b,c))=\gcd(\gcd(a,b),c).}$

Законы поглощения ${\displaystyle \operatorname {lcm} (a,\gcd(a,b))=a,}$ ${\displaystyle \gcd(a,\operatorname {lcm} (a,b))=a.}$

Идемпотентные законы ${\displaystyle \operatorname {lcm} (a,a)=a,}$ ${\displaystyle \gcd(a,a)=a.}$

Определите деления в lcm и gcd ${\displaystyle a\geq b\iff a=\operatorname {lcm} (a,b),}$ ${\displaystyle a\leq b\iff a=\gcd(a,b).}$

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

${\displaystyle \operatorname {lcm} (a,\gcd(b,c))=\gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (a,c)),}$

${\displaystyle \gcd(a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\gcd(a,b),\gcd(a,c)).}$

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

${\displaystyle \gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (b,c),\operatorname {lcm} (a,c))=\operatorname {lcm} (\gcd(a,b),\gcd(b,c),\gcd(a,c)).}$

Другой

• Позволять D быть продуктом ω(D) различных простых чисел (т. е. D является свободный от квадратов ).

потом^[8]

${\displaystyle |\{(x,y)\;:\;\operatorname {lcm} (x,y)=D\}|=3^{\omega (D)},}$

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

• Если ни один из ${\displaystyle a_{1},a_{2},\ldots ,a_{r}}$ равно нулю, то

${\displaystyle \operatorname {lcm} (a_{1},a_{2},\ldots ,a_{r})=\operatorname {lcm} (\operatorname {lcm} (a_{1},a_{2},\ldots ,a_{r-1}),a_{r}).}$^[9][10]

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

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

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

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

• 2520 (число), наименьшее общее кратное 1, ..., 10
• Аномальная отмена
• Взаимно простые целые числа
• Функция Чебышева

Примечания

1. «Исчерпывающий список символов алгебры». Математическое хранилище. 2020-03-25. Получено 2020-08-30.
2. Вайсштейн, Эрик В. "Наименьший общий множитель". 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)

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

• Крэндалл, Ричард; Померанс, Карл (2001), Простые числа: вычислительная перспектива, Нью-Йорк: Springer, ISBN  0-387-94777-9
• Харди, Г. Х .; Райт, Э. М. (1979), Введение в теорию чисел (пятое издание), Оксфорд: Oxford University Press, ISBN  978-0-19-853171-5
• Ландау, Эдмунд (1966), Элементарная теория чисел, Нью-Йорк: Челси
• Лонг, Кальвин Т. (1972), Элементарное введение в теорию чисел (2-е изд.), Лексингтон: Д. К. Хит и компания, LCCN  77-171950
• Петтофреццо, Энтони Дж .; Биркит, Дональд Р. (1970), Элементы теории чисел, Энглвудские скалы: Prentice Hall, LCCN  77-81766