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

Алгоритм вычисления наибольшего общего делителя

Метод Евклида для нахождения наибольшего общего делителя (НОД) двух начальных длин BA и DC, обе из которых определены как кратные общей «единичной» длины. Длина DC короче, она используется для «измерения» BA, но только один раз, потому что остаток EA меньше DC. Теперь EA измеряет (вдвое) более короткую длину DC, а остаток FC короче EA. Затем FC измеряет (втрое) длину EA. Поскольку остатка нет, процесс заканчивается тем, что FC становится НОД. Справа пример Никомаха с числами 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 году ( теорема Ламе ), ^{[1] [2]} и знаменует начало теории вычислительной сложности . Дополнительные методы повышения эффективности алгоритма были разработаны в 20 веке.

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

Первоначальный алгоритм был описан только для натуральных чисел и геометрических длин (действительных чисел), но в 19 веке алгоритм был обобщен на другие типы чисел, такие как гауссовы целые числа и многочлены одной переменной. Это привело к современным абстрактным алгебраическим понятиям, таким как евклидовы области .

Предыстория: наибольший общий делитель

Алгоритм Евклида вычисляет наибольший общий делитель (НОД) двух натуральных чисел a и b . Наибольший общий делитель g — это наибольшее натуральное число, которое делит как a , так и b без остатка. Синонимы НОД включают наибольший общий множитель (НОД), наибольший общий множитель (НОД), наибольший общий делитель (НОД) и наибольшую общую меру (НОМ). Наибольший общий делитель часто записывается как НОД( a ,  b ) или, проще говоря, как ( a ,  b ) , ^[3] , хотя последняя запись неоднозначна, также используется для таких понятий, как идеал в кольце целых чисел , который тесно связан с НОД.

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

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

Пусть g = gcd( a ,  b ) . Поскольку a и b оба кратны g , их можно записать как a  =  mg и b  =  ng , и нет большего числа G  >  g , для которого это верно. Натуральные числа m и n должны быть взаимно простыми, поскольку любой общий множитель можно вынести из m и n , чтобы сделать g больше. Таким образом, любое другое число c , которое делит и a , и b , должно также делить g . Наибольший общий делитель g a и b — это единственный (положительный) общий делитель a и b , который делится на любой другой общий делитель c . ^[6]

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

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

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

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

НОД( a ,  b ,  c ) = НОД( a , НОД( b ,  c )) = НОД(НОД( a ,  b ),  c ​​) = НОД(НОД( a ,  c ),  b ).

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

Описание

Процедура

Алгоритм Евклида можно рассматривать как построение последовательности неотрицательных целых чисел, которая начинается с двух заданных целых чисел и и в конечном итоге заканчивается целым числом ноль: с . Тогда целое число будет НОД, и мы можем заявить . Алгоритм указывает, как построить промежуточные остатки с помощью деления с остатком на предыдущей паре, найдя целое частное так, чтобы: ${\displaystyle r_{-2}=a}$ ${\displaystyle r_{-1}=b}$ ${\displaystyle \{r_{-2}=a,\ r_{-1}=b,\ r_{0},\ r_{1},\ \cdots ,\ r_{n-1},\ r_{n}=0\}}$ ${\displaystyle r_{k+1}<r_{k}}$ ${\displaystyle r_{n-1}}$ ${\displaystyle {\text{gcd}}(a,b)=r_{n-1}}$ ${\displaystyle r_{k}}$ ${\displaystyle (r_{k-2},\ r_{k-1})}$ ${\displaystyle q_{k}}$

${\displaystyle r_{k-2}=q_{k}\cdot r_{k-1}+r_{k}{\text{, with }}\ r_{k-1}>r_{k}\geq 0.}$

Поскольку последовательность неотрицательных целых чисел строго убывает, она в конечном итоге должна завершиться . Другими словами, поскольку для каждого , и каждое является целым числом, которое строго меньше предыдущего , в конечном итоге не может быть неотрицательного целого числа, меньшего нуля, и, следовательно, алгоритм должен завершиться. Фактически, алгоритм всегда завершится на n-м шаге с равным нулю. ^[15] ${\displaystyle \{r_{k}\}}$ ${\displaystyle r_{k}\geq 0}$ ${\displaystyle k}$ ${\displaystyle r_{k}}$ ${\displaystyle r_{k-1}}$ ${\displaystyle r_{n}}$

Для иллюстрации предположим, что запрашивается НОД 1071 и 462. Изначально последовательность имеет вид и для того, чтобы найти , нам нужно найти целые числа и такие, что: ${\displaystyle \{r_{-2}=1071,\ r_{-1}=462\}}$ ${\displaystyle r_{0}}$ ${\displaystyle q_{0}}$ ${\displaystyle r_{0}<r_{-1}}$

${\displaystyle 1071=q_{0}\cdot 462+r_{0}}$.

Это частное, так как . Это определяет и поэтому последовательность теперь . Следующий шаг — продолжить последовательность, чтобы найти , найдя целые числа и такие, что: ${\displaystyle q_{0}=2}$ ${\displaystyle 1071=2\cdot 462+147}$ ${\displaystyle r_{0}=147}$ ${\displaystyle \{1071,\ 462,\ r_{0}=147\}}$ ${\displaystyle r_{1}}$ ${\displaystyle q_{1}}$ ${\displaystyle r_{1}<r_{0}}$

${\displaystyle 462=q_{1}\cdot 147+r_{1}}$.

Это частное, так как . Это определяет и поэтому последовательность теперь . Следующий шаг — продолжить последовательность, чтобы найти , найдя целые числа и такие, что: ${\displaystyle q_{1}=3}$ ${\displaystyle 462=3\cdot 147+21}$ ${\displaystyle r_{1}=21}$ ${\displaystyle \{1071,\ 462,\ 147,\ r_{1}=21\}}$ ${\displaystyle r_{2}}$ ${\displaystyle q_{2}}$ ${\displaystyle r_{2}<r_{1}}$

${\displaystyle 147=q_{2}\cdot 21+r_{2}}$.

Это частное, так как . Это определяет и, таким образом, последовательность завершается, поскольку больше не может быть найдено неотрицательного целого числа, меньшего, чем . Предпоследний остаток , таким образом, является требуемым НОД: ${\displaystyle q_{2}=7}$ ${\displaystyle 147=7\cdot 21+0}$ ${\displaystyle r_{2}=0}$ ${\displaystyle \{1071,\ 462,\ 147,\ 21,\ r_{2}=0\}}$ ${\displaystyle 0}$ ${\displaystyle 21}$

${\displaystyle {\text{gcd}}(1071,\ 462)=21.}$

Мы можем немного обобщить, отбросив любое требование упорядочения для начальных двух значений и . Если , алгоритм может продолжаться и тривиально обнаружить, что в качестве последовательности остатков будет . Если , то мы также можем продолжать, поскольку , предполагая, что следующим остатком должен быть он сам, а последовательность равна . Обычно это было бы недействительно, поскольку нарушает требование , но теперь у нас есть по построению, поэтому требование автоматически удовлетворяется, и алгоритм Евклида может продолжаться как обычно. Следовательно, отбрасывание любого упорядочения между первыми двумя целыми числами не влияет на вывод о том, что последовательность должна в конечном итоге закончиться, поскольку следующий остаток всегда будет удовлетворять , и все продолжается, как указано выше. Единственные изменения, которые необходимо сделать, заключаются в том, что только для , и что подпоследовательность неотрицательных целых чисел для строго убывает, поэтому исключается из обоих утверждений. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a=b}$ ${\displaystyle {\text{gcd}}(a,\ a)=a}$ ${\displaystyle \{a,\ a,\ 0\}}$ ${\displaystyle a<b}$ ${\displaystyle a\equiv 0\cdot b+a}$ ${\displaystyle a}$ ${\displaystyle \{a,\ b,\ a,\ \cdots \}}$ ${\displaystyle r_{0}<r_{-1}}$ ${\displaystyle a<b}$ ${\displaystyle r_{0}<b}$ ${\displaystyle r_{k}<r_{k-1}}$ ${\displaystyle k\geq 0}$ ${\displaystyle \{r_{k-1}\}}$ ${\displaystyle k\geq 0}$ ${\displaystyle a=r_{-2}}$

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

Обоснованность алгоритма Евклида может быть доказана с помощью двухшагового рассуждения. ^[16] На первом шаге показано , что конечный ненулевой остаток r _{N −1 делит как} a, так и b . Поскольку это общий делитель, он должен быть меньше или равен наибольшему общему делителю g . На втором шаге показано, что любой общий делитель a и b , включая g , должен делить r _{N −1} ; следовательно, g должен быть меньше или равен r _{N −1} . Из этих двух противоположных неравенств следует, что r _{N −1}  =  g .

Чтобы продемонстрировать, что r _{N −1} делит как a, так и b (первый шаг), r _{N −1} делит свое предшественника r _{N −2}

г _{N −2} = q _N г _{N −1}

так как окончательный остаток r _N равен нулю. r _{N −1} также делит своего следующего предшественника r _{N −3}

г _{Н −3} = q _{Н −1} г _{Н −2} + г _{Н −1}

потому что он делит оба члена в правой части уравнения. Повторяя тот же аргумент, r _{N −1} делит все предыдущие остатки, включая a и b . Ни один из предыдущих остатков r _{N −2} , r _{N −3} и т. д. не делит a и b , так как они оставляют остаток. Поскольку r _{N −1} является общим делителем a и b , r _{N −1}  ≤  g .

На втором шаге любое натуральное число c, которое делит и a, и b (другими словами, любой общий делитель a и b ), делит остатки r _k . По определению a и b можно записать как кратные c  : a  =  mc и b  =  nc , где m и n — натуральные числа. Следовательно, c делит начальный остаток r ₀ , так как r ₀  =  a  −  q ₀ b  =  mc  −  q ₀ nc  = ( m  −  q ₀ n ) c . Аналогичное рассуждение показывает, что c также делит последующие остатки r ₁ , r ₂ и т. д. Следовательно, наибольший общий делитель g должен делить r _{N −1} , что подразумевает, что g  ≤  r _{N −1} . Поскольку первая часть рассуждения показала обратное ( r _{N −1}  ≤  g ), то отсюда следует, что g  =  r _{N −1} . Таким образом, g является наибольшим общим делителем всех последующих пар: ^{[17] [18]}

г знак равно НОД( а , б ) знак равно НОД( б , р ₀ ) знак равно НОД( р ₀ , р ₁ ) знак равно … знак равно НОД( р _{N -2} , р _{N -1} ) знак равно р _{N -1} .

Рабочий пример

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

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

1071 = 2 × 462 + 147.

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

462 = 3 × 147 + 21.

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

147 = 7 × 21 + 0.

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

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

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

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

На каждом шаге k алгоритм Евклида вычисляет частное q _k и остаток r _k из двух чисел r _{k −1} и r _{k −2.}

r _{k −2} = q _k r _{k −1} + r _k

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

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

r _k = r _{k −2} mod r _{k −1} .

Реализации

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

функция gcd(a, b) пока b ≠ 0 т := б б := а mod б а := т вернуть​

В начале k- й итерации переменная b содержит последний остаток r _{k −1} , тогда как переменная a содержит его предшественника, r _{k −2} . Шаг b  := a mod b эквивалентен приведенной выше формуле рекурсии r _k ≡ r _{k −2} mod r _{k −1} . Временная переменная t содержит значение r _{k −1} , пока вычисляется следующий остаток r _k . В конце итерации цикла переменная b содержит остаток r _k , тогда как переменная a содержит его предшественника, r _{k −1} .

(Если допускаются отрицательные входные данные или если функция mod может возвращать отрицательные значения, последнюю строку необходимо изменить на return abs (a).)

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

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

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

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

функция gcd(a, b) если b = 0 вернуть a иначе  вернуть gcd(b, a mod b)

(Как и выше, если допускаются отрицательные входные данные или если функция mod может возвращать отрицательные значения, инструкция « return a» должна быть изменена на « return max (a, −a)».)

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

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

В другой версии алгоритма Евклида частное на каждом шаге увеличивается на единицу, если полученный отрицательный остаток по величине меньше типичного положительного остатка. ^{[24] [25]} Ранее уравнение

r _{k −2} = q _k r _{k −1} + r _k

предполагается, что | r _{k −1} | >  r _k  > 0. Однако можно вычислить альтернативный отрицательный остаток e _{k :}

r _{k −2} = ( q _k + 1) r _{k −1} + e _k

если r _{k −1}  > 0 или

r _{k −2} = ( q _k − 1) r _{k −1} + e _k

если r _{k −1}  < 0 .

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

| r _k | ≤ | r _{k −1} | / 2

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

Леопольд Кронекер показал, что эта версия требует наименьшего количества шагов из всех версий алгоритма Евклида. ^{[24] [25]} В более общем смысле, было доказано, что для любых входных чисел a и b количество шагов минимально тогда и только тогда, когда q _k выбрано таким образом, что где — золотое сечение . ^[26] ${\displaystyle \left|{\frac {r_{k+1}}{r_{k}}}\right|<{\frac {1}{\varphi }}\sim 0.618,}$ ${\displaystyle \varphi }$

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

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

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

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

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

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

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

Алгоритм Евклида был первым алгоритмом целочисленных отношений , который является методом нахождения целочисленных отношений между соизмеримыми действительными числами. Было разработано несколько новых алгоритмов целочисленных отношений , таких как алгоритм Хеламана Фергюсона и Р. В. Форкада (1979) ^[48] и алгоритм LLL . ^{[49] [50]}

В 1969 году Коул и Дэви разработали игру для двух игроков, основанную на алгоритме Евклида, названную «Игра Евклида» ^[51] , которая имеет оптимальную стратегию. ^[52] Игроки начинают с двух кучек камней a и b . Игроки по очереди вынимают m кратных меньшей кучки из большей. Таким образом, если две кучки состоят из камней x и y , где x больше y , следующий игрок может уменьшить большую кучку с x камней до x − my камней, при условии, что последнее является неотрицательным целым числом. Победителем становится первый игрок, который уменьшит одну кучку до нуля камней. ^{[53] [54]}

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

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

Тождество Безу утверждает, что наибольший общий делитель g двух целых чисел a и b может быть представлен в виде линейной суммы исходных двух чисел a и b . ^[55] Другими словами, всегда можно найти целые числа s и t, такие что g  =  sa  +  tb . ^{[56] [57]}

Целые числа s и t можно вычислить из частных q ₀ , q ₁ и т. д., изменив порядок уравнений в алгоритме Евклида. ^[58] Начиная с предпоследнего уравнения, g можно выразить через частное q _{N −1} и два предыдущих остатка, r _{N −2} и r _{N −3} :

г = г _{Н −1} = г _{Н −3} − q _{Н −1} г _{Н −2}  .

Эти два остатка можно также выразить через их частные и предыдущие остатки:

r _{N −2} = r _{N −4} − q _{N −2} r _{N −3} и

г _{Н −3} = г _{Н −5} − q _{Н −3} г _{Н −4}  .

Подстановка этих формул для r _{N −2} и r _{N −3} в первое уравнение дает g как линейную сумму остатков r _{N −4} и r _{N −5} . Процесс подстановки остатков формулами, включающими их предшественников, может быть продолжен до тех пор, пока не будут достигнуты исходные числа a и b :

г ₂ = г ₀ − q ₂ г ₁

г ₁ = б − q ₁ г ₀

r ₀ = a − q ₀ b .

После подстановки всех остатков r ₀ , r _{1 и т. д. окончательное уравнение выражает} g как линейную сумму a и b , так что g  =  sa  +  tb .

Алгоритм Евклида и, следовательно, тождество Безу можно обобщить на контекст евклидовых областей .

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

Тождество Безу дает еще одно определение наибольшего общего делителя g двух чисел a и b . ^[12] Рассмотрим множество всех чисел ua  +  vb , где u и v — любые два целых числа. Поскольку a и b оба делятся на g , каждое число в множестве делится на g . Другими словами, каждое число множества является целым кратным g . Это верно для каждого общего делителя a и b . Однако, в отличие от других общих делителей, наибольший общий делитель является членом множества; по тождеству Безу выбор u  =  s и v  =  t дает g . Меньший общий делитель не может быть членом множества, поскольку каждый член множества должен делиться на g . И наоборот, любое кратное m числа g можно получить, выбрав u  =  ms и v  =  mt , где s и t — целые числа тождества Безу. Это можно увидеть, умножив тождество Безу на m ,

мг = мса + мтб .

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

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

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

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

с _к = с _{к −2} − q _к с _{к −1}

т _к = т _{к −2} − q _к т _{к −1}

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

с ₋₂ = 1, т ₋₂ = 0

с ₋₁ = 0, t ₋₁ = 1.

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

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

р _j = с _j а + т _j б

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

r _k = r _{k −2} − q _k r _{k −1} .

Поскольку предполагается, что рекурсивная формула верна для r _{k −2} и r _{k −1} , их можно выразить через соответствующие переменные s и t

r _k = ( _sk −2 _a + t k _{−2 b} ) − q _k ( sk _{−1 a} + t _{k −1} b ) .

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

r _k = sk _a + t _k b = ₍ sk ₋₂ − q _k s _{k −1} ) a + ( t _{k −2} − q _k t _{k −1} ) b .

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

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

${\displaystyle {\begin{aligned}a&=q_{0}b+r_{0}\\b&=q_{1}r_{0}+r_{1}\\&\,\,\,\vdots \\r_{N-2}&=q_{N}r_{N-1}+0\end{aligned}}}$

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

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

Пусть M представляет собой произведение всех матриц-факторов

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

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

${\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}g\\0\end{pmatrix}}\,.}$

Чтобы выразить g как линейную сумму a и b , обе стороны этого уравнения можно умножить на обратную матрицу M. ^{[61] [62]} Определитель M равен (−1) ^{N +1 ,} поскольку он равен произведению определителей матриц частных, каждая из которых отрицательна. Поскольку определитель M никогда не равен нулю, вектор конечных остатков можно решить с помощью обратной матрицы M

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

Так как верхнее уравнение дает

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

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

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

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

1 = вс + тв

по тождеству Безу. Умножение обеих частей на v дает соотношение:

v = внедорожник + твв = сЛ + твв

Так как w делит оба члена в правой части, оно также должно делить левую часть, v . Этот результат известен как лемма Евклида . ^[64] В частности, если простое число делит L , то оно должно делить по крайней мере один множитель L. И наоборот, если число w _{взаимно} просто с каждым из ряда чисел a ₁ , a ₂ , ..., an , то w также взаимно просто с их произведением, a ₁  ×  a ₂  × ... ×  a _n . ^[64]

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

L = p ₁ p ₂ … p _m = q ₁ q ₂ … q _n  .

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

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

График линейного диофантова уравнения , 9 x  + 12 y  = 483. Решения показаны синими кружками.

Диофантовы уравнения — это уравнения, решения которых ограничены целыми числами; они названы в честь александрийского математика третьего века Диофанта . ^[66] Типичное линейное диофантово уравнение ищет целые числа x и y , такие, что ^[67]

ах + бай = с

где a , b и c — заданные целые числа. Это можно записать как уравнение для x в модульной арифметике :

ах ≡ с mod b .

Пусть g будет наибольшим общим делителем a и b . Оба члена в ax  +  by делятся на g ; следовательно, c также должен делиться на g , иначе уравнение не имеет решений. Разделив обе части на c / g , уравнение можно свести к тождеству Безу

са + тб = г

где s и t можно найти с помощью расширенного алгоритма Евклида . ^[68] Это дает одно решение диофантова уравнения, x ₁  =  s ( c / g ) и y ₁  =  t ( c / g ).

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

ах ₁ + на ₁ = с = ах ₂ + на ₂

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

а ( Икс ₁ - Икс ₂ ) знак равно б ( y ₂ - y ₁ ).

Поэтому наименьшая разница между двумя решениями x равна b / g , тогда как наименьшая разница между двумя решениями y равна a / g . Таким образом, решения могут быть выражены как

х = х ₁ − бу / г

у = у ₁ + ау / г .

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

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

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

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

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

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

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

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

${\displaystyle {\begin{aligned}x_{1}&\equiv x{\pmod {m_{1}}}\\x_{2}&\equiv x{\pmod {m_{2}}}\\&\,\,\,\vdots \\x_{N}&\equiv x{\pmod {m_{N}}}\,.\end{aligned}}}$

Цель состоит в том, чтобы определить x из его N остатков x _i . Решение состоит в том, чтобы объединить множественные уравнения в одно линейное диофантово уравнение с гораздо большим модулем M , который является произведением всех отдельных модулей m _i , и определить M _i как

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

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

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

С помощью этих чисел h _i любое целое число x может быть восстановлено из его остатков x _i с помощью уравнения

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

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

Дерево Штерн–Броко

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

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

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

${\displaystyle {\begin{aligned}&\gcd(3,4)&\leftarrow \\={}&\gcd(3,1)&\rightarrow \\={}&\gcd(2,1)&\rightarrow \\={}&\gcd(1,1).\end{aligned}}}$

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

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

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

${\displaystyle {\begin{aligned}{\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}\,.\end{aligned}}}$

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

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

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

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

Конечное отношение остатков r _k / r _{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}]\,.}$

В приведенном выше примере был вычислен gcd(1071, 462), а частные q _k были равны 2, 3 и 7 соответственно. Таким образом, дробь 1071/462 можно записать так:

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

что может быть подтверждено расчетом.

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

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

Эффективность алгоритма

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

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

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

Количество ступеней

Число шагов для вычисления НОД двух натуральных чисел, a и b , можно обозначить как T ( a ,  b ). ^[95] Если g — НОД a и b , то a  =  mg и b  =  ng для двух взаимно простых чисел m и n . Тогда

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

как можно увидеть, разделив все шаги в алгоритме Евклида на g . ^[96] По тому же аргументу, количество шагов остается тем же самым, если a и b умножаются на общий множитель w : T ( a , b ) = T ( wa , wb ). Таким образом, количество шагов T может существенно различаться между соседними парами чисел, такими как T( a , b ) и T( a ,  b  + 1), в зависимости от размера двух НОД.

Рекурсивная природа алгоритма Евклида дает еще одно уравнение

Т ( а , б ) = 1 + Т ( б , г ₀ ) = 2 + Т ( г ₀ , г ₁ ) = … = N + Т ( г _{N −2} , г _{N −1} ) = N + 1

где T ( x , 0) = 0 по предположению. ^[95]

В худшем случае

Если алгоритм Евклида требует N шагов для пары натуральных чисел a  >  b  > 0, то наименьшие значения a и b, для которых это верно, — это числа Фибоначчи F _{N +2} и F _{N +1} соответственно. ^[97] Точнее, если алгоритм Евклида требует N шагов для пары a  >  b , то a  ≥  F _{N +2} и b  ≥  F _{N +1} . Это можно показать по индукции . ^[98] Если N  = 1, то b делит a без остатка; наименьшие натуральные числа, для которых это верно, — это b  = 1 и a  = 2, то есть F ₂ и F ₃ соответственно. Теперь предположим, что результат справедлив для всех значений N вплоть до M  − 1. Первый шаг алгоритма с M шагами — это a  =  q ₀ b  +  r ₀ , а алгоритм Евклида требует M  − 1 шагов для пары b  >  r ₀ . По предположению индукции имеем b  ≥  F _{M +1} и r ₀  ≥  F _M . Следовательно, a  =  q ₀ b  +  r ₀  ≥  b  +  r ₀  ≥  F _{M +1}  +  F _M  =  F _{M +2} , что и является искомым неравенством. Это доказательство, опубликованное Габриэлем Ламе в 1844 году, представляет собой начало теории вычислительной сложности ^[99] , а также первое практическое применение чисел Фибоначчи. ^[97]

Этого результата достаточно, чтобы показать, что число шагов в алгоритме Евклида никогда не может превышать число его цифр (основание 10) более чем в пять раз. ^[100] Ибо, если алгоритм требует N шагов, то b больше или равно F _{N +1,} что в свою очередь больше или равно φ ^{N −1} , где φ — золотое сечение . Поскольку b  ≥  φ ^{N −1} , то N  − 1 ≤ log _φ b . Поскольку log ₁₀ φ  > 1/5, ( N  − 1)/5 < log ₁₀ φ  log _φ b  = log ₁₀ b . Таким образом, N  ≤ 5 log ₁₀ b . Таким образом, алгоритм Евклида всегда требует менее O ( h ) делений, где h — количество цифр в меньшем числе b .

Средний

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

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

Однако, поскольку T ( a ,  b ) резко колеблется в зависимости от НОД двух чисел, усредненная функция T ( a ) также является «шумной». ^[101]

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

${\displaystyle \tau (a)={\frac {1}{\varphi (a)}}\sum _{\begin{smallmatrix}0\leq b<a\\\gcd(a,b)=1\end{smallmatrix}}T(a,b).}$

Существуют φ ( a ) взаимно простые целые числа, меньшие a , где φ — функция Эйлера . Это среднее тау растет плавно с a ^{[102] [103]}

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

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

${\displaystyle C=-{\frac {1}{2}}+{\frac {6\ln 2}{\pi ^{2}}}\left(4\gamma -{\frac {24}{\pi ^{2}}}\zeta '(2)+3\ln 2-2\right)\approx 1.467}$

где γ — константа Эйлера–Маскерони , а ζ' — производная дзета -функции Римана . ^{[105] [106]} Главный коэффициент (12/π ² ) ln 2 был определен двумя независимыми методами. ^{[107] [108]}

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

${\displaystyle T(a)={\frac {1}{a}}\sum _{d\mid a}\varphi (d)\tau (d)}$

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

${\displaystyle T(a)\approx C+{\frac {12}{\pi ^{2}}}\ln 2\,{\biggl (}{\ln a}-\sum _{d\mid a}{\frac {\Lambda (d)}{d}}{\biggr )}}$

где Λ( d ) — функция Мангольдта . ^[111]

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

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

Подстановка приближенной формулы для T ( a ) в это уравнение дает оценку для Y ( n ) ^[112]

${\displaystyle Y(n)\approx {\frac {12}{\pi ^{2}}}\ln 2\ln n+0.06.}$

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

На каждом шаге k алгоритма Евклида частное q _k и остаток r _k вычисляются для заданной пары целых чисел r _{k −2} и r _{k −1.}

r _{k −2} = q _k r _{k −1} + r _k .

Вычислительные затраты на шаг связаны в основном с нахождением q _k , поскольку остаток r _k можно быстро вычислить из r _{k −2} , r _{k −1} и q _k

r _k = r _{k −2} − q _k r _{k −1} .

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

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

Объединение предполагаемого числа шагов с предполагаемыми вычислительными затратами на шаг показывает, что алгоритм Евклида растет квадратично ( h ² ) со средним числом цифр h в начальных двух числах a и b . Пусть h ₀ , h ₁ , ..., h _{N −1} представляют число цифр в последовательных остатках r ₀ , r ₁ , ..., r _{N −1} . Поскольку число шагов N растет линейно с h , время выполнения ограничено

${\displaystyle O{\Big (}\sum _{i<N}h_{i}(h_{i}-h_{i+1}+2){\Big )}\subseteq O{\Big (}h\sum _{i<N}(h_{i}-h_{i+1}+2){\Big )}\subseteq O(h(h_{0}+2N))\subseteq O(h^{2}).}$

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

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

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

Двоичный алгоритм НОД является эффективной альтернативой, которая заменяет деление более быстрыми операциями, используя двоичное представление, используемое компьютерами. ^{[118] [119]} Однако эта альтернатива также масштабируется как O ( h ²) . Он, как правило, быстрее, чем алгоритм Евклида на реальных компьютерах, хотя он масштабируется таким же образом. ^[93] Дополнительная эффективность может быть получена путем изучения только первых цифр двух чисел a и b . ^{[120] [121]} Двоичный алгоритм может быть расширен на другие основания ( k -арные алгоритмы), ^[122] с увеличением скорости до пяти раз. ^[123] Алгоритм НОД Лемера использует тот же общий принцип, что и двоичный алгоритм, для ускорения вычислений НОД в произвольных основаниях.

Рекурсивный подход для очень больших целых чисел (более 25 000 цифр) приводит к квазилинейным целочисленным алгоритмам GCD, ^[124], таким как алгоритмы Шёнхаге, ^{[125] [126]} и Стеле и Циммермана. ^[127] Эти алгоритмы используют матричную форму 2×2 евклидова алгоритма, приведенного выше. Эти квазилинейные методы обычно масштабируются как O ( h log h ² log log h ). ^{[93] [94]}

Обобщения

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

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

Алгоритм Евклида может быть применен к действительным числам , как описано Евклидом в Книге 10 его Элементов . Цель алгоритма — определить действительное число g таким образом, что два заданных действительных числа, a и b , являются его целыми кратными: a = mg и b = ng , где m и n — целые числа . ^[28] Эта идентификация эквивалентна нахождению целочисленного отношения между действительными числами a и b ; то есть она определяет целые числа s и t , такие что sa + tb = 0. Если такое уравнение возможно, a и b называются соизмеримыми длинами, в противном случае они являются несоизмеримыми длинами . ^{[131] [132]}

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

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

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

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

${\displaystyle {\begin{aligned}m_{k}&=q_{k}m_{k-1}+m_{k-2}\\n_{k}&=q_{k}n_{k-1}+n_{k-2},\end{aligned}}}$

где m ₋₁ = n ₋₂ = 1 и m ₋₂ = n ₋₁ = 0 — начальные значения рекурсии. Сходящаяся дробь m _k / n _k — наилучшее рациональное числовое приближение к a / b со знаменателем n _k : ^[136]

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

Полиномы

Полиномы от одной переменной x можно складывать, умножать и разлагать на неприводимые полиномы , которые являются аналогами простых чисел для целых чисел. Наибольший общий делитель полинома g ( x ) двух полиномов a ( x ) и b ( x ) определяется как произведение их общих неприводимых полиномов, которые можно определить с помощью алгоритма Евклида. ^[128] Основная процедура аналогична процедуре для целых чисел. На каждом шаге k определяются частный полином q _k ( x ) и остаток полинома r _k ( x ) для удовлетворения рекурсивного уравнения

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

где r ₋₂ ( x ) = a ( x ) и r ₋₁ ( x ) = b ( x ) . Каждый частный многочлен выбирается таким образом, что каждый остаток либо равен нулю, либо имеет степень, меньшую степени своего предшественника: deg[ r _k ( x )] < deg[ r _{k −1} ( x )] . Поскольку степень является неотрицательным целым числом и поскольку она уменьшается с каждым шагом, алгоритм Евклида завершается за конечное число шагов. Последний ненулевой остаток является наибольшим общим делителем исходных двух многочленов, a ( x ) и b ( x ) . ^[137]

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

${\displaystyle {\begin{aligned}a(x)&=x^{4}-4x^{3}+4x^{2}-3x+14=(x^{2}-5x+7)(x^{2}+x+2)\qquad {\text{and}}\\b(x)&=x^{4}+8x^{3}+12x^{2}+17x+6=(x^{2}+7x+3)(x^{2}+x+2).\end{aligned}}}$

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

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

Полиномиальный алгоритм Евклида имеет и другие приложения, такие как цепи Штурма , метод подсчета нулей полинома , которые лежат внутри заданного действительного интервала . ^[139] Это, в свою очередь, имеет приложения в нескольких областях, таких как критерий устойчивости Рауса-Гурвица в теории управления . ^[140]

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

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

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

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

Алгоритм Евклида, разработанный для двух гауссовых целых чисел α и β, почти такой же, как и для обычных целых чисел, ^[142], но отличается в двух отношениях. Как и прежде, мы устанавливаем r ₋₂ = α и r ₋₁ = β , и задача на каждом шаге k состоит в том, чтобы определить частное q _k и остаток r _k таким образом, чтобы

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

где каждый остаток строго меньше своего предшественника: | r _k | < | r _{k −1} | . Первое отличие состоит в том, что частные и остатки сами являются целыми числами Гаусса, и, таким образом, являются комплексными числами . Частные q _k обычно находятся путем округления действительной и комплексной частей точного отношения (например, комплексного числа α / β ) до ближайших целых чисел. ^[142] Второе отличие заключается в необходимости определения того, как один комплексный остаток может быть «меньше» другого. Для этого определяется функция нормы f ( u + vi ) = u ² + v ^{2 , которая преобразует каждое целое число Гаусса} u + vi в обычное целое число. После каждого шага k алгоритма Евклида норма остатка f ( r _k ) меньше нормы предыдущего остатка, f ( r _{k −1} ) . Поскольку норма является неотрицательным целым числом и уменьшается с каждым шагом, алгоритм Евклида для гауссовых целых чисел заканчивается за конечное число шагов. ^[143] Окончательный ненулевой остаток равен gcd( α , β ) , гауссовскому целому числу наибольшей нормы, которое делит как α , так и β ; он уникален с точностью до умножения на единицу, ±1 или ± i . ^[144]

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

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

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

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

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

Уникальная факторизация евклидовых областей полезна во многих приложениях. Например, уникальная факторизация гауссовых целых чисел удобна при выводе формул для всех пифагорейских троек и при доказательстве теоремы Ферма о суммах двух квадратов . ^[141] Уникальная факторизация также была ключевым элементом в попытке доказательства Великой теоремы Ферма, опубликованной в 1847 году Габриэлем Ламе, тем же математиком, который проанализировал эффективность алгоритма Евклида, основанного на предложении Жозефа Лиувилля . ^[154] Подход Ламе требовал уникальной факторизации чисел вида x + ωy , где x и y — целые числа, а ω = e ^{2 iπ / n} — корень n- й степени из 1, то есть ω ⁿ = 1 . Хотя этот подход оказывается успешным для некоторых значений n (например, n = 3 , целые числа Эйзенштейна ), в общем случае такие числа не факторизуются однозначно. Эта неудача однозначной факторизации в некоторых циклотомических полях привела Эрнста Куммера к концепции идеальных чисел , а позднее Ричарда Дедекинда к идеалам . ^[155]

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

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

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

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

Однако если D действительно кратно четырем плюс один, то

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

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

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

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

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

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

где ψ ₀ представляет собой частное, а ρ ₀ — остаток. Здесь частное и остаток выбираются так, что (если они не равны нулю) остаток имеет N ( ρ ₀ ) < N ( β ) для «евклидовой функции» N, определяемой аналогично евклидовым функциям евклидовых областей в некоммутативном случае. ^[159] Это уравнение показывает, что любой общий правый делитель α и β также является общим делителем остатка ρ ₀ . Аналогичное уравнение для левых делителей будет иметь вид

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

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

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

${\displaystyle \Gamma _{\text{right}}=\sigma \alpha +\tau \beta .}$

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

${\displaystyle \Gamma _{\text{left}}=\alpha \sigma +\beta \tau .}$

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

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

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

Примечания

1. Некоторые широко используемые учебники, такие как «Темы алгебры » И. Н. Герштейна и «Алгебра » Сержа Ланга , используют термин «алгоритм Евклида» для обозначения евклидова деления.
2. Фраза «обычное целое число» обычно используется для различения обычных целых чисел от гауссовых целых чисел и, в более общем смысле, от алгебраических целых чисел .

Ссылки

1. Ламе, Габриэль (1844). «Обратите внимание на предел количества подразделений в исследованиях плюс великий разделитель Entre Deux Nombres entiers». Comptes Rendus des Séances de l'Académie des Sciences (на французском языке). 19 : 867–870.
2. Шаллит, Джеффри (1 ноября 1994 г.). «Истоки анализа алгоритма Евклида». Historia Mathematica . 21 (4): 401–419. doi : 10.1006/hmat.1994.1031 . ISSN  0315-0860.
3. Старк 1978, стр. 16
4. Старк 1978, стр. 21
5. Левек 1996, стр. 32
6. Левек 1996, стр. 31
7. Гроссман, Дж. В. (1990). Дискретная математика . Нью-Йорк: Macmillan. С. 213. ISBN 0-02-348331-8.
8. Schroeder 2005, стр. 21–22
9. Шредер 2005, стр. 19
10. Огилви, CS ; Андерсон, JT (1966). Экскурсии в теорию чисел . Нью-Йорк: Oxford University Press . С. 27–29.
11. Schroeder 2005, стр. 216–219
12. LeVeque 1996, стр. 33
13. Старк 1978, стр. 25
14. Оре 1948, стр. 47–48.
15. Старк 1978, стр. 18
16. Старк 1978, стр. 16–20.
17. Кнут 1997, стр. 320
18. Ловас, Л .; Пеликан, Дж.; Вестергомби, К. (2003). Дискретная математика: элементарная и не только . Нью-Йорк: Springer-Verlag. стр. 100–101. ISBN 0-387-95584-4.
19. Кимберлинг, К. (1983). «Визуальный евклидов алгоритм». Учитель математики . 76 : 108–109.
20. Даммит, Дэвид С.; Фут, Ричард М. (2004). Абстрактная алгебра . John Wiley & Sons, Inc. стр. 270–271. ISBN 978-0-471-43334-7.
21. Кнут 1997, стр. 319–320
22. Кнут 1997, стр. 318–319
23. Стиллвелл 1997, стр. 14
24. Ore 1948, стр. 43
25. Stewart, BM (1964). Теория чисел (2-е изд.). Нью-Йорк: Macmillan. С. 43–44. LCCN  64010964.
26. Лазард, Д. (1977). «Лучший алгоритм Евклида для K [ X ] и Z ». Comptes Rendus de l'Académie des Sciences (на французском языке). 284 : 1–4.
27. Knuth 1997, стр. 318
28. Weil, A. (1983). Теория чисел . Бостон: Birkhäuser. стр. 4–6. ISBN 0-8176-3141-0.
29. Джонс, А. (1994). «Греческая математика до 300 г. н. э.». Компаньонская энциклопедия истории и философии математических наук . Нью-Йорк: Routledge. С. 46–48. ISBN 0-415-09238-8.
30. ван дер Варден, BL (1954). Пробуждение науки . перевод Арнольда Дрездена. Гронинген: P. Noordhoff Ltd., стр. 114–115.
31. фон Фриц, К. (1945). «Открытие несоизмеримости Гиппасом из Метапонта». Annals of Mathematics . 46 (2): 242–264. doi :10.2307/1969021. JSTOR  1969021.
32. Хит, Т. Л. (1949). Математика у Аристотеля . Oxford Press. С. 80–83.
33. Фаулер, Д. Х. (1987). Математика Платоновской Академии: Новая реконструкция . Оксфорд: Oxford University Press. С. 31–66. ISBN 0-19-853912-6.
34. Беккер, О. (1933). «Евдокс-Студиен I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid». Quellen und Studien zur Geschichte der Mathematik B. 2 : 311–333.
35. Stillwell 1997, стр. 31
36. Tattersall 2005, стр. 70
37. Розен 2000, стр. 86–87.
38. Оре 1948, стр. 247–248.
39. Таттерсолл 2005, стр. 72, 184–185
40. Saunderson, Nicholas (1740). Элементы алгебры в десяти книгах. University of Cambridge Press . Получено 1 ноября 2016 г.
41. Таттерсолл 2005, стр. 72–76
42. Гаусс, CF (1832). «Theoria residuorum biquadraticorum». Комм. Соц. Рег. наук. Гетт. Рек . 4 .Перепечатано в Gauss, CF (2011). «Theoria residuorum biquadraticorum commentatio prima». Верке . Том. 2. Кембриджский университет. Нажимать. стр. 65–92. дои : 10.1017/CBO9781139058230.004. ISBN 9781139058230.и Гаусс, К.Ф. (2011). «Theoria residuorum biquadraticorum commentatio secunda». Верке . Том. 2. Кембриджский университет. Нажимать. стр. 93–148. дои : 10.1017/CBO9781139058230.005. ISBN 9781139058230.
43. Стиллвелл 1997, стр. 31–32
44. Лежен Дирихле 1894, стр. 29–31
45. Рихард Дедекинд в Lejeune Dirichlet 1894, Приложение XI
46. Стиллвелл 2003, стр. 41–42
47. Штурм, К. (1829). «Мемуар о разрешении числовых уравнений». Бык. Des Sciences de Férussac (на французском языке). 11 : 419–422.
48. Фергюсон, ХРП ; Форкад, РВ (1979). «Обобщение алгоритма Евклида для действительных чисел на все размерности выше двух». Бюллетень Американского математического общества . Новая серия. 1 (6): 912–914. doi : 10.1090/S0273-0979-1979-14691-3 . MR  0546316.
49. Петерсон, И. (12 августа 2002 г.). «Усложняем алгоритм Евклида». ScienceNews .
50. Cipra, Barry Arthur (16 мая 2000 г.). «Лучшие из 20-го века: редакторы назвали 10 лучших алгоритмов» (PDF) . SIAM News . 33 (4). Society for Industrial and Applied Mathematics . Архивировано из оригинала (PDF) 22 сентября 2016 г. . Получено 19 июля 2016 г. .
51. Коул, А. Дж.; Дэви, А. Дж. Т. (1969). «Игра, основанная на алгоритме Евклида, и выигрышная стратегия для нее». Math. Gaz . 53 (386): 354–357. doi :10.2307/3612461. JSTOR  3612461. S2CID  125164797.
52. Шпицнагель, Э. Л. (1973). «Свойства игры, основанной на алгоритме Евклида». Math. Mag . 46 (2): 87–92. doi :10.2307/2689037. JSTOR  2689037.
53. Розен 2000, стр. 95
54. Робертс, Дж. (1977). Элементарная теория чисел: проблемно-ориентированный подход. Кембридж, Массачусетс: MIT Press . С. 1–8. ISBN 0-262-68028-9.
55. Джонс, GA; Джонс, JM (1998). «Тождество Безу». Элементарная теория чисел . Нью-Йорк: Springer-Verlag. С. 7–11.
56. Розен 2000, стр. 81
57. Кон 1962, стр. 104
58. Розен 2000, стр. 91
59. Шредер 2005, стр. 23
60. Розен 2000, стр. 90–93
61. Koshy, T. (2002). Элементарная теория чисел с приложениями . Burlington, MA: Harcourt/Academic Press. стр. 167–169. ISBN 0-12-421171-2.
62. Бах, Э .; Шаллит, Дж. (1996). Алгоритмическая теория чисел . Кембридж, Массачусетс: MIT Press. С. 70–73. ISBN 0-262-02405-5.
63. Старк 1978, стр. 26–36.
64. Ore 1948, стр. 44
65. Старк 1978, стр. 281–292.
66. Розен 2000, стр. 119–125.
67. Шредер 2005, стр. 106–107
68. Шредер 2005, стр. 108–109
69. Розен 2000, стр. 120–121.
70. Старк 1978, стр. 47
71. Шредер 2005, стр. 107–109
72. Стиллвелл 1997, стр. 186–187
73. Шредер 2005, стр. 134
74. Moon, TK (2005). Кодирование с исправлением ошибок: математические методы и алгоритмы . John Wiley and Sons. стр. 266. ISBN 0-471-64800-0.
75. Розен 2000, стр. 143–170
76. Шредер 2005, стр. 194–195
77. Грэм, Р .; Кнут, Д.Э .; Паташник, О. (1989). Конкретная математика . Эддисон-Уэсли. стр. 123.
78. Виноградов, ИМ (1954). Элементы теории чисел . Нью-Йорк: Довер. С. 3–13.
79. Крэндалл и Померанс 2001, стр. 225–349.
80. Кнут 1997, стр. 369–371
81. Шор, П. В. (1997). «Алгоритмы полиномиального времени для разложения на простые множители и дискретных логарифмов на квантовом компьютере». Журнал SIAM по научным и статистическим вычислениям . 26 (5): 1484–1509. arXiv : quant-ph/9508027 . Bibcode : 1995quant.ph..8027S. doi : 10.1137/s0097539795293172. S2CID  2337707.
82. Диксон, Дж. Д. (1981). «Асимптотически быстрая факторизация целых чисел». Math. Comput . 36 (153): 255–260. doi : 10.2307/2007743 . JSTOR  2007743.
83. Lenstra, HW Jr. (1987). «Разложение целых чисел на эллиптические кривые». Annals of Mathematics . 126 (3): 649–673. doi :10.2307/1971363. hdl : 1887/2140 . JSTOR  1971363.
84. Кнут 1997, стр. 380–384.
85. Кнут 1997, стр. 339–364.
86. Рейно, А.-А.-Л. (1811). Traité d'arithmétique à l'usage des éleves, который предназначен для Политехнической школы (6-е изд.). Париж: Курьер. Примечание 60, с. 34.Как цитирует Шаллит (1994).
87. Финк, П.-Ж.-Э. (1841). Traité élémentaire d’arithmétique à l’usage des Candidates aux écoles spéciales (на французском языке). Дериво.
88. Шаллит 1994.
89. Ламе, Г. (1844). «Обратите внимание на предел количества подразделений в исследованиях плюс великий разделитель Entre Deux Nombres entiers». Comptes Rendus de l'Académie des Sciences (на французском языке). 19 : 867–870.
90. Гроссман, Х. (1924). «О числе делений при нахождении НОД». The American Mathematical Monthly . 31 (9): 443. doi :10.2307/2298146. JSTOR  2298146.
91. Хонсбергер, Р. (1976). Математические жемчужины II . Математическая ассоциация Америки . стр. 54–57. ISBN 0-88385-302-7.
92. Knuth 1997, стр. 257–261
93. Crandall & Pomerance 2001, стр. 77–79, 81–85, 425–431
94. Мёллер, Н. (2008). «Об алгоритме Шёнхаге и вычислении субквадратичных целых НОД» (PDF) . Математика вычислений . 77 (261): 589–607. Бибкод : 2008MaCom..77..589M. дои : 10.1090/S0025-5718-07-02017-0 .
95. Кнут 1997, стр. 344
96. Оре 1948, стр. 45
97. Knuth 1997, стр. 343
98. Моллин 2008, стр. 21
99. Левек 1996, стр. 35
100. Моллин 2008, стр. 21–22
101. Кнут 1997, стр. 353
102. Кнут 1997, стр. 357
103. Тонков, Т. (1974). «О средней длине конечных цепных дробей». Acta Arithmetica . 26 : 47–57. doi : 10.4064/aa-26-1-47-57 .
104. Кнут, Дональд Э. (1976). «Оценка константы Портера». Компьютеры и математика с приложениями . 2 (2): 137–139. doi : 10.1016/0898-1221(76)90025-0 .
105. Портер, Дж. В. (1975). «О теореме Хейльбронна». Mathematika . 22 : 20–28. doi :10.1112/S0025579300004459.
106. Кнут, Д. Э. (1976). «Оценка константы Портера». Компьютеры и математика с приложениями . 2 (2): 137–139. doi : 10.1016/0898-1221(76)90025-0 .
107. Диксон, Дж. Д. (1970). «Число шагов в алгоритме Евклида». J. Number Theory . 2 (4): 414–422. Bibcode :1970JNT.....2..414D. doi : 10.1016/0022-314X(70)90044-2 .
108. Heilbronn, HA (1969). «О средней длине класса конечных непрерывных дробей». В Paul Turán (ред.). Теория чисел и анализ . Нью-Йорк: Plenum. стр. 87–96. LCCN  76016027.
109. Кнут 1997, стр. 354
110. Norton, GH (1990). «Об асимптотическом анализе алгоритма Евклида». Журнал символических вычислений . 10 : 53–58. doi : 10.1016/S0747-7171(08)80036-3 .
111. Кнут 1997, стр. 355
112. Кнут 1997, стр. 356
113. Кнут 1997, стр. 352
114. Вагон, С. (1999). Mathematica в действии . Нью-Йорк: Springer-Verlag. С. 335–336. ISBN 0-387-98252-3.
115. Коэн 1993, стр. 14
116. Коэн 1993, стр. 14–15, 17–18.
117. Sorenson, Jonathan P. (2004). "Анализ обобщенного бинарного алгоритма GCD". Высокие простые числа и проступки: лекции в честь 60-летия Хью Коуи Уильямса. Fields Institute Communications. Том 41. Providence, RI: American Mathematical Society. С. 327–340. ISBN 9780821887592. MR  2076257. Алгоритмы, которые сегодня чаще всего используются на практике [для вычисления наибольшего общего делителя], — это, вероятно, двоичный алгоритм и алгоритм Евклида для меньших чисел, а также либо алгоритм Лемера, либо версия Лебеля алгоритма k -арного НОД для больших чисел.
118. Кнут 1997, стр. 321–323
119. Stein, J. (1967). «Вычислительные проблемы, связанные с алгеброй Рака». Журнал вычислительной физики . 1 (3): 397–405. Bibcode :1967JCoPh...1..397S. doi :10.1016/0021-9991(67)90047-2.
120. Кнут 1997, стр. 328
121. Лемер, Д. Х. (1938). «Алгоритм Евклида для больших чисел». The American Mathematical Monthly . 45 (4): 227–233. doi :10.2307/2302607. JSTOR  2302607.
122. Соренсон, Дж. (1994). «Два быстрых алгоритма НОД». J. Algorithms . 16 : 110–144. doi :10.1006/jagm.1994.1006.
123. Вебер, К. (1995). «Ускоренный алгоритм НОД». ACM Trans. Math. Softw . 21 : 111–122. doi : 10.1145/200979.201042 . S2CID  14934919.
124. Ахо, А.; Хопкрофт , Дж .; Ульман, Дж. (1974). Проектирование и анализ компьютерных алгоритмов. Нью-Йорк: Addison–Wesley. С. 300–310. ISBN 0-201-00029-6.
125. Шёнхаге, А. (1971). «Шнеле Берехнунг фон Кеттенбрухентвиклунген». Acta Informatica (на немецком языке). 1 (2): 139–144. дои : 10.1007/BF00289520. S2CID  34561609.
126. Cesari, G. (1998). "Параллельная реализация алгоритма целочисленного НОД Шёнхаге". В G. Buhler (ред.). Algorithmic Number Theory: Proc. ANTS-III, Portland, OR . Lecture Notes in Computer Science. Vol. 1423. New York: Springer-Verlag. pp. 64–76.
127. Stehlé, D.; Zimmermann, P. (2005). " Повторный взгляд на метод точных таблиц Гала ". Труды 17-го симпозиума IEEE по компьютерной арифметике (ARITH-17) . Лос-Аламитос, Калифорния: IEEE Computer Society Press .
128. Lang, S. (1984). Алгебра (2-е изд.). Menlo Park, CA: Addison–Wesley. стр. 190–194. ISBN 0-201-05487-6.
129. Weinberger, P. (1973). "О евклидовых кольцах алгебраических целых чисел". Proc. Sympos. Pure Math . Труды симпозиумов по чистой математике. 24 : 321–332. doi :10.1090/pspum/024/0337902. ISBN 9780821814246.
130. Stillwell 2003, стр. 151–152
131. Boyer, CB; Merzbach, UC (1991). История математики (2-е изд.). Нью-Йорк: Wiley. С. 116–117. ISBN 0-471-54397-7.
132. Каджори, Ф. (1894). История математики. Нью-Йорк: Macmillan. С. 70. ISBN 0-486-43874-0.
133. Жу, Антуан (2009). Алгоритмический криптоанализ. ЦРК Пресс. п. 33. ISBN 9781420070033.
134. Фукс, ДБ; Табачников, Серж (2007). Математический омнибус: Тридцать лекций по классической математике. Американское математическое общество. стр. 13. ISBN 9780821843161.
135. Дарлинг, Дэвид (2004). "Константа Хинчина". Универсальная книга математики: от абракадабры до парадоксов Зенона. John Wiley & Sons. стр. 175. ISBN 9780471667001.
136. Уильямс, Колин П. (2010). Исследования в области квантовых вычислений. Springer. С. 277–278. ISBN 9781846288876.
137. Кокс, Литтл и О'Ши 1997, стр. 37–46.
138. Шредер 2005, стр. 254–259
139. Граттан-Гиннесс, Айвор (1990). Свертки во французской математике, 1800-1840: от исчисления и механики к математическому анализу и математической физике. Том II: Повороты. Научные сети: исторические исследования. Том 3. Базель, Бостон, Берлин: Birkhäuser. стр. 1148. ISBN 9783764322380. Наш предмет здесь - "последовательность Штурма" функций, определяемых через функцию и ее производную с помощью алгоритма Евклида, для вычисления количества действительных корней многочлена в заданном интервале.
140. Хайрер, Эрнст; Нёрсетт, Сиверт П.; Ваннер, Герхард (1993). "Критерий Раута–Гурвица". Решение обыкновенных дифференциальных уравнений I: Нежесткие задачи. Springer Series in Computational Mathematics. Т. 8 (2-е изд.). Springer. С. 81 и далее. ISBN 9783540566700.
141. Stillwell 2003, стр. 101–116
142. Hensley, Doug (2006). Непрерывные дроби. World Scientific. стр. 26. ISBN 9789812564771.
143. Дедекинд, Ричард (1996). Теория целых алгебраических чисел. Кембриджская математическая библиотека. Издательство Кембриджского университета. С. 22–24. ISBN 9780521565189.
144. Джонстон, Бернард Л.; Ричман, Фред (1997). Числа и симметрия: Введение в алгебру. CRC Press. стр. 44. ISBN 9780849303012.
145. Адамс, Уильям У.; Голдштейн, Ларри Джоэл (1976). Введение в теорию чисел . Prentice-Hall. Упражнение 24, стр. 205. ISBN 9780134912820. Сформулируйте и докажите аналог китайской теоремы об остатках для гауссовых целых чисел.
146. Старк 1978, стр. 290
147. Кон 1962, стр. 104–105.
148. Лауритцен, Нильс (2003). Конкретная абстрактная алгебра: от чисел до базисов Грёбнера. Cambridge University Press. стр. 130. ISBN 9780521534109.
149. Лауритцен (2003), стр. 132
150. Лауритцен (2003), стр. 161
151. Sharpe, David (1987). Кольца и факторизация . Cambridge University Press. стр. 55. ISBN 9780521337182.
152. Шарп (1987), стр. 52
153. Лауритцен (2003), стр. 131
154. Ламе, Г. (1847). «Запоминание о разрешении, в комплексных числах, об уравнении A ⁿ + B ⁿ + C ⁿ = 0». Дж. Математика. Приложение Pures. (на французском языке). 12 : 172–184.
155. Эдвардс, Х. (2000). Последняя теорема Ферма: генетическое введение в алгебраическую теорию чисел . Springer. стр. 76.
156. Кон 1962, стр. 104–110.
157. LeVeque, WJ (2002) [1956]. Темы теории чисел, тома I и II. Нью-Йорк: Dover Publications. стр. II:57, 81. ISBN 978-0-486-42539-9. Збл  1009.11001.
158. Clark, DA (1994). «Квадратичное поле, которое является евклидовым, но не нормированным». Manuscripta Mathematica . 83 : 327–330. doi : 10.1007/BF02567617 . S2CID  895185. Zbl  0817.11047.
159. Bueso, Gómez-Torrecillas & Verschoren (2003); см. стр. 37-38 для некоммутативных расширений алгоритма Евклида и следствие 4.35, стр. 40, для дополнительных примеров некоммутативных колец, к которым они применимы.
160. Davidoff, Giuliana ; Sarnak, Peter; Valette, Alain (2003). "2.6 Арифметика целочисленных кватернионов". Элементарная теория чисел, теория групп и графы Рамануджана . Студенческие тексты Лондонского математического общества. Том 55. Cambridge University Press. С. 59–70. ISBN 9780521531436.
161. Рибенбойм, Пауло (2001). Классическая теория алгебраических чисел. Universitext. Springer-Verlag. стр. 104. ISBN 9780387950709.

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

• Буэсо, Хосе; Гомес-Торресильяс, Хосе; Вершорен, Ален (2003). Алгоритмические методы в некоммутативной алгебре: приложения к квантовым группам . Математическое моделирование: теория и приложения. Том 17. Kluwer Academic Publishers, Дордрехт. doi :10.1007/978-94-017-0285-0. ISBN 1-4020-1402-3. МР  2006329.
• Коэн, Х. (1993). Курс вычислительной алгебраической теории чисел. Нью-Йорк: Springer-Verlag. ISBN 0-387-55640-0.
• Кон, Х. (1962). Advanced Number Theory. Нью-Йорк: Довер. ISBN 0-486-64023-X.
• Кокс, Д.; Литтл, Дж.; О'Ши, Д. (1997). Идеалы, многообразия и алгоритмы: введение в вычислительную алгебраическую геометрию и коммутативную алгебру (2-е изд.). Springer-Verlag. ISBN 0-387-94680-2.
• Крэндалл, Р.; Померанс , К. (2001). Простые числа: вычислительная перспектива (1-е изд.). Нью-Йорк: Springer-Verlag. ISBN 0-387-94777-9.
• Лежен Дирихле, PG (1894). Дедекинд, Ричард (ред.). Vorlesungen über Zahlentheorie (Лекции по теории чисел) (на немецком языке). Брауншвейг: Просмотрег. LCCN  03005859. OCLC  490186017.. См. также Vorlesungen über Zahlentheorie.
• Кнут, Д.Э. (1997). Искусство программирования , том 2: Получисленные алгоритмы (3-е изд.). Эддисон–Уэсли. ISBN 0-201-89684-2.
• ЛеВек, WJ (1996) [1977]. Основы теории чисел . Нью-Йорк: Дувр. ISBN 0-486-68906-9.
• Mollin, RA (2008). Фундаментальная теория чисел с приложениями (2-е изд.). Boca Raton: Chapman & Hall/CRC. ISBN 978-1-4200-6659-3.
• Оре, О. (1948). Теория чисел и ее история . Нью-Йорк: McGraw–Hill.
• Rosen, KH (2000). Элементарная теория чисел и ее приложения (4-е изд.). Reading, MA: Addison–Wesley. ISBN 0-201-87073-8.
• Шредер, М. (2005). Теория чисел в науке и коммуникации (4-е изд.). Springer-Verlag. ISBN 0-387-15800-6.
• Старк, Х. (1978). Введение в теорию чисел. MIT Press. ISBN 0-262-69060-8.
• Стиллвелл, Дж. (1997). Числа и геометрия . Нью-Йорк: Springer-Verlag. ISBN 0-387-98289-2.
• Стиллвелл, Дж. (2003). Элементы теории чисел . Нью-Йорк: Springer-Verlag. ISBN 0-387-95587-9.
• Таттерсолл, Дж. Дж. (2005). Элементарная теория чисел в девяти главах . Кембридж: Cambridge University Press . ISBN 978-0-521-85014-8.

Внешние ссылки

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