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

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

Диаграмма Венна, показывающая наименьшие общие кратные всех подмножеств {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 , так как gcd( a , 0) = | a | . Однако, если оба aи 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.}$

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

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

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

Например:

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

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

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

Пример: НОК(8,9,21)

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

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

НОК будет результатом умножения наибольшей степени каждого простого числа. Наивысшая степень трех простых чисел 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.}$

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

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

Вот пример:

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 × 5 = 8640

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

Формулы

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

Согласно основной теореме арифметики , каждое целое число, большее 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 ). (Обратите внимание, что обычное определение ≤, основанное на величине, здесь не используется.)

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

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

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

Можно также показать ^[6] , что эта решетка является дистрибутивной ; то есть НОК распределяется по НОД, а НОД распределяется по НОК:

${\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. Weisstein, Eric W. "Наименьшее общее кратное". mathworld.wolfram.com . Получено 30.08.2020 .
2. Харди и Райт, § 5.1, стр. 48
3. Long (1972, стр. 39)
4. Петтофреццо и Биркит (1970, стр. 56)
5. "космическая математика НАСА" (PDF) .
6. Следующие три формулы взяты из Ландау, пример III.3, стр. 254.
7. Crandall & Pomerance, пример 2.4, стр. 101.
8. Лонг (1972, стр. 41)
9. Петтофреццо и Биркит (1970, стр. 58)
10. Бертон 1970, стр. 94.
11. Грийе 2007, стр. 142.

Ссылки

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