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

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

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

lcm - это «наименьший общий знаменатель » (lcd), который можно использовать перед тем, как дроби можно будет сложить, вычесть или сравнить. Lcm более двух целых чисел также четко определено: это наименьшее положительное целое число, которое делится на каждое из них.

Содержание

  • 1 Обзор
    • 1.1 Обозначение
    • 1.2 Пример
  • 2 Приложения
    • 2.1 Проблема с шестернями
    • 2.2 Выравнивание планет
  • 3 Расчет
    • 3.1 Использование наибольшего общего делителя
    • 3.2 Использование простого разложения
    • 3.3 Использование простого алгоритма
    • 3.4 Использование таблицы- метод
  • 4 Формулы
    • 4.1 Основная теорема арифметики
    • 4.2 Теоретико-решеточная
    • 4.3 Другое
  • 5 В коммутативных кольцах
  • 6 См. также
  • 7 Примечания
  • 8 Ссылки

Обзор

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

Обозначение

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

Пример

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

Умножение на 4:

4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76,... {\ displaystyle 4,8,12,16,20,24,28,32,36,40,44,48,52,56,60,64,68,72,76,...}{\ displaystyle 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,... {\ displaystyle 6,12,18,24,30,36,42,48,54,60,66,72,...}{\ displaystyle 6,12,18,24,30,36,42,48,54,60,66,72,...}

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

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

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

Приложения

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

2 21 + 1 6 = 4 42 + 7 42 = 11 42 {\ displaystyle {2 \ over 21} + {1 \ over 6} = {4 \ over 42} + {7 \ over 42}. = {11 \ over 42}}{2 \ over21} + {1 \ over6} = {4 \ over42} + {7 \ over42} = {11 \ over42}

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

Задача шестерен

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

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

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

Расчет

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

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

lcm ⁡ ( а, б) = | a ⋅ b | gcd (а, б). {\ displaystyle \ operatorname {lcm} (a, b) = {\ frac {| a \ cdot b |} {\ gcd (a, b)}}.}{\ displaystyle \ operatorname {lcm} (a, b) = {\ frac {| a \ cdot b |} {\ gcd (a, b)}}.}

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

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

lcm ⁡ (21, 6) = 21 ⋅ 6 gcd (21, 6) = 21 ⋅ 6 gcd (3, 6) = 21 ⋅ 6 3 = 126 3 = 42. {\ 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.}{\ 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 (a, b) является делителем как a, так и b, более эффективно вычислять lcm путем деления перед умножением:

lcm ⁡ (a, b) = (| a | gcd (a, b)) ⋅ | б | = (| b | НОД (a, b)) ⋅ | а |. {\ displaystyle \ operatorname {lcm} (a, b) = \ left ({| a | \ over \ gcd (a, b)} \ right) \ cdot | b | = \ left ({| b | \ over \ gcd (a, b)} \ right) \ cdot | a |.}{\ displaystyle \ operatorname {lcm} (a, b) = \ left ({| a | \ over \ gcd (a, b)} \ right) \ cdot | b | = \ left ({| b | \ over \ gcd (a, b)} \ right) \ cdot | a |.}

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

lcm ⁡ (21, 6) = 21 gcd (21, 6) ⋅ 6 = 21 gcd (3, 6) ⋅ 6 = 21 3 ⋅ 6 = 7 ⋅ 6 = 42. {\ displaystyle \ operatorname {lcm} (21,6) = {21 \ over \ gcd (21,6)} \ cdot 6 = {21 \ over \ gcd (3,6)} \ cdot 6 = {21 \ более 3} \ cdot 6 = 7 \ cdot 6 = 42.}{\ 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 может быть записано только в в одну сторону как произведение простых чисел. Простые числа можно рассматривать как атомарные элементы, которые при объединении составляют составное число.

. Например:

90 = 2 1 ⋅ 3 2 ⋅ 5 1 = 2 ⋅ 3 ⋅ 3 ⋅ 5. {\ displaystyle 90 = 2 ^ {1} \ cdot 3 ^ {2} \ cdot 5 ^ {1} = 2 \ cdot 3 \ cdot 3 \ cdot 5.}{\ 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)

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

8 = 2 3 9 = 3 2 21 Знак равно 3 1 ⋅ 7 1 {\ Displaystyle {\ begin {align} 8 = 2 ^ {3} \\ 9 = 3 ^ {2} \\ 21 = 3 ^ {1} \ cdot 7 ^ {1} \ end { выровненный}}}{\ displaystyle {\ begin {align} 8 = 2 ^ {3} \\ 9 = 3 ^ {2} \\ 21 = 3 ^ {1} \ cdot 7 ^ {1} \ end {align}}}

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

lcm ⁡ (8, 9, 21) = 2 3 ⋅ 3 2 ⋅ 7 1 = 8 ⋅ 9 ⋅ 7 = 504. {\ displaystyle \ operatorname {lcm} (8,9,21) = 2 ^ {3} \ cdot 3 ^ {2} \ cdot 7 ^ {1} = 8 \ cdot 9 \ cdot 7 = 504.}{\ 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 "s и" 3 ":

Наименьшее общее кратное. svg
Наименьшее общее кратное = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720
Наибольший общий делитель = 2 × 2 × 3 = 12

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

Использование простого алгоритма

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

Пусть имеется конечная последовательность натуральных чисел X = (x 1, x 2,..., x n), n>1. Алгоритм работает по шагам следующим образом: на каждом шаге m он проверяет и обновляет последовательность X = (x 1, x 2,..., x n), X = X, где X - m-я итерация X, то есть X на шаге m алгоритма и т. Д. Цель проверки - выбрать наименьший (возможно, один из многих) элемент последовательности X. Предполагая, что x k0является выбранным элементом, последовательность X определяется как

xk= x k, k ≠ k 0
xk0= x k0+ x k0.

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

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

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

X = (6, 4, 6)
X = ( 6, 8, 6)
X = (6, 8, 12) - выбором второго 6
X = (9, 8, 12)
X = (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 (см. Ниже).

x2
42
77
126
2121
4221

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

x22
421
777
1263
212121
422121

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

x2237
42111
77771
126311
21212171
42212171

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

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

Формулы

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

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

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

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

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

gcd (a, b) = ∏ pp min (ap, bp) {\ displaystyle \ gcd (a, b) = \ prod _ {p} p ^ {\ min (a_ {p}, b_ {p})}}{\ displaystyle \ gcd (a, b) = \ prod _ {p} p ^ {\ min (a_ { p}, b_ {p})}}

и

lcm ⁡ (a, b) = ∏ pp max (ap, bp). {\ displaystyle \ operatorname {lcm} (a, b) = \ prod _ {p} p ^ {\ max (a_ {p}, b_ {p})}.}{\ displaystyle \ operatorname {lcm} (a, b) = \ prod _ {p} p ^ {\ max (a_ {p}, b_ {p })}.}

Поскольку

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

это дает

gcd (a, б) lcm ⁡ (a, b) = ab. {\ displaystyle \ gcd (a, b) \ operatorname {lcm} (a, b) = a \, b.}{\ displaystyle \ gcd (a, b) \ operatorname {lcm} (a, b) = a \, b.}

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

4 = 2 2 3 0, 6 = 2 1 3 1, gcd (4, 6) = 2 1 3 0 = 2, lcm ⁡ (4, 6) = 2 2 3 1 = 12. 1 3 = 2 0 3 - 1 5 0, 2 5 = 2 1 3 0 5 - 1, НОД (1 3, 2 5) = 2 0 3 - 1 5 - 1 = 1 15, lcm ⁡ (1 3, 2 5) = 2 1 3 0 5 0 = 2, 1 6 = 2 - 1 3 - 1, 3 4 = 2 - 2 3 1, НОД (1 6, 3 4) = 2 - 2 3 - 1 = 1 12, lcm ⁡ (1 6, 3 4) = 2 - 1 3 1 = 3 2. {\ 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}}}{\ 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}}, \ имя оператора {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}}}

Теоретико-решеточная

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

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

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

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

Коммутативные законы
lcm ⁡ (a, b) = lcm ⁡ (b, a), {\ displaystyle \ operatorname {lcm} (a, b) = \ operatorname {lcm} (b, a),}{\ displaystyle \ operatorname {lcm} (a, b) = \ operatorname {lcm} (b, a),}
gcd (a, b) = gcd (b, a). {\ displaystyle \ gcd (a, b) = \ gcd (b, a).}{\ displaystyle \ gcd (a, b) = \ gcd (b, a).}
Ассоциативные законы
lcm ⁡ (a, lcm ⁡ (b, c)) = lcm ⁡ (lcm ⁡ (a, б), в), {\ displaystyle \ operatorname {lcm} (a, \ operatorname {lcm} (b, c)) = \ operatorname {lcm} (\ operatorname {lcm} (a, b), c),}{\ displaystyle \ operatorname {lcm} (a, \ operatorname {lcm} (b, c)) = \ operatorname {lcm} (\ operatorname {lcm} (a, b), c),}
gcd (a, gcd (b, c)) = gcd (gcd (a, b), c). {\ displaystyle \ gcd (a, \ gcd (b, c)) = \ gcd (\ gcd (a, b), c).}{\ displaystyle \ gcd (a, \ gcd (b, c)) = \ gcd (\ gcd (a, b), c).}
законы поглощения
lcm ⁡ (a, gcd (a, b)) знак равно a, {\ displaystyle \ operatorname {lcm} (a, \ gcd (a, b)) = a,}{\ displaystyle \ operatorname {lcm} (a, \ gcd (a, b)) = a,}
gcd (a, lcm ⁡ (a, b)) = a. {\ displaystyle \ gcd (a, \ operatorname {lcm} (a, b)) = a.}{\ displaystyle \ gcd (a, \ operatorname {lcm} (a, b)) = a.}
идемпотентные законы
lcm ⁡ (a, a) = a, {\ displaystyle \ operatorname {lcm} ( а, а) = а,}{\ displaystyle \ operatorname {lcm} (a, a) = a, }
gcd (а, а) = а. {\ displaystyle \ gcd (a, a) = a.}{\ displaystyle \ gcd (a, a) = a.}
Определите деление в lcm и gcd
a ≥ b ⟺ a = lcm ⁡ (a, b), {\ displaystyle a \ geq b \ если и только если a = \ operatorname {lcm} (a, b),}{\ displaystyle a \ geq b \ iff a = \ operatorname {lcm} (a, b),}
a ≤ b ⟺ a = gcd (a, b). {\ displaystyle a \ leq b \ iff a = \ gcd (a, b).}{\ displaystyle a \ leq b \ iff a = \ gcd (a, b).}

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

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

Это тождество самодвойственный:

gcd (lcm ⁡ (a, b), lcm ⁡ (b, c), lcm ⁡ (a, c)) = lcm ⁡ (gcd (a, b), gcd (b, c), 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)).}{ \ displaystyle \ gcd (\ operatorname {lcm} (a, b), \ o peratorname {lcm} (b, c), \ operatorname {lcm} (a, c)) = \ operatorname {lcm} (\ gcd (a, b), \ gcd (b, c), \ gcd (a, c))).}

Другое

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

Тогда

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

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

  • Если ни один из a 1, a 2,…, ar {\ displaystyle a_ {1}, a_ {2}, \ ldots, a_ {r}}{\ displaystyle a_ {1}, a_ {2}, \ ldots, a_ {r}} равно нулю, тогда
lcm ⁡ (a 1, a 2,…, ar) = lcm ⁡ (lcm ⁡ (a 1, a 2,…, ar - 1), ar). {\ Displaystyle \ operatorname {lcm} (a_ {1}, a_ {2}, \ ldots, a_ {r}) = \ operatorname {lcm} (\ operatorname {lcm} (a_ {1}, a_ {2}, \ ldots, a_ {r-1}), 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 }).}

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

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

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

См. Также

Примечания

Ссылки

Последняя правка сделана 2021-05-26 04:24:13
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте