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

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

В названии «наибольший общий делитель» прилагательное «наибольший» можно заменить на «наивысший», а слово «делитель» можно заменить на «коэффициент», чтобы другие названия включали в себя наибольший общий делитель и т. д. ^[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 равен 1, 2, 3, 6, 9, 18, 27, 54. Аналогично, делители числа 24 равны 1, 2, 3, 4, 6, 8, 12, 24. Числа, общие в этих двух списках, являются общими делителями 54 и 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] Например, $gcd(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)}}.

Расчет [ править ]

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

Наибольшие общие делители можно вычислить, определив простые факторизации двух чисел и сравнив коэффициенты. Например, чтобы вычислить $gcd(48, 180)$ , мы находим простые факторизации 48 = 2 ⁴ · 3 ¹ и 180 = 2 ² · 3 ² · 5 ¹; НОД тогда равен 2 ^мин(4,2) · 3 ^мин(1,2) · 5 ^мин(0,1) = 2 ² · 3 ¹ · 5 ⁰= 12 Тогда соответствующий НОК 2 ^{макс(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)=\gcd(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$ .

Бинарный алгоритм НОД [ править ]

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

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

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

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

Шаг 1 определяет $d$ как высшую степень $двойки$ , которая делит $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 д = 2 1$ и $а = б = 3$ .

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

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

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

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

O(n^{2})

.

Алгоритм НОД Лемера [ править ]

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

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

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

Свойства [ править ]

Для положительных целых чисел $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 — целое положительное число, то $НОД(м \cdot а, м \cdot б) = м \cdotНОД(а, б)$ .
Если 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 и 1 п 2 e е2 \cdot\cdot\cdot п м e в$ и $б = р 1 ж 1 п 2 f f2 \cdot\cdot\cdot п м ж м$ где $e i \geq 0$ и $fi \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)$ где $\nu _{p}(n)$ — $p$ -адическая оценка.

Вероятности ценность ожидаемая и

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

В коммутативных кольцах [ править ]

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

Если $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$ является областью целостности , то любые два НОД $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$ , откуда и возник теоретико-кольцевой термин.)

См. также [ править ]

Примечания [ править ]

^ Перейти обратно: ^а ^б Лонг (1972 , стр. 33)
^ Перейти обратно: ^а ^б ^с Петтофреззо и Биркит (1970 , стр. 34)
^ Келли, В. Майкл (2004), Полное руководство для идиота по алгебре , Penguin, стр. 142, ISBN 978-1-59257-161-1 .
^ Джонс, Аллин (1999), Целые числа, десятичные дроби, проценты и дроби, 7-й класс , Pascal Press, с. 16, ISBN 978-1-86441-378-6 .
^ Перейти обратно: ^а ^б ^с Харди и Райт (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 . Университет Западной Грузии , Карлов университет в Праге : A5 . Проверено 26 мая 2008 г.
^ Шрамм, Вольфганг (2008). «Преобразование Фурье функций наибольшего общего делителя» . ЦЕЛЫЕ ЧИСЛА: Электронный журнал комбинаторной теории чисел . 8 . Университет Западной Грузии , Карлов университет в Праге : A50 . Проверено 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: отсутствует местоположение издателя ( ссылка )
^ Мюллер-Хойссен, Фолькерт; Вальтер, Ханс-Отто (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 .
^ Найманн, Дж. Э. (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 .

Ссылки [ править ]

Эндрюс, Джордж Э. (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), Элементы теории чисел , Энглвуд Клиффс: Прентис Холл , LCCN 71081766

Дальнейшее чтение [ править ]

Дональд Кнут . Искусство компьютерного программирования , Том 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.
Сондерс Мак Лейн и Гаррет Биркгоф . Обзор современной алгебры , четвертое издание. Издательство Макмиллан, 1977. ISBN 0-02-310070-2 . 1–7: «Алгоритм Евклида».

[Long_1972_33-1] Перейти обратно: ^а ^б Лонг (1972 , стр. 33)

[Pettofrezzo_1970_34-2] Перейти обратно: ^а ^б ^с Петтофреззо и Биркит (1970 , стр. 34)

[3] Келли, В. Майкл (2004), Полное руководство для идиота по алгебре , Penguin, стр. 142, ISBN 978-1-59257-161-1 .

[4] Джонс, Аллин (1999), Целые числа, десятичные дроби, проценты и дроби, 7-й класс , Pascal Press, с. 16, ISBN 978-1-86441-378-6 .

[Hardy&Wright_1979_20-5] Перейти обратно: ^а ^б ^с Харди и Райт (1979 , стр. 20)

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

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

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

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

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

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

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

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

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

[15] "Наибольший общий делитель" . www.mathsisfun.com . Проверено 30 августа 2020 г.

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

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

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

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

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

[21] Адлеман, LM; Компелла, К. (1988). «Использование плавности для достижения параллелизма». 20-й ежегодный симпозиум ACM по теории вычислений . Нью-Йорк. стр. 528–538. дои : 10.1145/62212.62264 . ISBN 0-89791-264-0 . S2CID 9118047 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[22] Мюллер-Хойссен, Фолькерт; Вальтер, Ханс-Отто (2012), «Дов Тамари (ранее Бернхард Тейтлер)», в Мюллер-Хойссен, Фолькерт; Палло, Жан Марсель; Сташефф, Джим (ред.), Ассоциэдры, решетки Тамари и родственные структуры: Tamari Memorial Festschrift , Progress in Mathematics, vol. 299, Биркхойзер, стр. 1–40, ISBN. 978-3-0348-0405-9 . Сноска 27, с. 9: «Например, натуральные числа с НОД (наибольшим общим делителем) в качестве встречи и lcm (наименьшим общим кратным) в качестве операции соединения определяют (полную дистрибутивную) решетку». Включение этих определений для 0 необходимо для этого результата: если вместо этого исключить 0 из набора натуральных чисел, полученная решетка не будет полной.

[23] Кнут, Дональд Э .; Грэм, РЛ; Паташник, О. (март 1994 г.). Конкретная математика: основа информатики . Аддисон-Уэсли . ISBN 0-201-55802-5 .

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

v т Это Теоретико-числовые алгоритмы
Тесты на примитивность	АКС АПРЕЛЬ Бэйли – PSW Эллиптическая кривая Поклингтон Ферма Лукас Лукас-Лемер Лукас-Лемер-Ризель Теорема Прота Пепина Квадратичный Фробениус Соловей-Штрассен Миллер-Рабин
Прайм-генерирующий	Сито Аткина Решето Эратосфена Сито Причарда Решето Сундарама Факторизация колес
Целочисленная факторизация	Непрерывная дробь (CFRAC) Диксона Эллиптическая кривая Ленстры (ECM) Эйлера Ро Полларда п - 1 р + 1 Квадратное сито (QS) Сито общего числового поля (GNFS) Сито специального числового поля (SNFS) Рациональное сито Ферма Квадратные формы Шанкса Пробное подразделение Шора
Умножение	Древний Египет Длинный Карацуба Тум-Кук Шёнхаге-Штрассен Фюрера
Евклидово деление	Двоичный Разбивка на части Фурье Гольдшмидт Ньютон-Рафсон Длинный Короткий СТО
Дискретный логарифм	Бэби-шаг, гигантский шаг Поллард Ро Поллард кенгуру Полиг-Хеллман Индексное исчисление Функциональное поле сита
Наибольший общий делитель	Двоичный евклидов Расширенный евклидов Лемерс
Модульный квадратный корень	Лук Поклингтон Тонелли – Шанкс Берлекамп Кунерт
Другие алгоритмы	Чакравала Ворона Возведение в степень возведением в степень Целочисленный квадратный корень Целочисленное отношение ( LLL ; KZ ) Модульное возведение в степень Сокращение Монтгомери Пучок Система Трахтенберга
Курсивом обозначено, что алгоритм предназначен для чисел специальных форм.