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

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

В названии «наибольший общий делитель» прилагательное «наибольший» может быть заменено на «наивысший», а слово «делитель» может быть заменено на «множитель», так что другие названия будут включать наибольший общий множитель и т. д. ^[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) = | a |$ . Этот случай важен как завершающий шаг алгоритма Евклида.

Приведенное выше определение не подходит для определения $gcd(0, 0)$ , поскольку не существует наибольшего целого числа $n$ такого, что $0 \times n = 0.$ Однако ноль является своим собственным наибольшим делителем, если наибольшее понимается в контексте отношения делимости, поэтому $gcd(0, 0)$ обычно определяется как $0.$ Это сохраняет обычные тождества для GCD, и в частности тождество Безу , а именно, что $gcd(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 — 1, 2, 3, 6, 9, 18, 27, 54. Аналогично, делителями числа 24 являются 1, 2, 3, 4, 6, 8, 12, 24. Числа, которые есть в этих двух списках общими, являются общими делителями чисел 54 и 24, то есть,

1,2,3,6.

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

\НОД(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 на 6 или квадратов 12 на 12. Таким образом, 12 является наибольшим общим делителем 24 и 60. Прямоугольную область 24 на 60 можно разделить на сетку из квадратов 12 на 12, с двумя квадратами вдоль одного края ( $24/12 = 2$ ) и пятью квадратами вдоль другого ( $60/12 = 5$ ).

Приложения

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

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

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

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

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

\operatorname {НОК} (a,b)={\frac {|a\cdot b|}{\operatorname {НОД} (a,b)}}.

Расчет

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

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

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

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

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

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

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

{\begin{align}\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)=\gcd(6,6).\end{align}}

Итак, $НОД(48, 18) = 6$ .

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

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

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

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

Обозначая этот остаток как $a 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$ .

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

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

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

Метод заключается в следующем: начиная с $a$ и $b$ — двух положительных целых чисел, НОД которых ищется.

Если $a$ и $b$ оба четные, то разделите их на два до тех пор, пока хотя бы одно из них не станет нечетным; пусть $d$ — число этих парных делений.
Если $а$ четное, то разделите его на два, пока оно не станет нечетным.
Если $b$ четное, то разделите его на два, пока оно не станет нечетным.
Теперь $a$ и $b$ оба нечетные и останутся нечетными до конца вычисления.
Пока a ≠ b делать
- Если $a > b$ , то замените $a$ на $a - b$ и разделите результат на два, пока $a$ не станет нечетным (поскольку $a$ и $b$ оба нечетные, существует, по крайней мере, одно деление на 2).
- Если $a < b$ , то замените $b$ на $b - a$ и разделите результат на два, пока $b$ не станет нечетным.
Теперь $a = b$ , и наибольший общий делитель равен $2^{d}a.$

Шаг 1 определяет $d$ как наивысшую степень $2$ , которая делит $a$ и $b$ , и, таким образом, их наибольший общий делитель. Ни один из шагов не изменяет набор нечетных общих делителей $a$ и $b$ . Это показывает, что когда алгоритм останавливается, результат является правильным. Алгоритм в конечном итоге останавливается, поскольку каждый шаг делит по крайней мере один из операндов по крайней мере на $2.$ Более того, количество делений на $2$ и, таким образом, количество вычитаний не превышает общего количества цифр.

Пример: ( 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 1$ и $a = b = 3$ .

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

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

Квадрат этой сложности возникает из-за того, что деление на $2$ и вычитание занимают время, пропорциональное количеству бит входных данных.

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

O(n^{2})

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

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

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

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

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

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

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

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

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

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

Кит Славин показал, что для нечетных $a \geq 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 (T (n) log n)$ . Это означает, что самый быстрый известный алгоритм имеет сложность $O (n (log n) 2)$ .

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

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

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

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

Имеют место следующие версии дистрибутивности :
$НОД(a, НОК(b, c)) = НОК(НОД(a, b), НОД(a, c))$
$НОК(а, НОД(b, c)) = НОД(НОК(а, b), НОК(а, 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 равен
$gcd(a, b) = p 1 min(e 1, f 1) p 2 min(e 2, f 2) \cdot\cdot\cdot p m min(e m, f m)$ .
Иногда полезно определить $gcd(0, 0) = 0$ и $lcm(0, 0) = 0$ , потому что тогда натуральные числа становятся полной дистрибутивной решеткой с GCD в качестве операции встречи и LCM в качестве операции соединения. ^[22] Это расширение определения также совместимо с обобщением для коммутативных колец, приведенным ниже.
В декартовой системе координат $gcd(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)=\sum _{d|n}d\phi \left({\frac {n}{d}}\right)=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$ -адическая оценка. (последовательность A018804 в OEIS ) $\nu _{p}(n)$

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

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

Используя эту информацию, можно увидеть (неформально), что ожидаемое значение функции наибольшего общего делителя не существует, когда $k = 2.$ В этом случае вероятность того, что НОД равен $d,$ равна $d -2 / ζ (2)$ , и поскольку $ζ (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 \geq 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.

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

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

Если $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 + \sqrt -3$ являются двумя максимальными общими делителями (то есть любой общий делитель, кратный $2$ , связан с $2$ , то же самое справедливо для $1 + \sqrt -3$ $, но они не связаны, поэтому наибольшего общего делителя a$ и $b$ не существует ) .

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

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

Примечания

^ ab Long (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). Энциклопедия чистой математики. R. Griffin and Co., стр. 589..
^ Некоторые авторы используют $(a, b)$ , ^[1]^[2]^[5] но эта нотация часто двусмысленна. Эндрюс (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
^ Weisstein, Eric W. "Наибольший общий делитель". mathworld.wolfram.com . Получено 30 августа 2020 г.
^ "Наибольший общий множитель". www.mathsisfun.com . Получено 2020-08-30 .
^ Славин, Кит Р. (2008). "Q-биномиалы и наибольший общий делитель". ЦЕЛЫЕ ЧИСЛА: Электронный журнал комбинаторной теории чисел . 8. Университет Западной Джорджии , Карлов университет в Праге : A5 . Получено 26.05.2008 .
^ Шрамм, Вольфганг (2008). "Преобразование Фурье функций наибольшего общего делителя". ЦЕЛЫЕ ЧИСЛА: Электронный журнал комбинаторной теории чисел . 8. Университет Западной Джорджии , Карлов университет в Праге : A50 . Получено 25.11.2008 .
^ Кнут, Дональд Э. (1997). Искусство программирования . Том 2: Получисленные алгоритмы (3-е изд.). Addison-Wesley Professional. ISBN 0-201-89684-2.
^ Шэллкросс, Д.; Пан, В.; Лин-Криз, И. (1993). "Эквивалентность NC планарного целочисленного линейного программирования и евклидова НОД" (PDF) . 34-й симпозиум IEEE. Основы компьютерной науки . стр. 557–564. Архивировано (PDF) из оригинала 2006-09-05.
^ Чор, Б.; Голдрайх, О. (1990). «Улучшенный параллельный алгоритм для целочисленного НОД». Algorithmica . 5 (1–4): 1–10. doi :10.1007/BF01840374. S2CID 17699330.
^ Адлеман, Л. М.; Компелла, К. (1988). «Использование гладкости для достижения параллелизма». 20-й ежегодный симпозиум ACM по теории вычислений . Нью-Йорк. С. 528–538. doi :10.1145/62212.62264. ISBN 0-89791-264-0. S2CID 9118047.
^ Мюллер-Хойссен, Фолькерт; Вальтер, Ханс-Отто (2012). «Дов Тамари (бывший Бернхард Тейтлер)». В Мюллер-Хойссен, Фолькерт; Палло, Жан Марсель; Сташефф, Джим (ред.). Ассоциэдры, решетки Тамари и родственные структуры: Tamari Memorial Festschrift . Прогресс в математике. Том. 299. Биркхойзер. стр. 1–40. ISBN 978-3-0348-0405-9.. Сноска 27, стр. 9: «Например, натуральные числа с НОД (наибольшим общим делителем) в качестве операции встречи и НОК (наименьшее общее кратное) в качестве операции соединения определяют (полную дистрибутивную) решетку». Включение этих определений для 0 необходимо для этого результата: если вместо этого исключить 0 из множества натуральных чисел, результирующая решетка не будет полной.
^ Кнут, Дональд Э .; Грэм, Р. Л.; Паташник, О. (март 1994 г.). Конкретная математика: основа компьютерной науки . Addison-Wesley . ISBN 0-201-55802-5.
^ Найманн, Дж. Э. (1972). «О вероятности того, что k положительных целых чисел являются взаимно простыми». Журнал теории чисел . 4 (5): 469–473. Bibcode :1972JNT.....4..469N. doi : 10.1016/0022-314X(72)90038-8 .
^ Чидамбарасвами, Дж.; Ситармачандрарао, Р. (1987). «О вероятности того, что значения m многочленов имеют заданный наибольший общий делитель» Журнал теории чисел . 26 (3): 237–245. doi : 10.1016/0022-314X(87)90081-3 .
^ Ловетт, Стивен (2015). «Divisibility in Commutative Rings». Абстрактная алгебра: структуры и приложения . Boca Raton: CRC Press. стр. 267–318. ISBN 9781482248913.

Ссылки

Эндрюс, Джордж Э. (1994) [1971]. Теория чисел. Дувр. ISBN 978-0-486-68252-5.
Харди, ГХ ; Райт, ЭМ (1979). Введение в теорию чисел (Пятое изд.). Оксфорд: Oxford University Press . ISBN 978-0-19-853171-5.
Лонг, Кэлвин Т. (1972). Элементарное введение в теорию чисел (2-е изд.). Лексингтон: DC Heath and Company . LCCN 77171950.
Петтофреццо, Энтони Дж.; Биркит, Дональд Р. (1970). Элементы теории чисел . Englewood Cliffs: Prentice Hall . LCCN 71081766.

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

Дональд Кнут . Искусство программирования , том 2: Получисленные алгоритмы , третье издание. Addison-Wesley, 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: «Алгоритм Евклида».