Наименьший общий множитель

Наименьшее положительное число, делящееся на два целых числа

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

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

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

Наименьшее общее кратное более чем двух целых чисел a , b , c , . . . , обычно обозначаемый lcm( a ,  b ,  c , . . . ) , определяется как наименьшее положительное целое число, которое делится на каждое из a , b , c , . . . ^[1]

Обзор

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

Обозначения

Наименьшее общее кратное двух целых чисел a и b обозначается как lcm( a , b ). ^[1] В некоторых старых учебниках используются [ a , b ]. ^{[3] [4]}

Пример

${\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.

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

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

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

Предположим, вокруг звезды вращаются три планеты, которым требуется l , m и n единиц времени соответственно, чтобы совершить свой оборот по орбите. Предположим, что l , m и n — целые числа. Если предположить, что планеты начали двигаться вокруг звезды после первоначального линейного выравнивания, то через несколько единиц времени все планеты снова достигнут линейного выравнивания. В это время первая, вторая и третья планеты завершат обороты вокруг звезды соответственно. ^[5] ${\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}$

Расчет

Существует несколько способов вычисления наименьших общих кратных.

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

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

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

Чтобы не вводить целые числа, большие, чем результат, удобно использовать эквивалентные формулы

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

где результатом деления всегда является целое число.

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

Возвращаясь к приведенному выше примеру,

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

Существуют быстрые алгоритмы , такие как алгоритм Евклида для вычисления НОД, которые не требуют факторизации чисел . Для очень больших целых чисел существуют еще более быстрые алгоритмы для трех задействованных операций (умножение, НОД и деление); см. Быстрое умножение . Поскольку эти алгоритмы более эффективны с факторами одинакового размера, более эффективно разделить наибольший аргумент lcm на gcd аргументов, как в примере выше.

Использование простой факторизации

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

Например:

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

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

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

Пример: 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.

Произведение = 2 × 2 × 2 × 2 × 3 × 2 × 2 × 3 × 3 × 5 = 8640.

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

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

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

Пусть существует конечная последовательность натуральных чисел X = ( x ₁ , x ₂ , ..., x _n ), n > 1. Алгоритм действует поэтапно следующим образом: на каждом шаге m он проверяет и обновляет последовательность X ^{( m )} = ( x ₁ ^{( m )} , x ₂ ^{( m )} , ..., x _n ^{( m )} ), X ⁽¹⁾ = X , где X ^{( m )} — m -я итерация X , то есть, X на шаге m алгоритма и т. д. Цель проверки — выбрать наименьший (возможно, один из многих) элемент последовательности X ^{( m )} . Предполагая, что x _{k 0} ^{( m )} является выбранным элементом, последовательность X ^{( m +1)} определяется как

Икс _k ^{( м +1)} знак равно Икс _k ^{( м )} , k ≠ k ₀

Икс _{k 0} ^{( м +1)} знак равно Икс _{k 0} ^{( м )} + Икс _{k 0} ⁽¹⁾ .

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

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

Например, если X = X ⁽¹⁾ = (3, 4, 6), шаги алгоритма дают:

Х ⁽²⁾ = (6, 4, 6)

Х ⁽³⁾ = (6, 8, 6)

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

Х ⁽⁵⁾ = (9, 8, 12)

Х ⁽⁶⁾ = (9, 12, 12)

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

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

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

4

7

12

21

42

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

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

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

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

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

Формулы

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

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

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

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

Учитывая два положительных целых числа и , их наименьшее общее кратное и наибольший общий делитель определяются по формулам ${\textstyle a=\prod _{p}p^{a_{p}}}$ ${\textstyle 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)=ab.}$

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

${\displaystyle {\begin{aligned}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 \left({\tfrac {1}{3}},{\tfrac {2}{5}}\right)&=2^{0}3^{-1}5^{-1}={\tfrac {1}{15}},&\operatorname {lcm} \left({\tfrac {1}{3}},{\tfrac {2}{5}}\right)&=2^{1}3^{0}5^{0}=2,\\[8pt]{\tfrac {1}{6}}&=2^{-1}3^{-1},&{\tfrac {3}{4}}&=2^{-2}3^{1},&\gcd \left({\tfrac {1}{6}},{\tfrac {3}{4}}\right)&=2^{-2}3^{-1}={\tfrac {1}{12}},&\operatorname {lcm} \left({\tfrac {1}{6}},{\tfrac {3}{4}}\right)&=2^{-1}3^{1}={\tfrac {3}{2}}.\end{aligned}}}$

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

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

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

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

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

Можно также показать ^[6] , что эта решетка дистрибутивна ; то есть 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 не содержит квадратов ).

Тогда ^[7]

${\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}).}$^{[8] [9]}

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

Наименьшее общее кратное можно определить над коммутативными кольцами следующим образом:

Пусть a и b — элементы коммутативного кольца R . Общее кратное a и b — это элемент m из R такой, что и a , и b делят m (то есть существуют элементы x и y из R такие, что ax = m и by = m ) . Наименьшее общее кратное a и b — это общее кратное, минимальное в том смысле, что для любого другого общего кратного n a и b m делит  n .

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

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

• Аномальная отмена
• Взаимнопростые целые числа
• функция Чебышева

Примечания

1. Вайсштейн, Эрик В. «Наименьшее общее кратное». mathworld.wolfram.com . Проверено 30 августа 2020 г.
2. Харди и Райт, § 5.1, с. 48
3. Лонг (1972, стр. 39)
4. Петтофреззо и Биркит (1970, стр. 56)
5. "космическая математика НАСА" (PDF) .
6. Следующие три формулы взяты из Ландау, Ex. III.3, с. 254
7. Крэндалл и Померанс, бывш. 2.4, с. 101.
8. Лонг (1972, стр. 41)
9. Петтофреззо и Биркит (1970, стр. 58)
10. Бертон 1970, с. 94.
11. Гриле 2007, с. 142.

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

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