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

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

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

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

Обзор

Определение

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

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

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

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

Пример

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

54\times 1=27\times 2=18\times 3=9\times 6.

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

1,2,3,6.

Из них наибольшее число равно 6, поэтому оно является наибольшим общим делителем :

\gcd(54,24)=6.

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

Взаимнопростые числа

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

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

«Высокий, стройный прямоугольник, разделенный на сетку квадратов. Прямоугольник имеет ширину два квадрата и высоту пять квадратов». — Прямоугольник 24 на 60 покрыт десятью квадратными плитками размером 12 на 12, где 12 — это НОД, равный 24 и 60. В более общем смысле, прямоугольник a - b можно покрыть квадратными плитками только со стороной c . если c — общий делитель a и b .

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

Приложения

Сокращение дробей

Наибольший общий делитель полезен для приведения дробей к наименьшим слагаемым . ^[15] Например, НОД(42, 56) = 14, следовательно,

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

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

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

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

Расчет

Использование простых факторизаций

Наибольшие общие делители можно вычислить, определив простые факторизации двух чисел и сравнив коэффициенты. Например, чтобы вычислить НОД(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 ^{макс(1,2)} · 5 ^{макс(0,1)} = 2 ⁴ · 3 ² · 5 ¹ = 720.

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

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

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

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

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

{\begin{aligned}\gcd(48,18)\quad &\to \quad \gcd(48-18,18)=\gcd(30,18)&&\to \quad \gcd(30- 18,18)=\gcd(12,18)\\&\to \quad \gcd(12,18-12)=\gcd(12,6)&&\to \quad \gcd(12-6,6) =\НОД(6,6).\end{aligned}}

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

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

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

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

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

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

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

{\begin{aligned}\gcd(48,18)\quad &\to \quad \gcd(18,48{\bmod {1}}8)=\gcd(18,12)\\&\ to \quad \gcd(12,18{\bmod {1}}2)=\gcd(12,6)\\&\to \quad \gcd(6,12{\bmod {6}})=\gcd (6,0).\end{aligned}}

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

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

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

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

Бинарный алгоритм НОД

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

а = б .

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

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

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

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

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

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

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

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

Поскольку НОД( a , b ) = НОД( 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 ) имеют одинаковые общие делители, и, следовательно, НОД( a , b ) = НОД( b , c ) . Более того, поскольку a и b оба нечетны, а c четно, процесс можно продолжить с заменой пары ( a , b ) меньшими числами ( c /2, b ) без изменения НОД.

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

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

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

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

O(n^{2})

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

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

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

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

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

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

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

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

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

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

\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 ) — сумма Рамануджана . ^[17]

Сложность

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

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

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

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

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

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

Для положительных целых чисел a , $НОД(a, a) = a$ .
Каждый общий делитель a и b является делителем $НОД(a, b)$ .
$gcd(a, b)$ , где a и b не равны нулю, может быть альтернативно и эквивалентно определен как наименьшее положительное целое число d , которое можно записать в форме $d = a \cdot p + b \cdot q$ , где p и q являются целые числа. Это выражение называется тождеством Безу . Числа p и q , подобные этому, можно вычислить с помощью расширенного алгоритма Евклида .
$НОД(а, 0) = | а |$ , для $a \neq 0$ , поскольку любое число является делителем 0, а наибольший делитель a равен $| а |$ . ^[2]^[5] Обычно это используется в качестве базового случая в алгоритме Евклида.
Если a делит произведение b ⋅ c и $gcd(a, b) = d$ , то a / d делит c .
Если m — целое положительное число, то $НОД(m \cdot a, m \cdot b) = m \cdot НОД(a, b)$ .
Если m — любое целое число, то $НОД(a + m \cdot b, b) = НОД(a, b)$ . Эквивалентно, $НОД(a mod b, b) = НОД(a, b)$ .
Если m — положительный общий делитель a и b , то $НОД(a / m, b / m) = НОД(a, b)/ m$ .
НОД является коммутативной функцией: $НОД(a, b) = НОД(b, a)$ .
НОД является ассоциативной функцией: $НОД(a, НОД(b, c)) = НОД(НОД(a, b), c )$ . Таким образом, $НОД(a, b, c, ...)$ можно использовать для обозначения НОД нескольких аргументов.
НОД является мультипликативной функцией в следующем смысле: если a ₁ и a ₂ взаимно просты, то $НОД(a 1 \cdot a 2, b) = НОД(a 1, b)\cdot НОД(a 2, b)$ .
$gcd(a, b)$ тесно связан с наименьшим общим кратным $lcm(a, b)$ : мы имеем
$НОД(а, б)\cdotlcm(а, б) знак равно | а \cdot б |$ .

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

Верны следующие версии дистрибутивности :
$НОД(a, lcm(b, c)) = lcm(НОД(a, b), НОД(a, c))$
$lcm(a, НОД(b, c)) = НОД(lcm(a, b), lcm(a, c))$ .
Если у нас есть уникальные простые факторизации $a = p 1 e 1 p 2 e 2 \cdot\cdot\cdot p m e m$ и $b = p 1 f 1 p 2 f 2 \cdot\cdot\cdot p m f m$ , где $e i \geq 0$ и $f i \geq 0$ , то НОД a и b равен
$НОД(а, б) знак равно п 1 мин(е 1, ж 1) п 2 мин(е 2, ж 2) \cdot\cdot\cdot п м мин(е м, ж м)$ .
Иногда полезно определить $НОД(0, 0) = 0$ и $lcm(0, 0) = 0$ , потому что тогда натуральные числа становятся полной дистрибутивной решеткой с НОД в качестве операции встречи и LCM в качестве операции соединения. ^[22] Это расширение определения также совместимо с приведенным ниже обобщением для коммутативных колец.
В декартовой системе координат $НОД(a, b)$ можно интерпретировать как количество сегментов между точками с целыми координатами на отрезке прямой , соединяющем точки $(0, 0)$ и $(a, b)$ .
Для неотрицательных целых чисел a и b , где a и b не равны нулю, это доказывается с помощью алгоритма Евклида в базе n : ^[23]
$НОД(п а - 1, п б - 1) знак равно п НОД(а, б) - 1$ .
Тождество , включающее функцию тотента Эйлера :
$\gcd(a,b)=\sum _{k|a{\text{ and }}k|b}\varphi (k).$
$\sum _{k=1}^{n}\gcd(k,n)=n\sum _{d|n}{\frac {\varphi (d)}{d}}=n\prod _{p|n}\left(1+\nu _{p}(n)\left(1-{\frac {1}{p}}\right)\right)$ где - p -адическая оценка. $\nu _{p}(n)$

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

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

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

\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, ожидаемое значение четко определено, и согласно приведенному выше аргументу оно равно

\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,1106.

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

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

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

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

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

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$ , откуда и возник теоретико-кольцевой термин.)

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

Примечания

^ Аб Лонг (1972, стр. 33)
^ abc Pettofrezzo & Byrkit (1970, стр. 34)
^ Келли, В. Майкл (2004), Полное руководство для идиотов по алгебре, Penguin, стр. 142, ISBN 978-1-59257-161-1.
^ Джонс, Аллин (1999), Целые числа, десятичные дроби, проценты и дроби, 7-й год, Pascal Press, стр. 16, ISBN 978-1-86441-378-6.
^ abc Харди и Райт (1979, стр. 20)
^ Некоторые авторы рассматриваютнаибольший общий знаменатель как синонимнаибольшего общего делителя. Это противоречит общему значению используемых слов, поскольку знаменатель относится кдробям, а две дроби не имеют какого-либо наибольшего общего знаменателя (если две дроби имеют одинаковый знаменатель, можно получить больший общий знаменатель, умножив все числители и знаменатели на то жецелое число).
^ Барлоу, Питер ; Пикок, Джордж ; Ларднер, Дионисий ; Эйри, сэр Джордж Бидделл ; Гамильтон, HP ; Леви, А.; Де Морган, Огастес ; Мосли, Генри (1847), Энциклопедия чистой математики, Р. Гриффин и компания, стр. 589.
^ Некоторые авторы используют $(a, b)$ , ^[1]^[2]^[5] , но это обозначение часто неоднозначно. Эндрюс (1994, стр. 16) объясняет это так: «Многие авторы пишут ( a , b ) вместо $НОД(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 г.
^ Славин, Кейт Р. (2008). «Q-биномы и наибольший общий делитель». ЦЕЛЫЕ ЧИСЛА: Электронный журнал комбинаторной теории чисел . Университет Западной Грузии , Карлов университет в Праге . 8 : А5 . Проверено 26 мая 2008 г.
^ Шрамм, Вольфганг (2008). «Преобразование Фурье функций наибольшего общего делителя». ЦЕЛЫЕ ЧИСЛА: Электронный журнал комбинаторной теории чисел . Университет Западной Грузии , Карлов университет в Праге . 8 : А50 . Проверено 25 ноября 2008 г.
^ Кнут, Дональд Э. (1997). Искусство компьютерного программирования . Том. 2: Получисловые алгоритмы (3-е изд.). Аддисон-Уэсли Профессионал. ISBN 0-201-89684-2.
^ Шоллкросс, Д.; Пан, В.; Лин-Криз, Ю. (1993). «NC-эквивалентность плоского целочисленного линейного программирования и евклидова НОД» (PDF) . 34-й симпозиум IEEE. Основы информатики . стр. 557–564. Архивировано (PDF) из оригинала 5 сентября 2006 г.
^ Чор, Б .; Гольдрейх, О. (1990). «Улучшенный параллельный алгоритм для целочисленного НОД». Алгоритмика . 5 (1–4): 1–10. дои : 10.1007/BF01840374. S2CID 17699330.
^ Адлеман, LM; Компелла, К. (1988). «Использование плавности для достижения параллелизма». 20-й ежегодный симпозиум ACM по теории вычислений . Нью-Йорк. стр. 528–538. дои : 10.1145/62212.62264. ISBN 0-89791-264-0. S2CID 9118047.{{cite book}}: CS1 maint: location missing publisher (link)
^ Мюллер-Хойссен, Фолкерт; Вальтер, Ханс-Отто (2012), «Дов Тамари (ранее Бернхард Тейтлер)», в Мюллер-Хойссен, Фолькерт; Палло, Жан Марсель; Сташефф, Джим (ред.), Ассоциэдры, Решетки Тамари и родственные структуры: Tamari Memorial Festschrift , Progress in Mathematics, vol. 299, Биркхойзер, стр. 1–40, ISBN. 978-3-0348-0405-9. Сноска 27, с. 9: «Например, натуральные числа с НОД (наибольшим общим делителем) в качестве встречи и lcm (наименьшим общим кратным) в качестве операции соединения определяют (полную дистрибутивную) решетку». Включение этих определений для 0 необходимо для этого результата: если вместо этого исключить 0 из набора натуральных чисел, полученная решетка не будет полной.
^ Кнут, Дональд Э .; Грэм, РЛ; Паташник, О. (март 1994 г.). Конкретная математика: основа информатики . Аддисон-Уэсли . ISBN 0-201-55802-5.
^ Найманн, JE (1972). «О вероятности того, что k положительных целых чисел относительно просты». Журнал теории чисел . 4 (5): 469–473. Бибкод : 1972JNT.....4..469N. дои : 10.1016/0022-314X(72)90038-8 .
^ Чидамбарасвами, Дж.; Ситармачандрарао, Р. (1987). «О вероятности того, что значения m полиномов имеют заданный НОД» Журнал теории чисел . 26 (3): 237–245. дои : 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: «Алгоритм Евклида».