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

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

В названии «наибольший общий делитель» прилагательное «наибольший» может быть заменено на «наивысший», а слово «делитель» может быть заменено на «фактор», чтобы другие имена включали наибольший общий делитель ( gcf ) и т. Д. ^[4]^[5]^[6]^[7] Исторически, другие названия одного и того же понятия включали в себя наибольшую общую меру . ^[8]

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

Обзор

Определение

Наибольший общий делитель (НОД) двух ненулевых целых чисел $через$ и $Ь$ является наибольшим положительным целым числом $d$ таким образом, что $d$ является делителем обоих $а$ и $б$ ; то есть существуют целые числа $e$ и $f$ такие, что $a = de$ и $b = df$ , а $d$ - наибольшее такое целое число. НОД для $a$ и $b$ обычно обозначается $gcd (a, b)$ . ^[9]

Это определение также применяется, когда одно из $a$ и $b$ равно нулю. В этом случае НОД - это абсолютное значение ненулевого целого числа: $НОД (a, 0) = НОД (0, a) = | а |$ . Этот случай важен как завершающий шаг алгоритма Евклида .

Приведенное выше определение не может использоваться для определения $gcd (0, 0)$ , поскольку $0 \times n = 0$ , а значит, ноль не имеет наибольшего делителя. Однако нуль является его собственным наибольшим делителем, если наибольшее значение понимается в контексте отношения делимости, поэтому $gcd (0, 0)$ обычно определяется как 0. Это сохраняет обычные тождества для GCD и, в частности, тождество Безу , а именно, что $gcd (a, b)$ порождает тот же идеал, что и ${a, b}$ . ^[10]^[11]^[12] Этому соглашению придерживаются многие системы компьютерной алгебры . ^[13] Тем не менее, некоторые авторы оставляют $gcd (0, 0)$ неопределенным. ^[14]

НОД элементов $a$ и $b$ является их наибольшим положительным общим делителем в отношении предварительного порядка делимости . Это означает, что общие делители $a$ и $b$ в точности делят их НОД. Обычно это доказывается с помощью леммы Евклида , основной теоремы арифметики или алгоритма Евклида . Это значение слова «величайший», которое используется для обобщения концепции НОД.

Пример

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

{\ Displaystyle 54 \ раз 1 = 27 \ раз 2 = 18 \ раз 3 = 9 \ раз 6.}

Таким образом, полный список делителей числа 54 таков: ${\ displaystyle 1,2,3,6,9,18,27,54}$ . Аналогично делители числа 24 равны ${\ displaystyle 1,2,3,4,6,8,12,24}$ . Общие числа этих двух списков являются общими делителями 54 и 24, то есть

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

Из них наибольшее число равно 6, так что это наибольший общий делитель :

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

Вычисление всех делителей двух чисел таким способом обычно неэффективно, особенно для больших чисел, у которых много делителей. Более эффективные методы описаны в § Расчет .

Coprime числа

Два числа называются взаимно простыми или взаимно простыми , если их наибольший общий делитель равен 1. ^[15] Например, 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. В более общем плане , An матрицы с размерностью Ь прямоугольник может быть покрыт квадратными плитками длиной стороны с единственным если 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).

Приложения

Уменьшение фракций

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

{\ displaystyle {\ frac {42} {56}} = {\ frac {3 \ cdot 14} {4 \ cdot 14}} = {\ frac {3} {4}}.}

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

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

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

Расчет

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

Наибольшие общие делители могут быть вычислены путем определения разложения двух чисел на простые множители и сравнения множителей. Например, чтобы вычислить gcd (48, 180), мы находим факторизации на простые множители 48 = 2 ⁴ · 3 ¹ и 180 = 2 ² · 3 ² · 5 ¹ ; НОД тогда будет 2 ^{мин (4,2)} · 3 ^{мин (1,2)} · 5 ^{мин (0,1)} = 2 ² · 3 ¹ · 5 ⁰ = 12, как показано на диаграмме Венна . Соответствующее НОК тогда равно 2 ^{max (4,2)} · 3 ^{max (1,2)} · 5 ^{max (0,1)} = 2 ⁴ · 3 ² · 5 ¹ = 720.

^[17]

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

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

Метод, введенный Евклидом для вычисления наибольших общих делителей, основан на том факте, что для двух положительных целых чисел $a$ и $b$ таких, что $a > b$ , общие делители $a$ и $b$ совпадают с общими делителями $a - b$ и $b$ .

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

Например, чтобы вычислить $gcd (48,18)$ , $нужно действовать$ следующим образом:

{\ displaystyle {\ begin {align} (48,18) \ quad & \ to \ quad (48-18,18) = (30,18) && \ to \ quad (30-18,18) = (12, 18) \\ & \ to \ quad (12,18-12) = (12,6) && \ to \ quad (12-6,6) = (6,6). \ End {align}}}

Итак, $gcd (48, 18) = 6$ .

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

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

">

Воспроизвести медиа

Анимация, показывающая применение алгоритма Евклида для нахождения наибольшего общего делителя 62 и 36, равного 2.

Более эффективным методом является алгоритм Евклида , вариант, в котором разность двух чисел $a$ и $b$ заменяется остатком от евклидова деления (также называемого делением с остатком ) числа $a$ на $b$ .

Обозначив этот остаток в $виде мод б$ , алгоритм заменяет $( , б)$ по $(б, моды б)$ несколько раз , пока пара не является $(г, 0)$ , где $d$ представляет наибольший общий делитель.

Например, чтобы вычислить gcd (48,18), вычисление выглядит следующим образом:

{\ displaystyle {\ begin {align} (48,18) \ quad & \ to \ quad (18,48 {\ bmod {1}} 8) = (18,12) \\ & \ to \ quad (12, 18 {\ bmod {1}} 2) = (12,6) \\ & \ to \ quad (6,12 {\ bmod {6}}) = (6,0). \ End {align}}}

Это снова дает $gcd (48, 18) = 6$ .

Алгоритм Лемера GCD

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

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

Бинарный алгоритм GCD

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

а = б .

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

И 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 ), если a < b, то поменяйте местами a и b . Число c = a - b положительно и меньше a . Любое число, которое делит a и b, должно также делить c, поэтому каждый общий делитель a и b также является общим делителем b и c . Аналогично, a = b + c, и каждый общий делитель b и c также является общим делителем a и b . Таким образом, две пары ( a , b ) и ( b , c ) имеют одинаковые общие делители, и, следовательно, gcd ( a , b ) = gcd ( b , c ). Более того, поскольку a и b оба нечетны, c четно, процесс может быть продолжен с заменой пары ( a , b ) меньшими числами ( c / 2, b ) без изменения GCD.

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

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

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

{\ Displaystyle О ((\ журнал а + \ журнал Ь) ^ {2})}

Вычислительная сложность обычно выражается длиной $n$ входных данных. Здесь эта длина ${\ Displaystyle п = \ журнал а + \ журнал б,}$ и сложность, таким образом,

{\ Displaystyle О (п ^ {2})}

.

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

{\ Displaystyle \ НОД (1, х) = у,}

или функция Тома. Штриховка внизу указывает на эллипсы (т. Е. Отсутствие точек из-за очень высокой плотности).

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

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

,

но чаще НОК вычисляется из НОД.

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

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

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

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

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

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

{\ 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}}}

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

Сложность

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

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

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

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

Несмотря на то, что проблема не связана с ЧПУ , существуют параллельные алгоритмы, асимптотически более быстрые, чем алгоритм Евклида; Самый быстрый из известных детерминированных алгоритмов разработан Чором и Голдрайхом, который (в модели CRCW-PRAM ) может решить проблему за время $O (n / log n)$ с помощью $n 1 + ε$ процессоров. ^[22] Рандомизированные алгоритмы могут решить проблему за $O ((log n) 2)$ раз на ${\ Displaystyle \ ехр \ влево (О \ влево ({\ sqrt {п \ журнал п}} \ вправо) \ вправо)}$ процессоры ^{[ необходимы пояснения ]} (это суперполином ). ^[23]

Характеристики

Каждый общий делитель a и b является делителем gcd ( a , b ) .
gcd ( a , b ) , где a и b не равны нулю, может быть определен альтернативно и эквивалентно как наименьшее положительное целое число d, которое может быть записано в форме d = a ⋅ p + b ⋅ q , где p и q - целые числа. Это выражение называется личностью Безу . Такие числа p и q можно вычислить с помощью расширенного алгоритма Евклида .
gcd ( a , 0) = | а | , при a ≠ 0 , поскольку любое число является делителем 0, а наибольший делитель числа a равен | а |, ^[3]^[6] Это обычно используется как базовый случай в алгоритме Евклида.
Если 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 .
НОД является мультипликативной функцией в следующем смысле: если a ₁ и a ₂ взаимно просты, то gcd ( a ₁ ⋅ a ₂ , b ) = gcd ( a ₁ , b ) ⋅gcd ( a ₂ , b ) . В частности, вспоминая, что GCD является положительной целочисленной функцией, получаем, что gcd ( a , b ⋅ c ) = 1 тогда и только тогда, когда gcd ( a , b ) = 1 и gcd ( a , c ) = 1 .
НОД - это коммутативная функция: gcd ( a , b ) = gcd ( b , a ) .
НОД является ассоциативной функцией: gcd ( a , gcd ( b , c )) = gcd (gcd ( a , b ), c ) . Таким образом, gcd ( a , b , c , ...) может использоваться для обозначения GCD нескольких аргументов.
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 ₁^{e ₁} p ₂^{e ₂} ⋅⋅⋅ p _m^{e _m} и b = p ₁^{f ₁} p ₂^{f ₂} ⋅⋅⋅ p _m^{f _m,} где e _i ≥ 0 и f _i ≥ 0 , то НОД элементов a и b равен
gcd ( a , b ) = p ₁^{min ( e ₁ , f ₁ )} p ₂^{min ( e ₂ , f ₂ )} ⋅⋅⋅ p _m^{min ( e _m , f _m )} .
Иногда полезно определить gcd (0, 0) = 0 и lcm (0, 0) = 0, потому что тогда натуральные числа становятся полной распределительной решеткой с GCD в качестве операции встречи и LCM в качестве операции соединения. ^[24] Это расширение определения также совместимо с обобщением для коммутативных колец, приведенным ниже.
В системе декартовых координат , НОД ( , б ) можно интерпретировать как число сегментов между точками с целыми координатами на прямой отрезок прямой , соединяющей точки (0, 0) и ( , б ) .
Для неотрицательных целых чисел a и b , где a и b не равны нулю, можно доказать, рассматривая алгоритм Евклида в базе n : ^[25]
НОД ( n ^a - 1, n ^b - 1) = n ^{gcd ( a , b )} - 1 .
Тождество с участием totient функции Эйлера :
${\ displaystyle \ gcd (a, b) = \ sum _ {k | a {\ text {and}} k | b} \ varphi (k).}$

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

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

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

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

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

{\ displaystyle \ 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.

Если один аргумент GCD зафиксирован на некотором значении ${\ displaystyle m}$ , он станет мультипликативной функцией в другой переменной, и можно показать, что ^{[ необходима ссылка ]}

${\ 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 \ prod _ {p ^ {\ alpha} || n}}$ обозначает произведение по всем степеням простых чисел ${\ displaystyle p ^ {\ alpha}}$ такой, что ${\ displaystyle p ^ {\ alpha} | n}$ но ${\ displaystyle p ^ {\ alpha +1} \ not | n}$

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

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

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

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

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

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

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

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

Смотрите также

Безу домен
Наименьший общий знаменатель
Унитарный делитель

Заметки

^ a b «Исчерпывающий список символов алгебры» . Математическое хранилище . 2020-03-25 . Проверено 30 августа 2020 .
^ а б Лонг (1972 , стр. 33)
^ a b c Петтофреццо и Биркит (1970 , стр. 34)
^ Келли, У. Майкл (2004), Полное руководство для идиотов по алгебре , Penguin, стр. 142, ISBN 9781592571611.
^ Джонс, Аллин (1999), Целые числа, десятичные дроби, проценты и дроби, год 7 , Pascal Press, стр. 16, ISBN 9781864413786.
^ a b c Харди и Райт (1979 , стр.20)
^ Некоторые авторы относятся кНаибольший общий знаменатель как синонимнаибольшего общего делителя. Это противоречит общепринятому значению используемых слов, поскольку знаменатель относится кдробям, а две дроби не имеют наибольшего общего знаменателя (если две дроби имеют одинаковый знаменатель, общий знаменатель получается большим путем умножения всех числителей и знаменателей на то жецелое число).
^ Барлоу, Питер ; Павлин, Джордж ; Ларднер, Дионисий ; Эйри, сэр Джордж Бидделл ; Гамильтон, HP ; Леви, А .; Де Морган, Август ; Мосли, Генри (1847), Энциклопедия чистой математики , Р. Гриффин и Ко, стр. 589.
^ Некоторые авторы используют $(a, b)$ ,^[2]^[3]^[6], но это обозначение часто неоднозначно. Эндрюс (1994 , стр. 16) объясняет это так: «Многие авторы пишут ( a , b ) для $gcd (a, b)$ . Мы этого не делаем, потому что мы часто будем использовать ( a , b ) для обозначения точки в евклидовой системе координат. самолет."
^ Томас Х. Кормен и др. , Введение в алгоритмы (2-е издание, 2001 г.) ISBN 0262032937 , стр. 852
^ Бернард Л. Джонстон, Фред Ричман, Числа и симметрия: Введение в алгебруISBN 084930301X , стр. 38
^ Мартин Р. Диксон и др. , Введение в основные алгебраические структурыISBN 1118497759 , стр. 59
^ например, расчет Wolfram Alpha и Maxima
^ Джонатан Кац, Иегуда Линделл, Введение в современную криптографиюISBN 1351133012 , 2020, раздел 9.1.1, стр. 45
^ Вайсштейн, Эрик В. «Наибольший общий делитель» . mathworld.wolfram.com . Проверено 30 августа 2020 .
^ «Наибольший общий фактор» . www.mathsisfun.com . Проверено 30 августа 2020 .
^ Густаво Дельфино, «Понимание наименьшего общего множественного и наибольшего общего делителя», Wolfram Demonstrations Project , Опубликовано: 1 февраля 2013 г.
^ Славин, Кейт Р. (2008). «Q-биномы и наибольший общий делитель» . INTEGERS: Электронный журнал комбинаторной теории чисел . Университет Западной Грузии , Карлов университет в Праге . 8 : A5 . Проверено 26 мая 2008 .
^ Шрамм, Вольфганг (2008). «Преобразование Фурье функций наибольшего общего делителя» . INTEGERS: Электронный журнал комбинаторной теории чисел . Университет Западной Грузии , Карлов университет в Праге . 8 : A50 . Проверено 25 ноября 2008 .
^ Кнут, Дональд Э. (1997). Искусство программирования . 2: получисловые алгоритмы (3-е изд.). Эддисон-Уэсли Профессионал. ISBN 0-201-89684-2.
^ Shallcross, D .; Пан, В .; Лин-Криз Ю. (1993). «NC эквивалентность планарного целочисленного линейного программирования и евклидова НОД» (PDF) . 34-я конференция IEEE Symp. Основы компьютерных наук . С. 557–564.
^ Чор, Б .; Голдрайх, О. (1990). «Улучшенный параллельный алгоритм для целочисленного НОД». Алгоритмика . 5 (1–4): 1–10. DOI : 10.1007 / BF01840374 .
^ Адлеман, Л. М.; Компелла, К. (1988). «Использование плавности для достижения параллельности». 20-й ежегодный симпозиум ACM по теории вычислений . Нью-Йорк. С. 528–538. DOI : 10.1145 / 62212.62264 . ISBN 0-89791-264-0.
^ Мюллер-Хойссен, Фолкерт; Вальтер, Ханс-Отто (2012), «Дов Тамари (ранее Бернхард Тейтлер)», в Мюллер-Хойссен, Фолкерт; Палло, Жан Марсель; Сташефф, Джим (ред.), Associahedra , Tamari Lattices and Related Structures: Tamari Memorial Festschrift , Progress in Mathematics, 299 , Birkhäuser, pp. 1–40, ISBN 9783034804059. Сноска 27, стр. 9: «Например, натуральные числа с gcd (наибольшим общим делителем) в качестве совпадения и lcm (наименьшим общим кратным) в качестве операции соединения определяют (полную распределительную) решетку». Включение этих определений для 0 необходимо для этого результата: если вместо этого опустить 0 из набора натуральных чисел, результирующая решетка не будет полной.
^ Кнут, Дональд Э .; Graham, RL; Паташник, О. (март 1994). Конкретная математика: фундамент компьютерных наук . Эддисон-Уэсли . ISBN 0-201-55802-5.
^ Ниманн, Дж. Э. (1972). «О вероятности того, что k натуральных чисел взаимно просты» . Журнал теории чисел . 4 (5): 469–473. DOI : 10.1016 / 0022-314X (72) 90038-8 .
^ Chidambaraswamy, J .; Ситармачандрарао, Р. (1987). «О вероятности того, что значения m многочленов имеют данный НОД» Журнал теории чисел . 26 (3): 237–245. DOI : 10.1016 / 0022-314X (87) 90081-3 .

дальнейшее чтение

Дональд Кнут . Искусство программирования , Том 2: получисловые алгоритмы , третье издание. Аддисон-Уэсли, 1997. ISBN 0-201-89684-2 . Раздел 4.5.2: Наибольший общий делитель, стр. 333–356.
Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 31.2: Наибольший общий делитель, стр. 856–862.
Сондерс Маклейн и Гарретт Биркофф . Обзор современной алгебры , четвертое издание. MacMillan Publishing Co., 1977. ISBN 0-02-310070-2 . 1–7: «Евклидов алгоритм».

[:0-1] «Исчерпывающий список символов алгебры» . Математическое хранилище . 2020-03-25 . Проверено 30 августа 2020 .

[Long_1972_33-2] а б Лонг (1972 , стр. 33)

[Pettofrezzo_1970_34-3] Петтофреццо и Биркит (1970 , стр. 34)

[4] Келли, У. Майкл (2004), Полное руководство для идиотов по алгебре , Penguin, стр. 142, ISBN 9781592571611.

[5] Джонс, Аллин (1999), Целые числа, десятичные дроби, проценты и дроби, год 7 , Pascal Press, стр. 16, ISBN 9781864413786.

[Hardy&Wright_1979_20-6] Харди и Райт (1979 , стр.20)

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

[8] Барлоу, Питер ; Павлин, Джордж ; Ларднер, Дионисий ; Эйри, сэр Джордж Бидделл ; Гамильтон, HP ; Леви, А .; Де Морган, Август ; Мосли, Генри (1847), Энциклопедия чистой математики , Р. Гриффин и Ко, стр. 589.

[9] Некоторые авторы используют $(a, b)$ ,^[2]^[3]^[6], но это обозначение часто неоднозначно. Эндрюс (1994 , стр. 16) объясняет это так: «Многие авторы пишут ( a , b ) для $gcd (a, b)$ . Мы этого не делаем, потому что мы часто будем использовать ( a , b ) для обозначения точки в евклидовой системе координат. самолет."

[10] Томас Х. Кормен и др. , Введение в алгоритмы (2-е издание, 2001 г.) ISBN 0262032937 , стр. 852

[11] Бернард Л. Джонстон, Фред Ричман, Числа и симметрия: Введение в алгебруISBN 084930301X , стр. 38

[12] Мартин Р. Диксон и др. , Введение в основные алгебраические структурыISBN 1118497759 , стр. 59

[13] например, расчет Wolfram Alpha и Maxima

[14] Джонатан Кац, Иегуда Линделл, Введение в современную криптографиюISBN 1351133012 , 2020, раздел 9.1.1, стр. 45

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

[16] «Наибольший общий фактор» . www.mathsisfun.com . Проверено 30 августа 2020 .

[17] Густаво Дельфино, «Понимание наименьшего общего множественного и наибольшего общего делителя», Wolfram Demonstrations Project , Опубликовано: 1 февраля 2013 г.

[18] Славин, Кейт Р. (2008). «Q-биномы и наибольший общий делитель» . INTEGERS: Электронный журнал комбинаторной теории чисел . Университет Западной Грузии , Карлов университет в Праге . 8 : A5 . Проверено 26 мая 2008 .

[19] Шрамм, Вольфганг (2008). «Преобразование Фурье функций наибольшего общего делителя» . INTEGERS: Электронный журнал комбинаторной теории чисел . Университет Западной Грузии , Карлов университет в Праге . 8 : A50 . Проверено 25 ноября 2008 .

[20] Кнут, Дональд Э. (1997). Искусство программирования . 2: получисловые алгоритмы (3-е изд.). Эддисон-Уэсли Профессионал. ISBN 0-201-89684-2.

[21] Shallcross, D .; Пан, В .; Лин-Криз Ю. (1993). «NC эквивалентность планарного целочисленного линейного программирования и евклидова НОД» (PDF) . 34-я конференция IEEE Symp. Основы компьютерных наук . С. 557–564.

[22] Чор, Б .; Голдрайх, О. (1990). «Улучшенный параллельный алгоритм для целочисленного НОД». Алгоритмика . 5 (1–4): 1–10. DOI : 10.1007 / BF01840374 .

[23] Адлеман, Л. М.; Компелла, К. (1988). «Использование плавности для достижения параллельности». 20-й ежегодный симпозиум ACM по теории вычислений . Нью-Йорк. С. 528–538. DOI : 10.1145 / 62212.62264 . ISBN 0-89791-264-0.

[24] Мюллер-Хойссен, Фолкерт; Вальтер, Ханс-Отто (2012), «Дов Тамари (ранее Бернхард Тейтлер)», в Мюллер-Хойссен, Фолкерт; Палло, Жан Марсель; Сташефф, Джим (ред.), Associahedra , Tamari Lattices and Related Structures: Tamari Memorial Festschrift , Progress in Mathematics, 299 , Birkhäuser, pp. 1–40, ISBN 9783034804059. Сноска 27, стр. 9: «Например, натуральные числа с gcd (наибольшим общим делителем) в качестве совпадения и lcm (наименьшим общим кратным) в качестве операции соединения определяют (полную распределительную) решетку». Включение этих определений для 0 необходимо для этого результата: если вместо этого опустить 0 из набора натуральных чисел, результирующая решетка не будет полной.

[25] Кнут, Дональд Э .; Graham, RL; Паташник, О. (март 1994). Конкретная математика: фундамент компьютерных наук . Эддисон-Уэсли . ISBN 0-201-55802-5.

[nymann-26] Ниманн, Дж. Э. (1972). «О вероятности того, что k натуральных чисел взаимно просты» . Журнал теории чисел . 4 (5): 469–473. DOI : 10.1016 / 0022-314X (72) 90038-8 .

[chid-27] Chidambaraswamy, J .; Ситармачандрарао, Р. (1987). «О вероятности того, что значения m многочленов имеют данный НОД» Журнал теории чисел . 26 (3): 237–245. DOI : 10.1016 / 0022-314X (87) 90081-3 .

[1]