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

Диаграмма Венна, показывающая наименьшие общие кратные всех подмножеств {2, 3, 4, 5, 7}.

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

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

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

Обзор

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

Обозначения

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

Пример

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

Кратные 4:

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

Кратные 6:

$6,12,18,24,30,36,42,48,54,60,66,72,...$

Общие кратные 4 и 6 — это числа, которые есть в обоих списках:

$12,24,36,48,60,72,...$

В этом списке наименьшее число — 12. Следовательно, наименьшее общее кратное — 12.

Приложения

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

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

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

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

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

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

Смотрите также: Сизигий (астрономия)

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

Расчет

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

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

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

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

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

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

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

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

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

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

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

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

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

Например:

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

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

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

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

Факторируйте каждое число и выражайте его как произведение степеней простых чисел .

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

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

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

Формулы

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

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

$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}}}$, их наименьшее общее кратное и наибольший общий делитель определяются формулами

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

и

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

С

$\min(x,y)+\max(x,y)=x+y,$

это дает

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

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

${\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 и переключения ≥ на ≤, также верна. (Помните, что ≤ определяется как деление).

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

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

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

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

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

Определите деления с точки зрения lcm и gcd $a\geq b\iff a=\operatorname {lcm} (a,b),$ $a\leq b\iff a=\gcd(a,b).$

Это также можно показать что эта решетка дистрибутивна ; то есть lcm распространяется через gcd, а gcd распространяется через lcm:

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

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

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

$\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 не содержит квадратов ).

Затем

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

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

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

$\operatorname {lcm} (a_{1},a_{2},\ldots ,a_{r})=\operatorname {lcm} (\operatorname {lcm} (a_{1},a_{2},\ldots ,a_{r-1}),a_{r}).$

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

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

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

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

См. также

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

Ссылки

• Бертон, Дэвид М. (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