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

В арифметике и теории чисел наименьшее общее кратное , наименьшее общее кратное или наименьшее общее кратное двух целых чисел 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]

Пример [ править ]

\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$ вращаются вокруг звезды соответственно. ^[5]

Расчет [ править ]

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

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

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

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

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

Затем ^[7]

|\{(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}).

^[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] (пересечение совокупности идеалов всегда есть идеал).

См. также [ править ]

Примечания [ править ]

^ Перейти обратно: ^а ^б ^с Вайсштейн, Эрик В. «Наименьшее общее кратное» . mathworld.wolfram.com . Проверено 30 августа 2020 г.
^ Харди и Райт, § 5.1, с. 48
^ Перейти обратно: ^а ^б Лонг (1972 , стр. 39)
^ Петтофреззо и Биркит (1970 , стр. 56)
^ «космическая математика НАСА» (PDF) .
^ Следующие три формулы взяты из Ландау, Ex. III.3, с. 254
^ Крэндалл и Померанс, бывш. 2.4, с. 101.
^ Лонг (1972 , стр. 41)
^ Петтофреззо и Биркит (1970 , стр. 58)
^ Перейти обратно: ^а ^б Бертон 1970 , с. 94.
^ Гриле 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

[:1-1] Перейти обратно: ^а ^б ^с Вайсштейн, Эрик В. «Наименьшее общее кратное» . mathworld.wolfram.com . Проверено 30 августа 2020 г.

[2] Харди и Райт, § 5.1, с. 48

[auto-3] Перейти обратно: ^а ^б Лонг (1972 , стр. 39)

[4] Петтофреззо и Биркит (1970 , стр. 56)

[5] «космическая математика НАСА» (PDF) .

[6] Следующие три формулы взяты из Ландау, Ex. III.3, с. 254

[7] Крэндалл и Померанс, бывш. 2.4, с. 101.

[8] Лонг (1972 , стр. 41)

[9] Петтофреззо и Биркит (1970 , стр. 58)

[FOOTNOTEBurton197094-10] Перейти обратно: ^а ^б Бертон 1970 , с. 94.

[FOOTNOTEGrillet2007142-11] Гриле 2007 , стр. 142.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

v т Это Дроби и соотношения
	Деление и соотношение	Дивиденд ÷ Делитель = Частное
	Доля	Числитель / знаменатель = частное
	алгебраический Аспект Двоичный Продолжение Десятичная дробь Диадический Египетский Золотой Серебро Целое число Нередуцируемый Снижение Просто интонация ЖК-дисплей Музыкальный интервал Размер бумаги Процент Единица