Наибольший общий делитель

редактировать

Наибольшее положительное целое число, которое делит два или более целых числа

В математике символ наибольший общий делитель (gcd ) двух или более целых чисел, которые не все равны нулю, является наибольшим положительным целым числом, которое делит каждое из целые числа. Для двух целых чисел x, y наибольший общий делитель x и y обозначается gcd (x, y) {\ displaystyle \ gcd (x, y)}{\ displaystyle \ gcd (x, y)} . Например, НОД 8 и 12 равно 4, то есть НОД (8, 12) = 4 {\ displaystyle \ gcd (8,12) = 4}{\ displaystyle \ gcd (8,12) = 4} .

В названии «наибольший общий делитель», прилагательное «наибольший» можно заменить на «наивысший», а слово «делитель» можно заменить на «фактор», чтобы другие имена включали наибольший общий множитель (gcf ) и т. д. Исторически сложилось так, что другие названия той же концепции включают наибольшую общую меру .

. Это понятие может быть расширено до многочленов (см. наибольший общий делитель многочлена ) и других коммутативных колец. (см. § В коммутативных кольцах ниже).

Содержание

  • 1 Обзор
    • 1.1 Обозначение
    • 1.2 Пример
    • 1.3 Взаимно простые числа
    • 1.4 Геометрический вид
  • 2 Приложения
    • 2.1 Уменьшение дробей
    • 2.2 Наименьшее общее кратное
  • 3 Расчет
    • 3.1 Использование простых факторизаций
    • 3.2 Алгоритм Евклида
    • 3.3 Алгоритм НОД Лемера
    • 3.4 Двоичный алгоритм НОД
    • 3.5 Другие методы
    • 3.6 Сложность
  • 4 Свойства
  • 5 Вероятности и ожидаемое значение
  • 6 В коммутативных кольцах
  • 7 См. Также
  • 8 Примечания
  • 9 Ссылки
  • 10 Дополнительная литература
  • 11 Внешние ссылки

Обзор

Обозначение

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

Пример

Какой наибольший общий делитель 54 и 24?

Число 54 можно выразить как произведение двух целых чисел несколькими разными способами:

54 × 1 = 27 × 2 = 18 × 3 = 9 × 6. {\ displaystyle 54 \ times 1 = 27 \ times 2 = 18 \ times 3 = 9 \ times 6. \,}54 \ times 1 = 27 \ times 2 = 18 \ times 3 = 9 \ times 6. \,

Таким образом, делители 54 равны: 1, 2, 3, 6, 9, 18, 27, 54. {\ displaystyle 1,2,3,6,9,18,27,54. \,}1,2,3,6,9,18,27,54. \,

Аналогично, делители 24 равны: 1, 2, 3, 4, 6, 8, 12, 24. {\ displaystyle 1,2,3,4,6,8,12,24. \,}1,2,3,4,6,8,12,24.\,

Общие числа в этих двух списках - это общие делители 54 и 24:

1, 2, 3, 6. {\ displaystyle 1,2,3,6. \,}1,2,3,6. \,

Наибольшее из них - 6. То есть наибольший общий делитель 54 и 24 равен 6. Записывается:

gcd (54, 24) = 6. {\ displaystyle \ gcd (54,24) = 6. \,}\ gcd (54,24) = 6. \,

Coprime числа

Два числа называются взаимно простыми или взаимно простыми, если их наибольший общий делитель равен 1. Например, 9 и 28 являются взаимно простыми числами.

Геометрический вид

"Tall, slender rectangle divided into a grid of squares. The rectangle is two squares wide and five squares tall." Прямоугольник 24 на 60 покрыт десятью квадратными плитками 12 на 12, где 12 - это НОД 24 и 60. В более общем смысле, a-by-b прямоугольник может быть покрыт квадратными плитками со стороной c, только если c является общим делителем a и b.

Например, прямоугольную область 24 на 60 можно разделить на сетку: 1 на 1 квадраты, квадраты 2 на 2, квадраты 3 на 3, квадраты 4 на 4, квадраты 6 на 6 или квадраты 12 на 12. Следовательно, 12 - это наибольший общий делитель 24 и 60. Таким образом, прямоугольную область 24 на 60 можно разделить на сетку из квадратов 12 на 12, с двумя квадратами вдоль одного края (24/12 = 2) и пять квадратов вдоль другого (60/12 = 5).

Приложения

Уменьшение дробей

Наибольший общий делитель полезен для уменьшения дробей до младших членов. Например, НОД (42, 56) = 14, следовательно,

42 56 = 3 ⋅ 14 4 ⋅ 14 = 3 4. {\ displaystyle {\ frac {42} {56}} = {\ frac {3 \ cdot 14} {4 \ cdot 14}} = {\ frac {3} {4}}.}{\ frac {42} {56}} = {\ frac {3 \ cdot 14} {4 \ cdot 14}} = {\ гидроразрыв {3} {4}}.

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

Наибольший общий делитель можно использовать для нахождения наименьшего общего кратного двух чисел, когда известен наибольший общий делитель, используя соотношение

lcm ⁡ (a, b) = | a ⋅ b | gcd ⁡ (a, b). {\ displaystyle \ operatorname {lcm} (a, b) = {\ frac {| a \ cdot b |} {\ operatorname {gcd} (a, b)}}.}\ operatorname {lcm} (a, b) = \ гидроразрыв {| a \ cdot b |} {\ operatorname {gcd} (a, b)}.

Расчет

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

В принципе, наибольшие общие делители могут быть вычислены путем определения разложений на простые множители двух чисел и сравнения множителей, как в следующем примере: для вычисления НОД (18, 84), находим простые факторизации 18 = 2 · 3 и 84 = 2 · 3 · 7, и поскольку «перекрытие» двух выражений равно 2 · 3, НОД (18, 84) = 6. На практике этот метод возможно только для небольшого числа; вычисление разложения на простые множители занимает слишком много времени.

Вот еще один конкретный пример, проиллюстрированный диаграммой Венна. Предположим, нужно найти наибольший общий делитель 48 и 180. Сначала найдите простые множители двух чисел:

48 = 2 × 2 × 2 × 2 × 3,
180 = 2 × 2 × 3 × 3 × 5.

Их объединяет две цифры «2» и «3»:

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

Алгоритм Евклида

Файл: Большой общий делитель 62 и 36 равен 2.ogv Воспроизведение мультимедиа Анимация, показывающая применение алгоритма Евклида для поиска наибольшего общего делителя 62 и 36, что равно 2.

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

Например, чтобы вычислить НОД (48,18), разделите 48 на 18, чтобы получить частное 2 и остаток 12. Затем разделите 18 на 12, чтобы получить частное 1 и остаток 6. Затем разделите 12 на 6, чтобы получить остаток от 0, что означает, что 6 - это НОД. Здесь мы проигнорировали частное на каждом этапе, за исключением того, что отметили, когда остаток достиг 0, что означает, что мы пришли к ответу. Формально алгоритм можно описать как:

gcd (a, 0) = a {\ displaystyle \ gcd (a, 0) = a}\ gcd (a, 0) = a
gcd (a, b) = gcd (b, amodb) { \ displaystyle \ gcd (a, b) = \ gcd (b, a \, \ mathrm {mod} \, b)}\ gcd (a, b) = \ gcd (b, a \, \ mathrm {mod} \, b) ,

где

amodb = a - b ⌊ ab ⌋ {\ displaystyle a \, \ mathrm {mod} \, b = ab \ left \ lfloor {a \ over b} \ right \ rfloor}a \, \ mathrm {mod} \, b = ab \ left \ lfloor {a \ over b} \ right \ rfloor .

Если оба аргумента больше нуля, тогда алгоритм может быть записан в более элементарных терминах следующим образом:

gcd (a, a) = a {\ displaystyle \ gcd (a, a) = a}\gcd(a,a)=a,
gcd (a, b) = gcd (a - b, b), {\ displaystyle \ gcd (a, b) = \ gcd (ab, b) \ quad,}\ gcd (a, b) = \ gcd (ab, b) \ quad, , если a>b
gcd (a, b) = gcd (a, b - a), {\ displaystyle \ gcd (a, b) = \ gcd (a, ba) \ quad,}\ gcd (a, b) = \ gcd (a, ba) \ quad, if b>a

алгоритм НОД Лемера

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

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

Алгоритм двоичного НОД

Алгоритм двоичного НОД использует только вычитание и деление на 2. Метод следующий: Пусть a и b - два неотрицательных целых числа. Пусть целое число d равно 0. Есть пять возможностей:

  • a = b.

Поскольку gcd (a, a) = a, желаемый gcd ​​равен a × 2 (поскольку a и b изменяются в других случаях, а d записывает, сколько раз a и b были разделены на 2 на следующем шаге, НОД исходной пары является произведением a и 2).

  • И a, и b четны.

Тогда 2 - общий делитель. Разделите a и b на 2, увеличьте d на 1, чтобы записать, сколько раз 2 является общим делителем, и продолжайте.

  • a четное, а b нечетное.

Тогда 2 не является общим делителем. Разделите a на 2 и продолжайте.

  • a нечетное, а b четное.

Тогда 2 не является общим делителем. Разделите b на 2 и продолжайте.

  • И a, и b нечетные.

Поскольку gcd (a, b) = gcd (b, a), if a < b then exchange a and b. The number c = a − b is positive and smaller than a. Any number that divides a and b must also divide c so every common divisor of a and b is also a common divisor of b and c. Similarly, a = b + c and every common divisor of b and c is also a common divisor of a and b. So the two pairs (a, b) and (b, c) have the same common divisors, and thus gcd(a,b) = gcd(b,c). Moreover, as a and b are both odd, c is even, the process can be continued with the pair (a, b) replaced by the smaller numbers (c/2, b) without changing the gcd.

Каждый из вышеперечисленных шагов уменьшает по крайней мере одно из a и b, в то время как оставляя их неотрицательными и поэтому их можно повторять только конечное число раз. Таким образом, в конечном итоге процесс приводит к a = b, случаю остановки. Тогда НОД - это a × 2.

Пример: (a, b, d) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1); Таким образом, исходный НОД является произведением 6 из 2 = 2 и a = b = 3.

Двоичный алгоритм НОД особенно легко реализовать на двоичных компьютерах. Его вычислительная сложность равна

O ((log ⁡ a + log ⁡ b) 2) {\ displaystyle O ((\ log a + \ log b) ^ {2})}O ((\ log a + \ log b) ^ {2})

Вычислительная сложность обычно выражается длиной n входных данных. Здесь эта длина равна n = log ⁡ a + log ⁡ b, {\ displaystyle n = \ log a + \ log b,}{\ displaystyle n = \ log a + \ log b,} и сложность, таким образом, составляет

O (n 2) {\ displaystyle O (n ^ {2})}O(n^{2}).

Другие методы

gcd (1, x) = y, {\ displaystyle \ gcd (1, x) = y,}\ gcd (1, х) знак равно Y, или Функция Тома. Штриховка внизу указывает на эллипсы (то есть пропуск точек из-за очень высокой плотности).

Если a и b оба ненулевые, наибольший общий делитель a и b может вычисляться с использованием наименьшего общего кратного (lcm) для a и b:

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

но чаще lcm вычисляется из gcd.

Использование функции Тома f,

gcd (a, b) = af (ba), {\ displaystyle \ gcd (a, b) = af \ left ({\ frac {b} {a}} \ right),}\ gcd (a, b) = af \ left ( {\ frac {b} {a}} \ right),

который обобщает на a и b рациональные числа или соизмеримые действительные числа.

Кейт Славин показал, что для нечетного a ≥ 1:

gcd (a, b) = log 2 ⁡ ∏ k = 0 a - 1 (1 + e - 2 i π kb / a) { \ displaystyle \ gcd (a, b) = \ log _ {2} \ prod _ {k = 0} ^ {a-1} (1 + e ^ {- 2i \ pi kb / a})}\ gcd (a, b) = \ log _ {2} \ prod _ {k = 0} ^ {a-1} (1 + e ^ {- 2i \ pi kb / a})

который - функция, которую можно вычислить для комплексного b. Вольфганг Шрамм показал, что

gcd (a, b) = ∑ k = 1 a exp ⁡ (2 π i k b / a) ⋅ ∑ d | acd (к) d {\ displaystyle \ gcd (a, b) = \ sum \ limits _ {k = 1} ^ {a} \ exp (2 \ pi ikb / a) \ cdot \ sum \ limits _ {d \ left | a \ right.} {\ frac {c_ {d} (k)} {d}}}\ gcd (a, b) = \ sum \ limits _ {k = 1} ^ {a} \ exp (2 \ pi ikb / a) \ cdot \ sum \ limits _ {d \ left | a \ right.} {\ frac {c_ {d} (k)} {d}}

- целая функция в переменной b для всех положительных целых чисел a, где c d (k) - сумма Рамануджана.

Сложность

Вычислительная сложность вычисления наибольших общих делителей широко изучалась. Если использовать алгоритм Евклида и элементарные алгоритмы умножения и деления, вычисление наибольшего общего делителя двух целых чисел длиной не более n бит будет O (n 2). {\ displaystyle O (n ^ {2}).}{\ displaystyle O (n ^ {2}).} Это означает, что вычисление наибольшего общего делителя имеет, с точностью до постоянного множителя, ту же сложность, что и умножение.

Однако, если используется быстрый алгоритм умножения, можно модифицировать алгоритм Евклида для повышения сложности, но вычисление наибольшего общего делителя становится медленнее, чем умножение. Точнее, если умножение двух целых чисел по n бит занимает время T (n), то самый быстрый известный алгоритм вычисления наибольшего общего делителя имеет сложность O (T (n) log ⁡ n). {\ displaystyle O \ left (T (n) \ log n \ right).}{\ displaystyle O \ left (T (n) \ log n \ right).} Это означает, что самый быстрый известный алгоритм имеет сложность O (n (log ⁡ n) 2 log ⁡ журнал ⁡ п). {\ displaystyle O \ left (n \, (\ log n) ^ {2} \ log \ log n \ right).}{\ displaystyle O \ left (n \, (\ log n) ^ {2} \ log \ log n \ направо).}

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

Таким образом, вычисление наибольших общих делителей относится к классу задач, решаемых за квазилинейное время. Тем более, соответствующая задача решения принадлежит к классу P задач, решаемых за полиномиальное время. Неизвестно, что проблема GCD находится в NC, и поэтому не существует известного способа распараллелить ее эффективно; также не известно, что он P-complete, что означало бы, что вряд ли возможно эффективное распараллеливание вычислений GCD. Shallcross et al. показал, что родственная задача (EUGCD, определение остаточной последовательности, возникающей в ходе алгоритма Евклида) NC-эквивалентна задаче целочисленного линейного программирования с двумя переменными; если одна из проблем находится в NC или в P-complete, другая проблема также. Поскольку NC содержит NL, также неизвестно, существует ли компактный алгоритм для вычисления GCD, даже для недетерминированных машин Тьюринга.

Хотя неизвестно, что проблема в NC, существуют параллельные алгоритмы асимптотически быстрее, чем алгоритм Евклида; Самый быстрый из известных детерминированных алгоритмов разработан Чором и Голдрайхом, который (в модели CRCW-PRAM ) может решить проблему за время O (n / log n) с n процессорами. Рандомизированные алгоритмы может решить проблему за O ((log n)) времени на exp ⁡ (O (n log ⁡ n)) {\ displaystyle \ exp \ left (O \ left ({\ sqrt {n \ log n}) } \ right) \ right)}{\ displaystyle \ exp \ left (O \ left ({\ sqrt {n \ log n}} \ right) \ right)} процессоры (это суперполином ).

Свойства

  • Каждый общий делитель a и b является делителем gcd (a, b).
  • gcd (a, b), где a и b не равны нулю, может быть определен альтернативно и эквивалентно как наименьшее положительное целое число d, которое может быть записано в форме d = a⋅p + b⋅q, где p и q - целые числа. Это выражение называется тождеством Безу. Такие числа p и q можно вычислить с помощью расширенного алгоритма Евклида.
  • gcd (a, 0) = | a | для a ≠ 0, так как любое число является делителем 0, а наибольший делитель a равен | a |. Обычно это используется в качестве базового случая в алгоритме Евклида.
  • Если a делит произведение b⋅c и gcd (a, b) = d, тогда a / d делит c.
  • Если m - неотрицательное целое число, то gcd (m⋅a, m⋅b) = m⋅gcd (a, b).
  • Если m - любое целое число, то gcd (a + m⋅b, b) = gcd (a, b).
  • Если m равно положительный общий делитель чисел a и b, тогда gcd (a / m, b / m) = gcd (a, b) / m.
  • gcd - это мультипликативная функция в в следующем смысле: если a 1 и a 2 взаимно просты, то gcd (a 1⋅a2, b) = gcd (a 1, b) ⋅ gcd (a 2, b). В частности, вспоминая, что gcd является положительной целочисленной функцией, получаем, что gcd (a, b⋅c) = 1 тогда и только тогда, когда gcd (a, b) = 1 и gcd (a, c) = 1.
  • НОД - это коммутативная функция: НОД (a, b) = НОД (b, a).
  • НОД - это ассоциативная функция: НОД (a, gcd (b, c)) = gcd (gcd (a, b), c).
  • Если нет ни одного из 1, a 2,..., a r равно нулю, тогда gcd (a 1, a 2,..., a r) = gcd (gcd (a 1, a 2,..., a r-1), a r).
  • gcd (a, b) тесно связан с наименьшее общее кратное lcm (a, b): мы имеем
    gcd (a, b) ⋅lcm (a, b) = | a⋅b |.
Эта формула часто используется для вычисления наименьших общих кратных: сначала вычисляют НОД с помощью алгоритма Евклида, а затем делят произведение заданных чисел на их НОД.
  • Верны следующие версии дистрибутивности :
    gcd (a, lcm (b, c)) = lcm (gcd (a, b), gcd (a, c))
    lcm (a, gcd (b, c)) = gcd ( lcm (a, b), lcm (a, c)).
  • Если у нас есть уникальные разложения на простые множители a = p 1p2⋅⋅⋅ p m и b = p 1p2⋅⋅⋅ p m, где e i ≥ 0 и f i ≥ 0, тогда НОД для a и b равно
    НОД ( a, b) = p 1p2⋅⋅⋅ p m.
  • Иногда полезно определить gcd (0, 0) = 0 и lcm (0, 0) = 0, потому что тогда натуральные числа стать полным дистрибьютором решетка с gcd в качестве соединения и lcm в качестве операции соединения. Это расширение определения также совместимо с обобщением для коммутативных колец, приведенным ниже.
  • В декартовой системе координат НОД (a, b) можно интерпретировать как количество сегментов между точки с целыми координатами на отрезке прямой линии, соединяющем точки (0, 0) и (a, b).
  • Для неотрицательных целых чисел a и b, где a и b - не оба равны нулю, что можно доказать, рассматривая алгоритм Евклида в базе n:
    gcd (n - 1, n - 1) = n - 1.
  • тождество с участием Функция Эйлера :
    gcd (a, b) = ∑ k | а и к | б ф (к). {\ displaystyle \ gcd (a, b) = \ sum _ {k | a {\ text {and}} k | b} \ varphi (k).}{\ displaystyle \ gcd (a, b) = \ sum _ {k | a {\ text {and}} k | b} \ varphi (k).}

Вероятности и математическое ожидание

в В 1972 году Джеймс Э. Ниманн показал, что k целых чисел, выбранных независимо и равномерно из {1,..., n}, взаимно просты с вероятностью 1 / ζ (k), когда n стремится к бесконечности, где ζ относится к Дзета-функция Римана. (См. взаимно простое число для вывода.) Этот результат был расширен в 1987, чтобы показать, что вероятность того, что k случайных целых чисел имеют наибольший общий делитель d, равна d / ζ (k).

Использование этого информации, ожидаемое значение функции наибольшего общего делителя можно увидеть (неформально) как не существующее, когда k = 2. В этом случае вероятность того, что НОД будет равна d, равна d / ζ (2), и так как ζ (2) = π / 6, имеем

E (2) = ∑ d = 1 ∞ d 6 π 2 d 2 = 6 π 2 ∑ d = 1 ∞ 1 d. {\ displaystyle \ mathrm {E} (\ mathrm {2}) = \ sum _ {d = 1} ^ {\ infty} d {\ frac {6} {\ pi ^ {2} d ^ {2}}} = {\ frac {6} {\ pi ^ {2}}} \ sum _ {d = 1} ^ {\ infty} {\ frac {1} {d}}.}\ mathrm {E} (\ mathrm {2}) = \ sum _ {d = 1} ^ {\ infty} d {\ frac {6} {\ pi ^ {2} d ^ {2}}} = {\ frac {6} {\ pi ^ {2}}} \ sum _ {d = 1} ^ {\ infty} {\ frac {1} {d}}.

Последнее суммирование - это гармонический ряд, который расходится. Однако, когда k ≥ 3, ожидаемое значение хорошо определено, и согласно приведенным выше аргументам оно равно

E (k) = ∑ d = 1 ∞ d 1 - k ζ (k) - 1 = ζ (k - 1) ζ (k). {\ displaystyle \ mathrm {E} (k) = \ sum _ {d = 1} ^ {\ infty} d ^ {1-k} \ zeta (k) ^ {- 1} = {\ frac {\ zeta ( k-1)} {\ zeta (k)}}.}\ mathrm {E} (k) = \ sum _ {d = 1} ^ {\ infty} d ^ {1-k} \ zeta (k) ^ {- 1} = {\ frac {\ zeta (k-1) } {\ zeta (k)}}.

Для k = 3 это приблизительно равно 1,3684. Для k = 4 это примерно 1,1 · 106.

Если один аргумент НОД фиксирован на некотором значении m {\ displaystyle m}m , он станет мультипликативной функцией в другой переменной, и можно показать, что

1 N lim N → ∞ ∑ n = 1 N НОД (n, m) = ∏ p α | | n (1 + α - α p) {\ displaystyle {\ frac {1} {N}} \ lim _ {N \ to \ infty} \ sum _ {n = 1} ^ {N} \ gcd (n, m) = \ prod _ {p ^ {\ alpha} || n} \ left (1+ \ alpha - {\ frac {\ alpha} {p}} \ right)}{\ displaystyle {\ frac {1} {N}} \ li m _ {N \ to \ infty} \ sum _ {n = 1} ^ {N} \ gcd (n, m) = \ prod _ {p ^ {\ alpha} || n} \ left (1+ \ alpha - {\ frac {\ alpha} {p}} \ right)}

Здесь ∏ p α | | n {\ displaystyle \ prod _ {p ^ {\ alpha} || n}}{\ displaystyle \ prod _ {p ^ {\ alpha} || n}} завершает произведение по всем степеням простых чисел p α {\ displaystyle p ^ {\ alpha}}{\ displaystyle p ^ {\ alpha}} такое, что p α | n {\ displaystyle p ^ {\ alpha} | n}{\ displaystyle p ^ {\ alpha} | n} но p α + 1 ⧸ | n {\ displaystyle p ^ {\ alpha +1} \ not | n}{\ displaystyle p ^ {\ alpha +1} \ not | n}

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

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

Если R - коммутативное кольцо, а a и b принадлежат R, то элемент d кольца R называется общим делителем a и b, если он делит как a, так и b (то есть, если есть элементы x и y в R такие, что d · x = a и d · y = b). Если d является общим делителем a и b, и каждый общий делитель a и b делит d, то d называется наибольшим общим делителем a и b.

Согласно этому определению, два элемента a и b вполне могут иметь несколько наибольших общих делителей или вообще их не иметь. Если R является областью целостности, то любые два gcd a и b должны быть ассоциированными элементами, поскольку по определению один из них должен разделять другой; действительно, если gcd существует, любой из его партнеров также является gcd. Существование НОД не гарантируется в произвольных областях целостности. Однако, если R является доменом уникальной факторизации, то любые два элемента имеют gcd, и в более общем плане это верно в доменах gcd. Если R является евклидовой областью, в которой евклидово деление задается алгоритмически (как, например, в случае, когда R = F [X], где F - это поле, или когда R - кольцо целых чисел Гаусса ), то наибольшие общие делители могут быть вычислены с использованием формы алгоритма Евклида, основанного на процедуре деления.

Ниже приведен пример области целостности с двумя элементами, не имеющими НОД:

R = Z [- 3], a = 4 = 2 ⋅ 2 = (1 + - 3) (1 - - 3), б знак равно (1 + - 3) ⋅ 2. {\ Displaystyle R = \ mathbb {Z} \ left [{\ sqrt {-3}} \, \, \ right], \ quad a = 4 = 2 \ cdot 2 = \ left (1 + {\ sqrt {-3}} \, \, \ right) \ left (1 - {\ sqrt {-3}} \, \, \ right), \ quad b = \ left (1 + {\ sqrt {-3}} \, \, \ right) \ cdot 2.}R = \ mathbb {Z } \ left [{\ sqrt {-3}} \, \, \ right], \ quad a = 4 = 2 \ cdot 2 = \ left (1 + {\ sqrt {-3}} \, \, \ right) \ left (1 - {\ sqrt {-3}} \, \, \ right), \ quad b = \ left (1 + {\ sqrt {-3}} \, \, \ right) \ cdot 2.

Элементы 2 и 1 + √ − 3 являются двумя максимальными общими делителями (то есть, любой общий делитель, кратный 2, связан с 2, то же самое верно для 1 + √ − 3, но они не связаны, поэтому не существует наибольшего общего делителя a и b.

В соответствии со свойством Безу мы можем в любом коммутативном кольце рассматривать набор элементов вида pa + qb, где p и q простираются над кольцом. Это идеал, порожденный и b, и обозначается просто (a, b). В кольце, все идеалы которого являются главными (область главных идеалов или PID), этот идеал будет идентичен h множество кратных некоторого элемента кольца d; тогда это d является наибольшим общим делителем a и b. Но идеал (a, b) может быть полезен даже тогда, когда нет наибольшего общего делителя a и b. (Действительно, Эрнст Куммер использовал этот идеал в качестве замены НОД в своей трактовке Великой теоремы Ферма, хотя он представлял его как набор кратных некоторого гипотетического или идеального, элемент кольца d, отсюда теоретико-кольцевой термин.)

См. также

Примечания

Ссылки

Дополнительная литература

Внешние ссылки

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