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

Метод Евклида для нахождения наибольшего общего делителя (НОД) двух начальных длин BA и DC, которые определены как кратные общей «единичной» длины. Поскольку длина DC короче, она используется для «измерения» BA, но только один раз, потому что остаток EA меньше DC. EA теперь измеряет (в два раза) более короткую длину DC, а остаток FC короче, чем EA. Затем FC измеряет (трижды) длину EA. Поскольку остатка нет, процесс завершается тем, что FC является GCD. Справа Никомах Пример с числами 49 и 21, результатом которых является их НОД 7 (получено из Heath 1908: 300).

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

Алгоритм Евклида основан на том принципе, что наибольший общий делитель двух чисел не меняется, если большее число заменяется его разностью с меньшим числом. Например, 21 - это НОД 252 и 105 (как 252 = 21 × 12 и 105 = 21 × 5), и то же число 21 также является НОД 105 и 252 - 105 = 147. Поскольку эта замена уменьшает большее из двух чисел, повторение этого процесса дает последовательно меньшие пары чисел, пока два числа не станут равными. Когда это происходит, они являются НОД исходных двух чисел. К поменять шаги или используя расширенный алгоритм Евклида, НОД можно выразить как линейная комбинация двух исходных чисел, то есть суммы двух чисел, каждое из которых умножено на целое число (Например, 21 = 5 × 105 + (−2) × 252). Тот факт, что НОД всегда можно выразить таким образом, известен как Личность Безу.

Версия алгоритма Евклида, описанная выше (и Евклидом), может предпринять много шагов вычитания, чтобы найти НОД, когда одно из заданных чисел намного больше другого. Более эффективная версия алгоритма сокращает эти шаги, вместо этого заменяя большее из двух чисел его остатком при делении на меньшее из двух (в этой версии алгоритм останавливается при достижении нулевого остатка). Благодаря этому усовершенствованию алгоритм никогда не требует больше шагов, чем пятикратное количество цифр (основание 10) меньшего целого числа. Это было доказано Габриэль Ламе в 1844 году и знаменует собой начало теория сложности вычислений. Дополнительные методы повышения эффективности алгоритма были разработаны в ХХ веке.

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

Фон: наибольший общий делитель

Алгоритм Евклида вычисляет наибольший общий делитель (НОД) двух натуральные числа а и б. Наибольший общий делитель грамм это наибольшее натуральное число, которое делит оба а и б не оставляя остатка. Синонимы к GCD включают наибольший общий делитель (GCF), наивысший общий фактор (HCF), старший общий делитель (HCD), а наибольшая общая мера (GCM). Наибольший общий делитель часто записывается как gcd (а, б) или, проще, как (а, б),^[1] хотя последнее обозначение неоднозначно, оно также используется для таких понятий, как идеальный в кольцо целых чисел, который тесно связан с GCD.

Если gcd (а, б) = 1, то а и б как говорят совмещать (или относительно простые).^[2] Это свойство не означает, что а или же б сами простые числа.^[3] Например, ни 6, ни 35 не являются простыми числами, так как они оба имеют два простых множителя: 6 = 2 × 3 и 35 = 5 × 7. Тем не менее, 6 и 35 взаимно просты. Никакое натуральное число, кроме 1, не делит 6 и 35, так как у них нет общих простых делителей.

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

Позволять грамм = gcd (а, б). С а и б оба кратны грамм, их можно написать а = мг и б = нг, и нет большего числа грамм > грамм для чего это правда. Натуральные числа м и п должны быть взаимно простыми, поскольку любой общий фактор может быть исключен из м и п сделать грамм больше. Таким образом, любое другое число c что разделяет оба а и б должен также разделить грамм. Наибольший общий делитель грамм из а и б является единственным (положительным) общим делителем числа а и б который делится на любой другой общий делитель c.^[4]

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

НОД двух чисел а и б представляет собой произведение простых множителей, общих для двух чисел, где один и тот же простой множитель может использоваться несколько раз, но только до тех пор, пока произведение этих множителей делит оба а и б.^[6] Например, поскольку 1386 можно разложить на 2 × 3 × 3 × 7 × 11, а 3213 можно разложить на 3 × 3 × 3 × 7 × 17, наибольший общий делитель 1386 и 3213 равен 63 = 3 × 3 × 7, произведение их общих простых факторов. Если два числа не имеют общих простых делителей, их наибольший общий делитель равен 1 (получен здесь как пример пустой продукт ), другими словами, они взаимно просты. Ключевым преимуществом алгоритма Евклида является то, что он может эффективно находить НОД без вычисления простых множителей.^[7][8] Факторизация больших целых чисел считается вычислительно очень сложной задачей, а безопасность многих широко используемых криптографические протоколы основано на его невозможности.^[9]

Другое определение НОД полезно в продвинутой математике, особенно в теория колец.^[10] Наибольший общий делитель грамм двух ненулевых чисел а и б также является их наименьшей положительной целочисленной линейной комбинацией, то есть наименьшим положительным числом вида ua + vb куда ты и v целые числа. Множество всех целых линейных комбинаций а и б фактически совпадает с набором всех кратных грамм (мг, куда м является целым числом). На современном математическом языке идеальный создано а и б идеал, порожденныйграмм один (идеал, порожденный одним элементом, называется главный идеал, а все идеалы целых чисел являются главными идеалами). Некоторые свойства НОД на самом деле легче увидеть с помощью этого описания, например тот факт, что любой общий делитель а и б также делит НОД (он делит оба члена ua + vb). Эквивалентность этого определения GCD другим определениям описывается ниже.

НОД трех или более чисел равен произведению простых множителей, общих для всех чисел,^[11] но его также можно вычислить, многократно взяв НОД пар чисел.^[12] Например,

gcd (а, б, c) = gcd (а, gcd (б, c)) = gcd (gcd (а, б), c) = gcd (gcd (а, c), б).

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

Описание

Процедура

Алгоритм Евклида состоит из ряда шагов, так что выходные данные каждого шага используются в качестве входных данных для следующего. Позволять k быть целым числом, которое считает шаги алгоритма, начиная с нуля. Таким образом, начальный шаг соответствует k = 0, следующий шаг соответствует k = 1 и так далее.

Каждый шаг начинается с двух неотрицательных остатков р_k−1 и р_k−2. Поскольку алгоритм гарантирует, что остатки неуклонно уменьшаются с каждым шагом, р_k−1 меньше, чем его предшественник р_k−2. Цель k-й шаг - найти частное q_k и остаток р_k которые удовлетворяют уравнению

${displaystyle r_ {k-2} = q_ {k} r_ {k-1} + r_ {k}}$

и что 0 ≤ р_k < р_k−1. Другими словами, кратные меньшему числу р_k−1 вычитаются из большего числа р_k−2 до остатка р_k меньше чем р_k−1.

На начальном этапе (k = 0) остатки р₋₂ и р₋₁ равный а и б, числа, для которых ищется НОД. На следующем шаге (k = 1) остатки равны б а остальное р₀ начального шага и т. д. Таким образом, алгоритм можно записать в виде последовательности уравнений

${displaystyle {egin {align} a & = q_ {0} b + r_ {0} b & = q_ {1} r_ {0} + r_ {1} r_ {0} & = q_ {2} r_ {1} + r_ {2} r_ {1} & = q_ {3} r_ {2} + r_ {3} & ,,, vdots конец {выровнено}}}$

Если а меньше чем б, первый шаг алгоритма меняет местами числа. Например, если а < б, начальное частное q₀ равен нулю, а остаток р₀ является а. Таким образом, р_k меньше, чем его предшественник р_k−1 для всех k ≥ 0.

Поскольку остатки уменьшаются с каждым шагом, но никогда не могут быть отрицательными, остаток р_N должен в конечном итоге равняться нулю, после чего алгоритм останавливается.^[13] Последний ненулевой остаток р_N−1 является наибольшим общим делителем а и б. Номер N не может быть бесконечным, потому что есть только конечное число неотрицательных целых чисел между начальным остатком р₀ и ноль.

Доказательство действительности

Справедливость алгоритма Евклида может быть доказана двухэтапным аргументом.^[14] На первом шаге последний ненулевой остаток р_N−1 показано деление обоих а и б. Поскольку это общий делитель, он должен быть меньше или равен наибольшему общему делителю. грамм. На втором шаге показано, что любой общий делитель числа а и б, включая грамм, должен разделить р_N−1; следовательно, грамм должно быть меньше или равно р_N−1. Эти два вывода несовместимы, если р_N−1 = грамм.

Чтобы продемонстрировать, что р_N−1 разделяет оба а и б (первый шаг), р_N−1 делит своего предшественника р_N−2

р_N−2 = q_N р_N−1

так как последний остаток р_N равно нулю. р_N−1 также делит своего следующего предшественника р_N−3

р_N−3 = q_N−1 р_N−2 + р_N−1

потому что он делит оба члена в правой части уравнения. Повторяя тот же аргумент, р_N−1 делит все предыдущие остатки, включая а и б. Ни один из предыдущих остатков р_N−2, р_N−3и т. д. разделить а и б, поскольку они оставляют остаток. С р_N−1 является общим делителем а и б, р_N−1 ≤ грамм.

На втором этапе любое натуральное число c что разделяет оба а и б (другими словами, любой общий делитель а и б) делит остатки р_k. По определению, а и б можно записать как кратное c : а = MC и б = NC, куда м и п натуральные числа. Следовательно, c делит начальный остаток р₀, поскольку р₀ = а − q₀б = MC − q₀NC = (м − q₀п)c. Аналогичный аргумент показывает, что c также делит последующие остатки р₁, р₂и т. д. Следовательно, наибольший общий делитель грамм должен разделить р_N−1, откуда следует, что грамм ≤ р_N−1. Поскольку первая часть аргумента показала обратное (р_N−1 ≤ грамм), следует, что грамм = р_N−1. Таким образом, грамм является наибольшим общим делителем всех последующих пар:^[15][16]

грамм = gcd (а, б) = gcd (б, р₀) = gcd (р₀, р₁) =… = НОД (р_N−2, р_N−1) = р_N−1.

Пример работы

Анимация алгоритма Евклида на основе вычитания. Исходный прямоугольник имеет размеры а = 1071 и б = 462. Квадраты размером 462 × 462 помещаются в него, оставляя прямоугольник 462 × 147. Этот прямоугольник выложен плиткой из 147 × 147 квадратов, пока не останется прямоугольник 21 × 147, который, в свою очередь, выложен плиткой 21 × 21 квадратом, не оставляя непокрытой области. Наименьший квадрат размером 21 - это НОД 1071 и 462.

Для иллюстрации можно использовать алгоритм Евклида, чтобы найти наибольший общий делитель а = 1071 и б = 462. Для начала, кратные 462 вычитаются из 1071, пока остаток не станет меньше 462. Два таких кратных можно вычесть (q₀ = 2), оставляя остаток от 147:

1071 = 2 × 462 + 147.

Затем из 462 вычитаются числа, кратные 147, пока остаток не станет меньше 147. Можно вычесть три кратных (q₁ = 3), оставив остаток от 21:

462 = 3 × 147 + 21.

Затем из 147 вычитаются числа, кратные 21, пока остаток не станет меньше 21. Можно вычесть семь кратных (q₂ = 7), не оставляя остатка:

147 = 7 × 21 + 0.

Поскольку последний остаток равен нулю, алгоритм заканчивается 21 как наибольший общий делитель 1071 и 462. Это согласуется с НОД (1071, 462), найденным путем разложения на простые множители. над. В табличной форме шаги следующие:

Визуализация

Алгоритм Евклида можно представить себе в терминах мозаичной аналогии, приведенной выше для наибольшего общего делителя.^[17] Предположим, что мы хотим покрыть а-к-б прямоугольник с квадратными плитками ровно, где а является большим из двух чисел. Сначала мы пытаемся выложить прямоугольник, используя б-к-б квадратная плитка; однако это оставляет р₀-к-б остаточный прямоугольник без элементов, где р₀ < б. Затем мы пытаемся замостить остаточный прямоугольник с помощью р₀-к-р₀ квадратная плитка. Остается второй остаточный прямоугольник р₁-к-р₀, который мы пытаемся выложить плиткой, используя р₁-к-р₁ квадратная плитка и т. д. Последовательность завершается, когда нет остаточного прямоугольника, то есть когда квадратные плитки точно покрывают предыдущий остаточный прямоугольник. Длина сторон самой маленькой квадратной плитки - это НОД размеров исходного прямоугольника. Например, самая маленькая квадратная плитка на соседнем рисунке имеет размер 21 на 21 (показано красным), а 21 - это НОД 1071 и 462, размеры исходного прямоугольника (показаны зеленым).

Евклидово деление

На каждом шагу k, алгоритм Евклида вычисляет частное q_k и остальное р_k из двух номеров р_k−1 и р_k−2

р_k−2 = q_k р_k−1 + р_k

где р_k неотрицательно и строго меньше, чем абсолютная величина из р_k−1. Теорема, лежащая в основе определения Евклидово деление гарантирует, что такое частное и остаток всегда существуют и уникальны.^[18]

В исходной версии алгоритма Евклида частное и остаток находятся путем повторного вычитания; то есть, р_k−1 вычитается из р_k−2 повторно до остатка р_k меньше чем р_k−1. После того р_k и р_k−1 обмениваются, и процесс повторяется. Евклидово деление сокращает все шаги между двумя обменами до одного шага, что, таким образом, более эффективно. Более того, частные не нужны, поэтому можно заменить евклидово деление на операция по модулю, что дает только остаток. Таким образом, итерация алгоритма Евклида становится просто

р_k = р_k−2 мод р_k−1.

Реализации

Реализации алгоритма могут быть выражены в псевдокод. Например, версия на основе разделения может быть запрограммированный в качестве^[19]

функция gcd (a, b) пока b ≠ 0 t: = b b: = a мод б а: = т возвращаться а

В начале kй итерации переменная б держит последний остаток р_k−1, а переменная а держит своего предшественника, р_k−2. Шаг б := а мод б эквивалентно приведенной выше формуле рекурсии р_k ≡ р_k−2 мод р_k−1. В временная переменная т имеет ценность р_k−1 а следующий остаток р_k рассчитывается. В конце итерации цикла переменная б держит остаток р_k, а переменная а держит своего предшественника, р_k−1.

В версии на основе вычитания, которая была исходной версией Евклида, вычисление остатка (б: = а мод б) заменяется повторным вычитанием.^[20] В отличие от версии на основе деления, которая работает с произвольными целыми числами в качестве ввода, версия на основе вычитания предполагает, что ввод состоит из положительных целых чисел и останавливается, когда а = б:

функция gcd (a, b) пока а ≠ б если а> б а: = а - б еще            б: = б - а возвращаться а

Переменные а и б поочередно удерживая предыдущие остатки р_k−1 и р_k−2. Предположить, что а больше чем б в начале итерации; тогда а равно р_k−2, поскольку р_k−2 > р_k−1. Во время итерации цикла а уменьшается кратно предыдущему остатку б до того как а меньше чем б. потом а следующий остаток р_k. потом б уменьшается кратно а пока он снова не станет меньше, чем а, давая следующий остаток р_k+1, и так далее.

Рекурсивная версия^[21] основан на равенстве НОД последовательных остатков и условия остановки НОД (р_N−1, 0) = р_N−1.

функция gcd (a, b) если б = 0 возвращаться а еще        возвращаться gcd (b, a мод б)

Например, НОД (1071, 462) вычисляется из эквивалентного НОД (462, 1071 mod 462) = НОД (462, 147). Последний НОД вычисляется из НОД (147, 462 mod 147) = НОД (147, 21), который, в свою очередь, вычисляется из НОД (21, 147 mod 21) = НОД (21, 0) = 21.

Метод наименьших абсолютных остатков

В другой версии алгоритма Евклида частное на каждом шаге увеличивается на единицу, если результирующий отрицательный остаток меньше по величине, чем типичный положительный остаток.^[22][23] Ранее уравнение

р_k−2 = q_k р_k−1 + р_k

предположил, что |р_k−1| > р_k > 0. Однако альтернативный отрицательный остаток е_k можно вычислить:

р_k−2 = (q_k + 1) р_k−1 + е_k

если р_k−1 > 0 или же

р_k−2 = (q_k − 1) р_k−1 + е_k

если р_k−1 < 0.

Если р_k заменяется на е_k. когда |е_k| < |р_k|, то получается такой вариант алгоритма Евклида, что

|р_k| ≤ |р_k−1| / 2

на каждом шагу.

Леопольд Кронекер показал, что эта версия требует наименьшего количества шагов по сравнению с любой версией алгоритма Евклида.^[22][23] В более общем плане было доказано, что для каждого входного числа а и б, количество шагов минимально тогда и только тогда, когда q_k выбирается для того, чтобы ${displaystyle left | {frac {r_ {k + 1}} {r_ {k}}} ight | <{frac {1} {varphi}} sim 0.618,}$ куда ${displaystyle varphi}$ это Золотое сечение.^[24]

Историческое развитие

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

Алгоритм Евклида - один из самых старых широко используемых алгоритмов.^[25] Он появляется в Евклида Элементы (ок. 300 г. до н.э.), особенно в Книге 7 (Предложения 1–2) и Книге 10 (Предложения 2–3). В Книге 7 алгоритм сформулирован для целых чисел, тогда как в Книге 10 он сформулирован для длин отрезков прямой. (В современном использовании можно сказать, что он был сформулирован для действительные числа. Но длины, площади и объемы, представленные в современном обиходе действительными числами, не измеряются в одних и тех же единицах, и нет естественных единиц длины, площади или объема; понятие действительных чисел в то время было неизвестно.) Последний алгоритм является геометрическим. НОД двух длин а и б соответствует наибольшей длине грамм это меры а и б равномерно; другими словами, длина а и б оба целые числа кратные длины грамм.

Вероятно, алгоритм не был обнаружен Евклид, который обобщил результаты более ранних математиков в своей Элементы.^[26][27] Математик и историк Б. Л. ван дер Варден предполагает, что Книга VII происходит из учебника по теория чисел написано математиками в школе Пифагор.^[28] Алгоритм, вероятно, был известен Евдокс Книдский (около 375 г. до н.э.).^[25][29] Алгоритм может даже предшествовать Евдоксу,^[30][31] судя по использованию технического термина ἀνθυφαίρεσις (ангиферез, взаимное вычитание) в работах Евклида и Аристотеля.^[32]

Спустя столетия алгоритм Евклида был независимо открыт как в Индии, так и в Китае.^[33] в первую очередь решить Диофантовы уравнения возникшие в астрономии и создании точных календарей. В конце V века индийский математик и астроном Арьябхата описал алгоритм как «измельчитель»,^[34] возможно, из-за его эффективности при решении диофантовых уравнений.^[35] Хотя частный случай Китайская теорема об остатках уже было описано в китайской книге Сунзи Суаньцзин,^[36] общее решение было опубликовано Цинь Цзюшао в его книге 1247 г. Шушу Цзючжан (數 書 九章 Математический трактат в девяти разделах ).^[37] Впервые был описан алгоритм Евклида. численно и популяризован в Европе во втором издании Баше Problèmes plaisants et délectables (Приятные и приятные проблемы, 1624).^[34] В Европе он также использовался для решения диофантовых уравнений и при разработке непрерывные дроби. В расширенный алгоритм Евклида был опубликован английским математиком Николас Сондерсон,^[38] кто приписал это Роджер Котс как метод эффективного вычисления непрерывных дробей.^[39]

В 19 веке алгоритм Евклида привел к развитию новых систем счисления, таких как Гауссовские целые числа и Целые числа Эйзенштейна. В 1815 г. Карл Гаусс использовали алгоритм Евклида, чтобы продемонстрировать уникальную факторизацию Гауссовские целые числа, хотя его работа была впервые опубликована в 1832 году.^[40] Гаусс упомянул алгоритм в своем Disquisitiones Arithmeticae (опубликовано в 1801 г.), но только как метод для непрерывные дроби.^[33] Питер Густав Лежен Дирихле кажется, был первым, кто описал алгоритм Евклида как основу большей части теории чисел.^[41] Лежен Дирихле отметил, что многие результаты теории чисел, такие как уникальная факторизация, будут верны для любой другой системы чисел, к которой можно применить алгоритм Евклида.^[42] Лекции Лежена Дирихле по теории чисел редактировал и дополнял Ричард Дедекинд, который использовал алгоритм Евклида для изучения алгебраические целые числа, новый общий тип номера. Например, Дедекинд первым доказал Теорема Ферма о двух квадратах используя уникальную факторизацию гауссовских целых чисел.^[43] Дедекинд также определил понятие Евклидова область, система счисления, в которой может быть определена обобщенная версия алгоритма Евклида (как описано ниже ). В последние десятилетия XIX века алгоритм Евклида постепенно уступил место более общей теории Дедекинда. идеалы.^[44]

Другие приложения алгоритма Евклида были разработаны в 19 веке. В 1829 г. Чарльз Штурм показал, что алгоритм был полезен в Штурмовая цепь метод подсчета действительных корней многочленов в любом заданном интервале.^[45]

Алгоритм Евклида был первым алгоритм целочисленного отношения, который представляет собой метод нахождения целочисленных отношений между соизмеримыми действительными числами. Несколько романов алгоритмы целочисленных отношений были разработаны, например, алгоритм Геламан Фергюсон и Р.В. Форкэйд (1979)^[46] и LLL алгоритм.^[47][48]

В 1969 году Коул и Дэви разработали игру для двух игроков, основанную на алгоритме Евклида, под названием Игра Евклида,^[49] который имеет оптимальную стратегию.^[50] Игроки начинают с двумя стопками а и б камни. Игроки по очереди снимают м кратно меньшей стопке большей. Таким образом, если две стопки состоят из Икс и у камни, где Икс больше чем у, следующий игрок может уменьшить большую стопку из Икс камни в Икс − мой камни, если последнее является целым неотрицательным числом. Побеждает тот игрок, который первым уменьшит одну стопку камней до нуля.^[51][52]

Математические приложения

Личность Безу

Личность Безу утверждает, что наибольший общий делитель грамм двух целых чисел а и б можно представить как линейную сумму двух исходных чисел а и б.^[53] Другими словами, всегда можно найти целые числа s и т такой, что грамм = са + tb.^[54][55]

Целые числа s и т можно рассчитать из частных q₀, q₁и т.д., изменив порядок уравнений в алгоритме Евклида.^[56] Начиная с предпоследнего уравнения, грамм можно выразить через частное q_N−1 и два предыдущих остатка, р_N−2 и р_N−3:

грамм = р_N−1 = р_N−3 − q_N−1 р_N−2 .

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

р_N−2 = р_N−4 − q_N−2 р_N−3 и

р_N−3 = р_N−5 − q_N−3 р_N−4 .

Подставляя эти формулы для р_N−2 и р_N−3 в первое уравнение дает грамм как линейную сумму остатков р_N−4 и р_N−5. Процесс замены остатков формулами с участием их предшественников может быть продолжен до тех пор, пока исходные числа а и б достигаются:

р₂ = р₀ − q₂ р₁

р₁ = б − q₁ р₀

р₀ = а − q₀ б.

После всего остального р₀, р₁и т. д., окончательное уравнение выражает грамм как линейную сумму а и б: грамм = са + tb. Личность Безу, и, следовательно, предыдущий алгоритм, оба могут быть обобщены в контексте Евклидовы области.

Основные идеалы и связанные с ними проблемы

Тождество Безу дает еще одно определение наибольшего общего делителя грамм двух чисел а и б.^[10] Рассмотрим набор всех чисел ua + vb, куда ты и v - любые два целых числа. С а и б оба делятся на грамм, каждое число в наборе делится на грамм. Другими словами, каждое число в наборе является целым числом, кратным грамм. Это верно для любого общего делителя а и б. Однако, в отличие от других общих делителей, наибольший общий делитель является членом множества; личности Безу, выбрав ты = s и v = т дает грамм. Меньший общий делитель не может быть членом множества, так как каждый член множества должен делиться на грамм. И наоборот, любое кратное м из грамм можно получить, выбрав ты = РС и v = мт, куда s и т являются целыми числами личности Безу. Это можно увидеть, умножив личность Безу на м,

мг = мса + mtb.

Следовательно, набор всех чисел ua + vb эквивалентен множеству кратных м из грамм. Другими словами, множество всех возможных сумм целых кратных двух чисел (а и б) эквивалентен множеству кратных gcd (а, б). Говорят, что НОД является генератором идеальный из а и б. Это определение НОД привело к современному абстрактная алгебраическая концепции главный идеал (идеал, порожденный одним элементом) и главная идеальная область (а домен в котором каждый идеал является главным идеалом).

С помощью этого результата можно решить некоторые проблемы.^[57] Например, рассмотрим две мерные чашки объема. а и б. Добавляя / вычитая ты кратные первой чашки и v кратные второй чашки, любой объем ua + vb можно измерить. Все эти объемы кратны грамм = gcd (а, б).

Расширенный алгоритм Евклида

Целые числа s и т тождества Безу можно эффективно вычислить с помощью расширенный алгоритм Евклида. Это расширение добавляет к алгоритму Евклида два рекурсивных уравнения^[58]

s_k = s_k−2 − q_ks_k−1

т_k = т_k−2 − q_kт_k−1

с начальными значениями

s₋₂ = 1, т₋₂ = 0

s₋₁ = 0, т₋₁ = 1.

Используя эту рекурсию, целые числа Безу s и т даны s = s_N и т = т_N, куда N + 1 шаг, на котором алгоритм завершается с р_{N + 1} = 0.

Справедливость этого подхода можно показать по индукции. Предположим, что формула рекурсии верна до шага k - 1 алгоритм; другими словами, предположим, что

р_j = s_j а + т_j б

для всех j меньше, чем k. В k-й шаг алгоритма дает уравнение

р_k = р_k−2 − q_kр_k−1.

Поскольку формула рекурсии считается правильной для р_k−2 и р_k−1, они могут быть выражены через соответствующие s и т переменные

р_k = (s_k−2 а + т_k−2 б) − q_k(s_k−1 а + т_k−1 б).

Преобразование этого уравнения приводит к формуле рекурсии для шага k, как требуется

р_k = s_k а + т_k б = (s_k−2 − q_ks_k−1) а + (т_k−2 − q_kт_k−1) б.

Матричный метод

Целые числа s и т также можно найти с помощью эквивалента матрица метод.^[59] Последовательность уравнений алгоритма Евклида

${displaystyle {egin {align} a & = q_ {0} b + r_ {0} b & = q_ {1} r_ {0} + r_ {1} & ,,, vdots r_ {N-2} & = q_ {N} r_ {N-1} + 0end {выровнено}}}$

может быть записано как произведение матриц частных 2 на 2, умноженных на двумерный вектор остатка

${displaystyle {egin {pmatrix} a bend {pmatrix}} = {egin {pmatrix} q_ {0} & 1 1 & 0end {pmatrix}} {egin {pmatrix} b r_ {0} end {pmatrix}} = {egin {pmatrix} q_ {0} & 1 1 & 0end {pmatrix}} {egin {pmatrix} q_ {1} & 1 1 & 0end {pmatrix}} {egin {pmatrix} r_ {0} r_ {1} end {pmatrix}} = cdots = prod _ {i = 0} ^ {N} {egin {pmatrix} q_ {i} & 1 1 & 0end {pmatrix}} {egin {pmatrix} r_ {N-1} 0end {pmatrix}} ,.}$

Позволять M представляют собой произведение всех матриц частных

${displaystyle mathbf {M} = {egin {pmatrix} m_ {11} & m_ {12} m_ {21} & m_ {22} end {pmatrix}} = prod _ {i = 0} ^ {N} {egin {pmatrix } q_ {i} & 1 1 & 0end {pmatrix}} = {egin {pmatrix} q_ {0} & 1 1 & 0end {pmatrix}} {egin {pmatrix} q_ {1} & 1 1 & 0end {pmatrix}} cdots {egin {pmatrix} } q_ {N} & 1 1 & 0end {pmatrix}} ,.}$

Это упрощает алгоритм Евклида до вида

${displaystyle {egin {pmatrix} a bend {pmatrix}} = mathbf {M} {egin {pmatrix} r_ {N-1} 0end {pmatrix}} = mathbf {M} {egin {pmatrix} g 0end { pmatrix}} ,.}$

Выражать грамм как линейная сумма а и б, обе части этого уравнения можно умножить на обратный матрицы M.^[59][60] В детерминант из M равно (−1)^N+1, так как он равен произведению определителей факторных матриц, каждая из которых отрицательна. Поскольку определитель M никогда не равен нулю, вектор конечных остатков может быть решен с помощью обратного к M

${displaystyle {egin {pmatrix} g 0end {pmatrix}} = mathbf {M} ^ {- 1} {egin {pmatrix} a bend {pmatrix}} = (- 1) ^ {N + 1} {egin { pmatrix} m_ {22} & - m_ {12} - m_ {21} & m_ {11} end {pmatrix}} {egin {pmatrix} a bend {pmatrix}} ,.}$

Поскольку верхнее уравнение дает

грамм = (−1)^N+1 ( м₂₂ а − м₁₂ б),

два целых числа личности Безу равны s = (−1)^N+1м₂₂ и т = (−1)^Nм₁₂. Матричный метод столь же эффективен, как и эквивалентная рекурсия, с двумя умножениями и двумя сложениями на шаг алгоритма Евклида.

Лемма Евклида и единственная факторизация

Личность Безу важна для многих приложений алгоритма Евклида, таких как демонстрация уникальная факторизация чисел в простые множители.^[61] Чтобы проиллюстрировать это, предположим, что число L можно записать как произведение двух факторов ты и v, то есть, L = УФ. Если другой номер ш также разделяет L но совпадает с ты, тогда ш должен разделить v, по следующему аргументу: если наибольший общий делитель ты и ш равно 1, то целые числа s и т можно найти так, что

1 = вс + tw .

по личности Безу. Умножая обе стороны на v дает отношение

v = внедорожник + twv = sL + twv .

С ш делит оба члена в правой части, он также должен делить левую часть, v. Этот результат известен как Лемма евклида.^[62] В частности, если простое число делит L, то он должен делить хотя бы один множитель L. И наоборот, если число ш взаимно проста с каждым из ряда чисел а₁, а₂, ..., а_п, тогда ш также взаимно прост с их продуктом, а₁ × а₂ × ... × а_п.^[62]

Леммы Евклида достаточно, чтобы доказать, что каждое число имеет уникальное разложение на простые числа.^[63] Чтобы убедиться в этом, предположим противное, что существуют две независимые факторизации L в м и п простые множители соответственно

L = п₁п₂…п_м = q₁q₂…q_п .

Поскольку каждое простое число п разделяет L по предположению, он также должен делить один из q факторы; поскольку каждый q тоже простое, это должно быть так п = q. Итеративное деление на п факторов показывает, что каждый п имеет равный аналог q; две простые факторизации идентичны, за исключением их порядка. Уникальное разложение чисел на простые числа имеет множество применений в математических доказательствах, как показано ниже.

Линейные диофантовы уравнения

Участок линейного Диофантово уравнение, 9Икс + 12у = 483. Решения показаны синими кружками.

Диофантовы уравнения - уравнения, решения в которых ограничены целыми числами; они названы в честь александрийского математика 3-го века Диофант.^[64] Типичный линейный Диофантово уравнение ищет целые числа Икс и у такой, что^[65]

топор + к = c

куда а, б и c даны целые числа. Это можно записать в виде уравнения для Икс в модульная арифметика:

топор ≡ c мод б.

Позволять грамм быть наибольшим общим делителем а и б. Оба термина в топор + к делятся на грамм; следовательно, c также должно делиться на грамм, либо уравнение не имеет решений. Разделив обе стороны на c/грамм, уравнение сводится к тождеству Безу

са + tb = грамм

куда s и т можно найти по расширенный алгоритм Евклида.^[66] Это дает одно решение диофантова уравнения, Икс₁ = s (c/грамм) и у₁ = т (c/грамм).

В общем случае линейное диофантово уравнение не имеет решений или имеет бесконечное число решений.^[67] Чтобы найти последнее, рассмотрим два решения: (Икс₁, у₁) и (Икс₂, у₂), куда

топор₁ + к₁ = c = топор₂ + к₂

или эквивалентно

а(Икс₁ − Икс₂) = б(у₂ − у₁).

Поэтому наименьшая разница между двумя Икс решения б/грамм, тогда как наименьшая разница между двумя у решения а/грамм. Таким образом, решения могут быть выражены как

Икс = Икс₁ − бу/грамм

у = у₁ + au/грамм.

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

Мультипликативные инверсии и алгоритм RSA

А конечное поле представляет собой набор чисел с четырьмя обобщенными операциями. Эти операции называются сложением, вычитанием, умножением и делением и имеют свои обычные свойства, такие как коммутативность, ассоциативность и распределенность. Примером конечного поля является набор из 13 чисел {0, 1, 2, ..., 12} с использованием модульная арифметика. В этом поле сокращаются результаты любой математической операции (сложение, вычитание, умножение или деление). по модулю 13; то есть числа, кратные 13, добавляются или вычитаются, пока результат не будет находиться в диапазоне 0–12. Например, результат 5 × 7 = 35 mod 13 = 9. Такие конечные поля могут быть определены для любого простого числа. п; используя более сложные определения, они также могут быть определены для любой мощности м премьер п ^м. Конечные поля часто называют Галуа поля, и сокращенно GF (п) или GF (п ^м).

В таком поле с м числа, каждый ненулевой элемент а имеет уникальный модульный мультипликативный обратный, а⁻¹ такой, что аа⁻¹ = а⁻¹а ≡ 1 модм. Это обратное можно найти, решив уравнение сравнения топор ≡ 1 модм,^[69] или эквивалентное линейное диофантово уравнение^[70]

топор + мой = 1.

Это уравнение можно решить с помощью алгоритма Евклида, как описано над. Нахождение мультипликативных инверсий - важный шаг в Алгоритм RSA, который широко используется в электронная коммерция; в частности, уравнение определяет целое число, используемое для дешифрования сообщения.^[71] Хотя алгоритм RSA использует кольца вместо полей, алгоритм Евклида все еще может использоваться для нахождения мультипликативного обратного, если он существует. У алгоритма Евклида есть и другие приложения в коды с исправлением ошибок; например, его можно использовать как альтернативу Алгоритм Берлекампа-Месси для расшифровки BCH и Коды Рида – Соломона, основанные на полях Галуа.^[72]

Китайская теорема об остатках

Алгоритм Евклида также можно использовать для решения нескольких линейных диофантовых уравнений.^[73] Такие уравнения возникают в Китайская теорема об остатках, который описывает новый метод представления целого числа Икс. Вместо представления целого числа цифрами оно может быть представлено остатками Икс_я по модулю набора N взаимно простые числа м_я:^[74]

${displaystyle {egin {выровнено} x_ {1} & Equiv x {pmod {m_ {1}}} x_ {2} & Equiv x {pmod {m_ {2}}} & ,,, vdots x_ {N} & Equiv x {pmod {m_ {N}}} ,. конец {выровнено}}}$

Цель - определить Икс из его N остатки Икс_я. Решение состоит в том, чтобы объединить несколько уравнений в одно линейное диофантово уравнение с гораздо большим модулем M это продукт всех индивидуальных модулей м_я, и определим M_я в качестве

${displaystyle M_ {i} = {frac {M} {m_ {i}}}.}$

Таким образом, каждый M_я является произведением всех модулей Кроме м_я. Решение зависит от поиска N новые номера час_я такой, что

${displaystyle M_ {i} h_ {i} Equiv 1 {pmod {m_ {i}}} ,.}$

С этими числами час_я, любое целое число Икс может быть восстановлен по его остаткам Икс_я по уравнению

${displaystyle xequiv (x_ {1} M_ {1} h_ {1} + x_ {2} M_ {2} h_ {2} + cdots + x_ {N} M_ {N} h_ {N}) {pmod {M} } ,.}$

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

Стерн – Броко

Алгоритм Евклида можно использовать для упорядочивания множества всех положительных рациональное число в бесконечность двоичное дерево поиска, называется Стерн – Броко Число 1 (выраженное дробью 1/1) помещается в корень дерева, а расположение любого другого числа а/б можно найти, вычислив gcd (а,б) с использованием исходной формы алгоритма Евклида, в котором каждый шаг заменяет большее из двух заданных чисел его разницей на меньшее число (не его остаток), останавливаясь при достижении двух равных чисел. Шаг алгоритма Евклида, который заменяет первое из двух чисел, соответствует шагу в дереве от узла до его правого дочернего элемента, а шаг, который заменяет второе из двух чисел, соответствует шагу в дереве от узла. слева от него. Построенная таким образом последовательность шагов не зависит от того, а/б дается в наименьших терминах и образует путь от корня до узла, содержащего число а/б.^[75] Этот факт можно использовать, чтобы доказать, что каждое положительное рациональное число встречается в этом дереве ровно один раз.

Например, 3/4 можно найти, начав с корня, перейдя один раз влево, а затем дважды вправо:

Дерево Штерна – Броко и последовательности Штерна – Броко порядка я за я = 1, 2, 3, 4

${displaystyle {egin {выровнен} & gcd (3,4) & leftarrow = {} & gcd (3,1) & ightarrow = {} & gcd (2,1) & ightarrow = {} & gcd (1,1) .end {выровнен }}}$

Алгоритм Евклида имеет почти такое же отношение к другому двоичному дереву рациональных чисел, называемому Дерево Калкина – Уилфа. Разница в том, что путь является обратным: вместо создания пути от корня дерева к цели, он создает путь от цели к корню.

Непрерывные дроби

Алгоритм Евклида тесно связан с непрерывные дроби.^[76] Последовательность уравнений можно записать в виде

${displaystyle {egin {align} {frac {a} {b}} & = q_ {0} + {frac {r_ {0}} {b}} {frac {b} {r_ {0}}} & = q_ {1} + {frac {r_ {1}} {r_ {0}}} {frac {r_ {0}} {r_ {1}}} & = q_ {2} + {frac {r_ {2}) } {r_ {1}}} & ,,, vdots {frac {r_ {k-2}} {r_ {k-1}}} & = q_ {k} + {frac {r_ {k}} { r_ {k-1}}} & ,,, vdots {frac {r_ {N-2}} {r_ {N-1}}} & = q_ {N} ,. конец {выровнено}}}$

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

${displaystyle {frac {a} {b}} = q_ {0} + {cfrac {1} {q_ {1} + {cfrac {r_ {1}} {r_ {0}}}}} ,.}$

Третье уравнение можно использовать для замены члена знаменателя р₁/р₀, уступая

${displaystyle {frac {a} {b}} = q_ {0} + {cfrac {1} {q_ {1} + {cfrac {1} {q_ {2}} + {cfrac {r_ {2}} {r_ {) 1}}}}}}} ,.}$

Окончательное соотношение остатков р_k/р_k−1 всегда можно заменить, используя следующее уравнение в серии, вплоть до последнего уравнения. Результат - непрерывная дробь

${displaystyle {frac {a} {b}} = q_ {0} + {cfrac {1} {q_ {1} + {cfrac {1} {q_ {2}} + {cfrac {1} {ddots + {cfrac {) 1} {q_ {N}}}}}}}}} = [q_ {0}; q_ {1}, q_ {2}, ldots, q_ {N}] ,.}$

В отработанном примере над, был вычислен НОД (1071, 462), а частные q_k были 2, 3 и 7 соответственно. Следовательно, дробь 1071/462 может быть записана

${displaystyle {frac {1071} {462}} = 2+ {cfrac {1} {3+ {cfrac {1} {7}}}} = [2; 3,7]}$

что подтверждается расчетом.

Алгоритмы факторизации

Вычисление наибольшего общего делителя - важный шаг в нескольких целочисленная факторизация алгоритмы,^[77] Такие как Алгоритм ро Полларда,^[78] Алгоритм Шора,^[79] Метод факторизации Диксона^[80] и Факторизация эллиптической кривой Ленстры.^[81] Для эффективного нахождения этого НОД можно использовать алгоритм Евклида. Факторизация непрерывной дроби использует непрерывные дроби, которые определяются с помощью алгоритма Евклида.^[82]

Алгоритмическая эффективность

Количество шагов в алгоритме Евклида для gcd (Икс,у). Светлые (красные и желтые) точки указывают на относительно небольшое количество шагов, тогда как более темные (фиолетовые и синие) точки указывают на большее количество шагов. Самая большая темная область следует за линией у = Φx, куда Φ это Золотое сечение.

Вычислительная эффективность алгоритма Евклида тщательно изучена.^[83] Эту эффективность можно описать числом шагов деления, которое требует алгоритм, умноженным на вычислительные затраты на каждый шаг. Первый известный анализ алгоритма Евклида принадлежит А.А.Л. Рейно в 1811 г.^[84] кто показал, что количество шагов деления на входе (ты, v) ограничен v; позже он улучшил это до v/ 2 + 2. Позже, в 1841 г., П. Дж. Э. Финк показал^[85] что количество шагов деления не превышает 2 log₂ v + 1, и, следовательно, алгоритм Евклида работает во времени, полиномиальном от размера входных данных.^[86] Эмиль Леже в 1837 г. изучал худший случай, когда входы последовательные Числа Фибоначчи.^[86] Анализ Финка был уточнен Габриэль Ламе в 1844 г.,^[87] кто показал, что количество шагов, необходимых для выполнения, никогда не превышает пятикратное количество час десятичных цифр меньшего числаб.^[88][89]

в модель единой стоимости (подходит для анализа сложности вычисления НОД для чисел, которые укладываются в одно машинное слово), каждый шаг алгоритма занимает постоянное время, и анализ Ламе подразумевает, что общее время работы также О(час). Однако в модели вычислений, подходящей для вычислений с большими числами, вычислительные затраты на вычисление одного остатка в алгоритме могут достигать О(час²).^[90] В этом случае общее время для всех шагов алгоритма можно проанализировать с помощью телескопическая серия, показывая, что это также О(час²). Современные алгоритмические техники, основанные на Алгоритм Шёнхаге – Штрассена для быстрого целочисленного умножения может использоваться, чтобы ускорить это, что приводит к квазилинейные алгоритмы для НОД.^[91][92]

Кол-во ступеней

Количество шагов для вычисления НОД двух натуральных чисел, а и б, может быть обозначено Т(а, б).^[93] Если грамм это НОД а и б, тогда а = мг и б = нг для двух взаимно простых чисел м и п. потом

Т(а, б) = Т(м, п)

как можно увидеть, разделив все шаги в алгоритме Евклида на грамм.^[94] По тому же аргументу количество шагов остается прежним, если а и б умножаются на общий коэффициент ш: Т(а, б) = Т(ва, wb). Следовательно, количество ступеней Т может сильно различаться между соседними парами чисел, например T (а, б) и т(а, б + 1), в зависимости от размера двух НОД.

Рекурсивный характер алгоритма Евклида дает еще одно уравнение

Т(а, б) = 1 + Т(б, р₀) = 2 + Т(р₀, р₁) = … = N + Т(р_N−2, р_N−1) = N + 1

куда Т(Икс, 0) = 0 по предположению.^[93]

Худший случай

Если алгоритм Евклида требует N шаги для пары натуральных чисел а > б > 0 наименьшие значения а и б для которых это верно, являются Числа Фибоначчи F_N+2 и F_N+1, соответственно.^[95] Точнее, если алгоритм Евклида требует N шаги для пары а > б, то есть а ≥ F_N+2 и б ≥ F_N+1. Это можно показать индукция.^[96] Если N = 1, б разделяет а без остатка; наименьшие натуральные числа, для которых это верно, б = 1 и а = 2, которые F₂ и F₃, соответственно. Теперь предположим, что результат верен для всех значений N вплоть до M - 1. Первый шаг M-шаговый алгоритм а = q₀б + р₀, а алгоритм Евклида требует M - 1 ступенька для пары б > р₀. По предположению индукции имеем б ≥ F_M+1 и р₀ ≥ F_M. Следовательно, а = q₀б + р₀ ≥ б + р₀ ≥ F_M+1 + F_M = F_M+2, которое является искомым неравенством. Это доказательство, опубликованное Габриэль Ламе в 1844 г., представляет собой начало теория сложности вычислений,^[97] а также первое практическое применение чисел Фибоначчи.^[95]

Этого результата достаточно, чтобы показать, что количество шагов в алгоритме Евклида никогда не может превышать количество его цифр более чем в пять раз (основание 10).^[98] Если алгоритм требует N шаги, то б Больше или равно F_N+1 что, в свою очередь, больше или равно φ^N−1, куда φ это Золотое сечение. С б ≥ φ^N−1, тогда N - 1 ≤ журнал_φб. Поскольку журнал₁₀φ > 1/5, (N - 1) / 5 <журнал₁₀φ бревно_φб = журнал₁₀б. Таким образом, N ≤ 5 журнал₁₀б. Таким образом, алгоритм Евклида всегда требует меньше, чем О(час) подразделения, где час это количество цифр в меньшем числе б.

Средний

Среднее количество шагов, выполняемых алгоритмом Евклида, было определено тремя различными способами. Первое определение - это среднее время Т(а), необходимого для расчета НОД заданного числа а и меньшее натуральное число б выбираются с равной вероятностью из целых чисел от 0 до а − 1^[93]

${displaystyle T (a) = {frac {1} {a}} sum _ {0leq b$

Однако, поскольку Т(а, б) сильно колеблется в зависимости от НОД двух чисел, усредненная функция Т(а) также "шумно".^[99]

Чтобы уменьшить этот шум, второй средний τ(а) берется по всем числам, взаимно простым с а

${displaystyle au (a) = {frac {1} {varphi (a)}} sum _ {egin {smallmatrix} 0leq b$

Есть φ(а) взаимно простые целые числа меньше а, куда φ является Функция Эйлера. Это среднее значение тау плавно растет с а^[100][101]

${displaystyle au (a) = {frac {12} {pi ^ {2}}} ln 2ln a + C + O (a ^ {- 1/6-varepsilon})}$

с остаточной ошибкой порядка а^{−(1/6) + ε}, куда ε является бесконечно малый. Постоянная C (Константа Портера^[102]) в этой формуле равно

${displaystyle C = - {frac {1} {2}} + {frac {6ln 2} {pi ^ {2}}} left (4gamma - {frac {24} {pi ^ {2}}} zeta '(2 ) + 3ln 2-2ight) примерно 1,467}$

куда γ это Константа Эйлера – Маскерони а ζ '- производная из Дзета-функция Римана.^[103][104] Старший коэффициент (12 / π²) ln 2 определяли двумя независимыми методами.^[105][106]

Поскольку первое среднее значение может быть вычислено из среднего тау путем суммирования по делителям d иза^[107]

${displaystyle T (a) = {frac {1} {a}} sum _ {dmid a} varphi (d) au (d)}$

его можно аппроксимировать формулой^[108]

${displaystyle T (a) приблизительно C + {frac {12} {pi ^ {2}}} ln 2left (ln a-sum _ {dmid a} {frac {Lambda (d)} {d}} ight)}$

где Λ (d) это Функция Мангольдта.^[109]

Третье среднее Y(п) определяется как среднее количество шагов, необходимых, когда оба а и б выбираются случайным образом (с равномерным распределением) от 1 до п^[108]

${displaystyle Y (n) = {frac {1} {n ^ {2}}} sum _ {a = 1} ^ {n} sum _ {b = 1} ^ {n} T (a, b) = { frac {1} {n}} sum _ {a = 1} ^ {n} T (a).}$

Подставляя приближенную формулу для Т(а) в это уравнение дает оценку для Y(п)^[110]

${displaystyle Y (n) приблизительно {frac {12} {pi ^ {2}}} ln 2ln n + 0,06.}$

Вычислительные затраты на шаг

На каждом шагу k алгоритма Евклида, фактор q_k и остальное р_k вычисляются для данной пары целых чисел р_k−2 и р_k−1

р_k−2 = q_k р_k−1 + р_k.

Вычислительные затраты на шаг связаны в основном с поиском q_k, так как остаток р_k можно быстро рассчитать из р_k−2, р_k−1, и q_k

р_k = р_k−2 − q_k р_k−1.

Вычислительные затраты на деление час-битовые числа масштабируются как О(час(ℓ+1)), где ℓ - длина частного.^[90]

Для сравнения: оригинальный алгоритм Евклида, основанный на вычитании, может быть намного медленнее. Одно целочисленное деление эквивалентно частному q количество вычитаний. Если соотношение а и б очень велико, частное велико, и потребуется много вычитаний. С другой стороны, было показано, что частные с большой вероятностью будут небольшими целыми числами. Вероятность данного частного q примерно ln |ты/(ты - 1) | куда ты = (q + 1)².^[111] Для иллюстрации вероятность частного 1, 2, 3 или 4 составляет примерно 41,5%, 17,0%, 9,3% и 5,9% соответственно. Так как операция вычитания быстрее деления, особенно для больших чисел,^[112] алгоритм Евклида, основанный на вычитании, конкурирует с версией, основанной на делении.^[113] Это эксплуатируется в двоичная версия алгоритма Евклида.^[114]

Комбинирование расчетного количества шагов с расчетными вычислительными затратами на шаг показывает, что алгоритм Евклида растет квадратично (час²) со средним количеством цифр час в первых двух числах а и б. Позволять час₀, час₁, ..., час_N−1 представляют количество цифр в последовательных остатках р₀, р₁, ..., р_N−1. Поскольку количество ступеней N растет линейно с час, время работы ограничено

${displaystyle O {Big (} sum _ {i$

Альтернативные методы

Алгоритм Евклида широко используется на практике, особенно для малых чисел, из-за своей простоты.^[115] Для сравнения можно определить эффективность альтернатив алгоритму Евклида.

Один неэффективный подход к нахождению НОД двух натуральных чисел а и б вычислить все их общие делители; НОД тогда является наибольшим общим делителем. Общие делители можно найти, разделив оба числа на последовательные целые числа от 2 до меньшего числа. б. Количество шагов этого подхода линейно растет с увеличением б, или экспоненциально по количеству цифр. Другой неэффективный подход - найти простые множители одного или обоих чисел. Как указано над, НОД равняется произведению простых множителей двух чисел а и б.^[6] Настоящие методы для простые множители также неэффективны; многие современные системы криптографии даже полагаются на эту неэффективность.^[9]

В двоичный алгоритм GCD - эффективная альтернатива, которая заменяет деление более быстрыми операциями за счет использования двоичный представление, используемое компьютерами.^[116][117] Однако эта альтернатива также масштабируется как О(час²). Как правило, он быстрее, чем алгоритм Евклида на реальных компьютерах, хотя масштабируется таким же образом.^[91] Дополнительную эффективность можно получить, изучив только первые цифры двух чисел. а и б.^[118][119] Бинарный алгоритм может быть расширен на другие базы (k-арные алгоритмы),^[120] с пятикратным увеличением скорости.^[121] Алгоритм Лемера GCD использует тот же общий принцип, что и двоичный алгоритм, для ускорения вычислений GCD с произвольной базой.

Рекурсивный подход для очень больших целых чисел (более 25000 цифр) приводит к квазилинейный целочисленные алгоритмы НОД,^[122] такие как у Шёнхаге,^[123][124] и Stehlé и Zimmermann.^[125] Эти алгоритмы используют матричную форму 2 × 2 алгоритма Евклида, заданного над. Эти квазилинейные методы обычно масштабируются как О(час (бревно час)² (журнал журнал час)).^[91][92]

Обобщения

Хотя алгоритм Евклида используется для нахождения наибольшего общего делителя двух натуральных чисел (положительных целых чисел), он может быть обобщен на действительные числа и другие математические объекты, такие как многочлены,^[126] квадратичные целые числа^[127] и Кватернионы Гурвица.^[128] В последних случаях алгоритм Евклида используется для демонстрации ключевого свойства уникальной факторизации, то есть того, что такие числа могут быть однозначно разложены на множители. неприводимые элементы, аналоги простых чисел. Уникальная факторизация необходима для многих доказательств теории чисел.

Рациональные и действительные числа

Алгоритм Евклида можно применить к действительные числа, как описано Евклидом в книге 10 его Элементы. Цель алгоритма - определить реальное число грамм такие, что два заданных действительных числа, а и б, являются целыми кратными ему: а = мг и б = нг, куда м и п находятся целые числа.^[26] Это отождествление эквивалентно нахождению целочисленное отношение среди реальных чисел а и б; то есть определяет целые числа s и т такой, что са + tb = 0. Евклид использует этот алгоритм для решения вопроса о несоизмеримые длины.^[129][130]

Алгоритм Евклида с действительными числами отличается от своего целочисленного аналога в двух отношениях. Во-первых, остатки р_k являются действительными числами, хотя частные q_k как и раньше, являются целыми числами. Во-вторых, не гарантируется, что алгоритм закончит конечное число N шагов. Если это так, дробь а/б - рациональное число, то есть отношение двух целых чисел

${displaystyle {frac {a} {b}} = {frac {mg} {ng}} = {frac {m} {n}},}$

и может быть записана в виде конечной цепной дроби [q₀; q₁, q₂, ..., q_N]. Если алгоритм не останавливается, дробь а/б является иррациональный номер и описывается бесконечной цепной дробью [q₀; q₁, q₂, …].^[131] Примеры бесконечных цепных дробей: Золотое сечение φ = [1; 1, 1, ...] и квадратный корень из двух, √2 = [1; 2, 2, ...].^[132] Алгоритм вряд ли остановится, так как почти все соотношения а/б двух действительных чисел иррациональны.^[133]

Бесконечная цепная дробь может быть усечена на шаге k [q₀; q₁, q₂, ..., q_k] чтобы приблизиться к а/б это улучшается как k увеличена. Приближение описывается формулой сходящиеся м_k/п_k; числитель и знаменатели взаимно просты и подчиняются отношение повторения

${displaystyle {egin {align} m_ {k} & = q_ {k} m_ {k-1} + m_ {k-2} n_ {k} & = q_ {k} n_ {k-1} + n_ { k-2}, конец {выровнен}}}$

куда м₋₁ = п₋₂ = 1 и м₋₂ = п₋₁ = 0 - начальные значения рекурсии. Сходящийся м_k/п_k лучший Рациональное число приближение к а/б со знаменателем п_k:^[134]

${displaystyle left | {frac {a} {b}} - {frac {m_ {k}} {n_ {k}}} ight | <{frac {1} {n_ {k} ^ {2}}}.}$

Полиномы

Многочлены от одной переменной Икс можно складывать, умножать и разложить на неприводимые многочлены, которые являются аналогами простых чисел для целых чисел. Многочлен наибольшего общего делителя грамм(Икс) двух многочленов а(Икс) и б(Икс) определяется как произведение их общих неприводимых многочленов, которые можно идентифицировать с помощью алгоритма Евклида.^[126] Основная процедура аналогична работе с целыми числами. На каждом шагу k, фактор-полином q_k(Икс) и полином остатка р_k(Икс) идентифицируются так, чтобы удовлетворять рекурсивному уравнению

${Displaystyle r_ {k-2} (x) = q_ {k} (x) r_ {k-1} (x) + r_ {k} (x),}$

куда р₋₂(Икс) = а(Икс) и р₋₁(Икс) = б(Икс). Каждый фактор-полином выбирается таким образом, чтобы каждый остаток был либо равен нулю, либо имел степень меньше, чем степень его предшественника: град [р_k(Икс)] р_k−1(Икс)]. Поскольку степень является неотрицательным целым числом и уменьшается с каждым шагом, алгоритм Евклида завершается за конечное число шагов. Последний ненулевой остаток - это наибольший общий делитель двух исходных многочленов, а(Икс) и б(Икс).^[135]

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

${displaystyle {egin {выравнивается} a (x) & = x ^ {4} -4x ^ {3} + 4x ^ {2} -3x + 14 = (x ^ {2} -5x + 7) (x ^ { 2} + x + 2) qquad {ext {and}} b (x) & = x ^ {4} + 8x ^ {3} + 12x ^ {2} + 17x + 6 = (x ^ {2} + 7x + 3) (x ^ {2} + x + 2) .end {выровнено}}}$

Разделение а(Икс) к б(Икс) дает остаток р₀(Икс) = Икс³ + (2/3)Икс² + (5/3)Икс − (2/3). На следующем этапе б(Икс) делится на р₀(Икс) дающий остаток р₁(Икс) = Икс² + Икс + 2. Наконец, разделив р₀(Икс) к р₁(Икс) дает нулевой остаток, указывая, что р₁(Икс) является полиномом наибольшего общего делителя а(Икс) и б(Икс), в соответствии с их факторизацией.

Многие из приложений, описанных выше для целых чисел, переносятся на полиномы.^[136] Алгоритм Евклида можно использовать для решения линейных диофантовых уравнений и китайских задач остатка для многочленов; также могут быть определены непрерывные дроби многочленов.

У полиномиального алгоритма Евклида есть и другие приложения, например Цепи Штурма, метод подсчета нули полинома что лежат внутри данного реальный интервал.^[137] Это, в свою очередь, имеет приложения в нескольких областях, таких как Критерий устойчивости Рауса – Гурвица. в теория управления.^[138]

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

Гауссовские целые числа

Распределение гауссовских простых чисел ты + vi в комплексной плоскости, с нормами ты² + v² менее 500

Целые гауссовы числа сложные числа формы α = ты + vi, куда ты и v обычные целые числа^{[заметка 2]} и я это квадратный корень из отрицательного.^[139] Определяя аналог алгоритма Евклида, можно показать, что гауссовские целые числа однозначно факторизуемы с помощью аргумента над.^[40] Эта уникальная факторизация полезна во многих приложениях, например при выводе всех Пифагорейские тройки или доказывая Теорема Ферма о суммах двух квадратов.^[139] В целом алгоритм Евклида удобен в таких приложениях, но не является существенным; например, теоремы часто можно доказать другими аргументами.

Алгоритм Евклида, разработанный для двух целых гауссовских чисел α и β почти такая же, как и для обычных целых чисел,^[140] но отличается в двух отношениях. Как и раньше, задача на каждом шаге k заключается в определении частного q_k и остаток р_k такой, что

${displaystyle r_ {k} = r_ {k-2} -q_ {k} r_ {k-1},}$

куда р_k−2 = α, куда р_k−1 = β, и где каждый остаток строго меньше, чем его предшественник: |р_k| < |р_k−1|. Первое отличие состоит в том, что частные и остатки сами являются целыми гауссовскими числами и, следовательно, являются сложные числа. Факторы q_k обычно находятся путем округления действительной и комплексной частей точного отношения (например, комплексного числа α/β) до ближайших целых чисел.^[140] Второе отличие состоит в необходимости определения того, как один комплексный остаток может быть «меньше» другого. Для этого функция нормы ж(ты + vi) = ты² + v² определено, которое преобразует каждое целое гауссовское число ты + vi в обычное целое число. После каждого шага k алгоритма Евклида норма остатка ж(р_k) меньше нормы предыдущего остатка, ж(р_k−1). Поскольку норма является неотрицательным целым числом и уменьшается с каждым шагом, алгоритм Евклида для целых гауссовских чисел завершается за конечное число шагов.^[141] Последний ненулевой остаток равен gcd (α, β), гауссовское целое число наибольшей нормы, которое делит оба α и β; он уникален с точностью до умножения на единицу, ±1 или же ±я.^[142]

Многие другие приложения алгоритма Евклида переносятся на гауссовские целые числа. Например, его можно использовать для решения линейных диофантовых уравнений и китайских задач остатка для гауссовских целых чисел;^[143] также могут быть определены цепные дроби гауссовских целых чисел.^[140]

Евклидовы области

Набор элементов на двоих бинарные операции, обозначаемые как сложение и умножение, называется Евклидова область если он образует коммутативное кольцо р и, грубо говоря, если на них можно выполнить обобщенный алгоритм Евклида.^[144][145] Две операции такого кольца не обязательно должны быть сложением и умножением в обычной арифметике; скорее, они могут быть более общими, например, операции математическая группа или же моноид. Тем не менее, эти общие операции должны соответствовать многим законам, регулирующим обычную арифметику, например: коммутативность, ассоциативность и распределенность.

Обобщенный алгоритм Евклида требует Евклидова функция, т.е. отображение ж из р в множество неотрицательных целых чисел, таких что для любых двух ненулевых элементов а и б в р, существуют q и р в р такой, что а = qb + р и ж(р) < ж(б).^[146] Примерами таких отображений являются абсолютное значение для целых чисел, степень для одномерные многочлены, а норма для целых гауссовских чисел над.^[147][148] Основной принцип заключается в том, что каждый шаг алгоритма уменьшает ж неумолимо; следовательно, если ж может быть сокращен только конечное количество раз, алгоритм должен остановиться за конечное количество шагов. Этот принцип основан на хороший порядок свойство неотрицательных целых чисел, которое утверждает, что каждый непустой набор неотрицательных целых чисел имеет наименьший член.^[149]

В основная теорема арифметики применяется к любому евклидовому домену: любое число из евклидовой области может быть однозначно разложено на неприводимые элементы. Любая евклидова область - это уникальная область факторизации (UFD), хотя обратное неверно.^[149] Евклидовы области и UFD являются подклассами GCD домены, области, в которых всегда существует наибольший общий делитель двух чисел.^[150] Другими словами, может существовать наибольший общий делитель (для всех пар элементов в области), хотя его невозможно найти с помощью алгоритма Евклида. Евклидова область всегда главная идеальная область (PID), область целостности в котором каждый идеальный это главный идеал.^[151] И снова обратное неверно: не каждый PID является евклидовой областью.

Уникальная факторизация евклидовых областей полезна во многих приложениях. Например, уникальная факторизация гауссовских целых чисел удобна при выводе формул для всех Пифагорейские тройки и в доказательстве Теорема Ферма о суммах двух квадратов.^[139] Уникальная факторизация также была ключевым элементом в попытке доказательства Последняя теорема Ферма опубликовано в 1847 году Габриэлем Ламе, тем же математиком, который проанализировал эффективность алгоритма Евклида, основываясь на предположении Джозеф Лиувиль.^[152] Подход Ламе потребовал уникальной факторизации чисел вида Икс + ωy, куда Икс и у целые числа, и ω = е^2я/п является пкорень -й степени из 1, то есть ω^п = 1. Хотя этот подход успешен для некоторых значений п (Такие как п = 3, то Целые числа Эйзенштейна ), в целом такие числа нет фактор однозначно. Эта неудача уникальной факторизации в некоторых циклотомические поля вел Эрнст Куммер к концепции идеальные числа и позже, Ричард Дедекинд к идеалы.^[153]

Уникальная факторизация квадратичных целых чисел

Распределение простых чисел Эйзенштейна ты + vω в комплексной плоскости, с нормами менее 500. Количество ω это кубический корень из 1.

В квадратичное целое число кольца полезны для иллюстрации евклидовых областей. Квадратичные целые числа являются обобщениями гауссовских целых чисел, в которых мнимая единица я заменяется числом ω. Таким образом, они имеют вид ты + vω, куда ты и v целые числа и ω имеет одну из двух форм, в зависимости от параметра D. Если D не равно четырем плюс один, тогда

${displaystyle omega = {sqrt {D}}.}$

Если, однако, D равно кратному четырем плюс одному, тогда

${displaystyle omega = {frac {1+ {sqrt {D}}} {2}}.}$

Если функция ж соответствует норма функция, такая как та, которая используется для упорядочивания целых чисел Гаусса над, то домен известен как норм-евклидова. Норм-евклидовы кольца целых квадратичных чисел - это в точности те кольца, в которых D является одним из значений −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, или 73.^[154][155] Случаи D = −1 и D = −3 дать Гауссовские целые числа и Целые числа Эйзенштейна, соответственно.

Если ж может быть любой евклидовой функцией, то список возможных значений D для которой область евклидова, пока не известно.^[156] Первый пример евклидовой области, которая не была евклидовой по норме (с D = 69) был опубликован в 1994 году.^[156] В 1973 году Вайнбергер доказал, что квадратичное целочисленное кольцо с D > 0 евклидово тогда и только тогда, когда оно главная идеальная область при условии, что обобщенная гипотеза Римана держит.^[127]

Некоммутативные кольца

Алгоритм Евклида может быть применен к некоторым некоммутативным кольцам, таким как набор Кватернионы Гурвица.^{[требуется разъяснение ][128]} Позволять α и β представляют собой два элемента из такого кольца. У них общий правый делитель δ если α = ξδ и β = ηδ для некоторого выбора ξ и η в ринге. Точно так же у них есть общий левый делитель, если α = dξ и β = dη для некоторого выбора ξ и η в ринге. Поскольку умножение не коммутативно, существует две версии алгоритма Евклида: одна для правых делителей, другая для левых делителей.^[128] Выбор правильных делителей - первый шаг в поиске gcd (α, β) алгоритмом Евклида можно записать

${displaystyle ho _ {0} = alpha -psi _ {0} eta = (xi -psi _ {0} eta) delta,}$

куда ψ₀ представляет собой частное и ρ₀ остаток.^{[требуется разъяснение ]} Это уравнение показывает, что любой общий правый делитель числа α и β также является общим делителем остатка ρ₀. Аналогичное уравнение для левых делителей будет

${displaystyle ho _ {0} = alpha - eta psi _ {0} = delta (xi -eta psi _ {0}).}$

При любом выборе процесс повторяется, как указано выше, до тех пор, пока не будет определен наибольший общий правый или левый делитель. Как и в евклидовой области, «размер» остатка ρ₀ должен быть строго меньше чем β, и должно быть только конечное число возможных размеров для ρ₀, так что алгоритм гарантированно завершится.^{[требуется разъяснение ][157]}

Большинство результатов для НОД переносятся на некоммутативные числа.^{[требуется разъяснение ]} Например, Личность Безу заявляет, что право gcd (α, β) можно выразить как линейную комбинацию α и β.^[158] Другими словами, есть числа σ и τ такой, что

${displaystyle Gamma _ {ext {right}} = sigma alpha + au eta.}$

Аналогичная идентичность для левого НОД почти такая же:

${displaystyle Gamma _ {ext {left}} = alpha sigma + eta au.}$

Тождество Безу можно использовать для решения диофантовых уравнений. Например, одно из стандартных доказательств Теорема Лагранжа о четырех квадратах, что каждое положительное целое число может быть представлено в виде суммы четырех квадратов, основано на кватернионных НОД таким образом.^[157]

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

• Евклидов ритм, метод использования алгоритма Евклида для генерации музыкальных ритмов.

Примечания

Рекомендации

Библиография

• Коэн, Х. (1993). Курс вычислительной алгебраической теории чисел. Нью-Йорк: Springer-Verlag. ISBN  0-387-55640-0.CS1 maint: ref = harv (связь)
• Кон, Х. (1962). Расширенная теория чисел. Нью-Йорк: Дувр. ISBN  0-486-64023-X.CS1 maint: ref = harv (связь)
• Кокс, Д.; Little, J .; О'Ши, Д. (1997). Идеалы, многообразия и алгоритмы: введение в вычислительную алгебраическую геометрию и коммутативную алгебру (2-е изд.). Springer-Verlag. ISBN  0-387-94680-2.CS1 maint: ref = harv (связь)
• Крэндалл, Р.; Померанс, К. (2001). Простые числа: вычислительная перспектива (1-е изд.). Нью-Йорк: Springer-Verlag. ISBN  0-387-94777-9.CS1 maint: ref = harv (связь)
• Лежен Дирихле, П. (1894). Дедекинд, Ричард (ред.). Vorlesungen über Zahlentheorie (Лекции по теории чисел) (на немецком). Брауншвейг: Vieweg. LCCN  03005859. OCLC  490186017.CS1 maint: ref = harv (связь). Смотрите также Vorlesungen über Zahlentheorie
• Кнут, Д. Э. (1997). Искусство программирования, Том 2: Получисленные алгоритмы (3-е изд.). Аддисон-Уэсли. ISBN  0-201-89684-2.CS1 maint: ref = harv (связь)
• Левек, В. Дж. (1996) [1977]. Основы теории чисел. Нью-Йорк: Дувр. ISBN  0-486-68906-9.CS1 maint: ref = harv (связь)
• Моллин, Р. А. (2008). Фундаментальная теория чисел с приложениями (2-е изд.). Бока-Ратон: Чепмен и Холл / CRC. ISBN  978-1-4200-6659-3.CS1 maint: ref = harv (связь)
• Руда, О. (1948). Теория чисел и ее история. Нью-Йорк: Макгроу – Хилл.CS1 maint: ref = harv (связь)
• Розен, К. Х. (2000). Элементарная теория чисел и ее приложения (4-е изд.). Ридинг, Массачусетс: Аддисон – Уэсли. ISBN  0-201-87073-8.CS1 maint: ref = harv (связь)
• Шредер, М. (2005). Теория чисел в науке и коммуникации (4-е изд.). Springer-Verlag. ISBN  0-387-15800-6.CS1 maint: ref = harv (связь)
• Старк, Х. (1978). Введение в теорию чисел. MIT Press. ISBN  0-262-69060-8.CS1 maint: ref = harv (связь)
• Стиллвелл, Дж. (1997). Числа и геометрия. Нью-Йорк: Springer-Verlag. ISBN  0-387-98289-2.CS1 maint: ref = harv (связь)
• Стиллвелл, Дж. (2003). Элементы теории чисел. Нью-Йорк: Springer-Verlag. ISBN  0-387-95587-9.CS1 maint: ref = harv (связь)
• Таттерсолл, Дж. Дж. (2005). Элементарная теория чисел в девяти главах. Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-85014-8.CS1 maint: ref = harv (связь)

внешняя ссылка

• Демонстрации алгоритма Евклида
• Вайсштейн, Эрик В. «Евклидов алгоритм». MathWorld.
• Алгоритм Евклида в завязать узел
• Алгоритм Евклида в PlanetMath.org.
• Евклидов алгоритм на MathPages
• Игра Евклида в завязать узел
• Музыка и алгоритм Евклида