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

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

В математике , то алгоритм Евклида или алгоритм Евклида , является эффективным способом для вычисления наибольший общий делитель (GCD) двух целых чисел (цифр), наибольшее число , которое делит их обоих без остатка . Он назван в честь древнегреческого математика Евклида , который впервые описал его в своих « Элементах» (около 300 г. до н. Э.). Это пример алгоритма , пошаговой процедуры для выполнения вычислений в соответствии с четко определенными правилами, и это один из старейших широко используемых алгоритмов. Его можно использовать для приведения дробей к их простейшей форме и является частью многих других теоретико-числовых и криптографических вычислений.

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

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

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

Справочная информация: наибольший общий делитель

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

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

Прямоугольник 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 . Наибольший общий делитель г из и б является единственным (положительным) общим делителем и Ь , что делится на любом другом общий делитель с .

НОД можно визуализировать следующим образом. Рассмотрим прямоугольную область 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 . Например, поскольку 1386 можно разложить на 2 × 3 × 3 × 7 × 11, а 3213 можно разложить на 3 × 3 × 3 × 7 × 17, наибольший общий делитель 1386 и 3213 равен 63 = 3 × 3 × 7, произведение их общих простых факторов. Если у двух чисел нет общих простых делителей, их наибольший общий делитель равен 1 (получен здесь как пример пустого произведения ), другими словами, они взаимно просты. Ключевым преимуществом алгоритма Евклида является то, что он может эффективно находить НОД без необходимости вычислять простые множители. Считается, что факторизация больших целых чисел является очень сложной вычислительной проблемой, и безопасность многих широко используемых криптографических протоколов основана на ее невозможности.

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

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

gcd ( a ,  b ,  c ) = gcd ( a , gcd ( b ,  c )) = gcd (gcd ( a ,  b ),  c ) = gcd (gcd ( a ,  c ),  b ).

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

Описание

Процедура

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

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

${\ Displaystyle r_ {k-2} = q_ {k} r_ {k-1} + r_ {k}}$

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

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

${\ displaystyle {\ begin {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 \ end {align}}}$

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

Поскольку остатки уменьшаются с каждым шагом, но никогда не могут быть отрицательными, остаток r _N должен в конечном итоге равняться нулю, и на этом этапе алгоритм останавливается. Последний ненулевой остаток r _{N −1} является наибольшим общим делителем a и b . Число N не может быть бесконечным, потому что между начальным остатком r ₀ и нулем находится только конечное число неотрицательных целых чисел .

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

Справедливость алгоритма Евклида может быть доказана двухэтапным аргументом. На первом этапе показано , что последний ненулевой остаток 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.}

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

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

r _{N −3} = q _{N −1} r _{N −2} + r _{N −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 - наибольший общий делитель всех последующих пар:

g = gcd ( a , b ) = gcd ( b , r ₀ ) = gcd ( r ₀ , r ₁ ) =… = gcd ( r _{N −2} , r _{N −1} ) = r _{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. Можно вычесть три кратных числа ( q ₁  = 3), в результате останется остаток 21:

462 = 3 × 147 + 21.

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

147 = 7 × 21 + 0.

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

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

Алгоритм Евклида можно представить себе в терминах мозаичной аналогии, приведенной выше для наибольшего общего делителя. Предположим, что мы хотим точно покрыть прямоугольник размером a на b квадратными плитками, где a - большее из двух чисел. Мы первая попытка плитки прямоугольника , используя б матрицы с размерностью б квадратных плиток; Однако, это оставляет г ₀ матрицы с размерностью б остаточный прямоугольник untiled, где г _-  <  б . Затем мы пытаемся выложить остаточный прямоугольник плитками размером r _{0 на} 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 является неотрицательным и строго меньше , чем абсолютное значение от г _{к -1} . Теорема, лежащая в основе определения евклидова деления, гарантирует, что такое частное и остаток всегда существуют и уникальны.

В исходной версии алгоритма Евклида частное и остаток находятся путем повторного вычитания; то есть 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} .

Реализации

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

function gcd(a, b)
    while b ≠ 0
        t := b
        b := a mod b
        a := t
    return a

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

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

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

function gcd(a, b)
    while a ≠ b 
        if a > b
            a := a − b
        else
            b := b − a
    return a

Переменные 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} , и так далее.

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

function gcd(a, b)
    if b = 0
        return a
    else
        return gcd(b, a mod b)

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

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

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

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

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

предположил, что | r _{k −1} | >  г _к  > 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

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

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

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

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

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

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

Спустя столетия алгоритм Евклида был независимо открыт как в Индии, так и в Китае, в первую очередь для решения диофантовых уравнений , возникших в астрономии, и создания точных календарей. В конце 5-го века индийский математик и астроном Арьябхата описал алгоритм как «измельчитель», возможно, из-за его эффективности при решении диофантовых уравнений. Хотя частный случай китайской теоремы об остатках уже был описан в китайской книге Сунцзи Суаньцзин , общее решение было опубликовано Цинь Цзюшао в его книге 1247 года Шушу Цзючжан (數 書 九章Математический трактат в девяти разделах ). Алгоритм евклидовой впервые был описан числен и популяризировал в Европе во втором издании Баша в задачах и их plaisants и др délectables ( и приятных проблемы , 1624). В Европе он также использовался для решения диофантовых уравнений и для построения цепных дробей . Расширенный алгоритм Евклида был опубликован английским математиком Николас Сондерсона , который приписывает его к Roger Cotes в качестве способа для эффективного вычисления дробей.

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

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

Алгоритм Евклида был первым алгоритмом целочисленных отношений , который представляет собой метод нахождения целочисленных отношений между соизмеримыми действительными числами. Было разработано несколько новых алгоритмов целочисленных отношений , таких как алгоритм Геламана Фергюсона и RW Forcade (1979) и алгоритм LLL .

В 1969 году Коул и Дэви разработали игру для двух игроков, основанную на алгоритме Евклида, под названием «Игра Евклида» , которая имеет оптимальную стратегию. Игроки начинают с двумя стопками камней a и b . Игроки по очереди удаляют m кратных меньших стопок из большей. Таким образом, если две стопки состоят из x и y камней, где x больше, чем y , следующий игрок может уменьшить большую стопку с x камней до x - моих камней, если последнее является неотрицательным целым числом. Побеждает тот игрок, который первым уменьшит одну стопку камней до нуля.

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

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

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

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

g = r _{N −1} = r _{N −3} - q _{N −1} r _{N −2}  .

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

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

r _{N −3} = r _{N −5} - q _{N −3} r _{N −4}  .

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

г ₂ = г ₀ - д ₂ г ₁

г ₁ = б - д ₁ г ₀

г ₀ = а - q ₀ б .

После подстановки всех остатков r ₀ , r ₁ и т. Д. Окончательное уравнение выражает g как линейную сумму a и b : g  =  sa  +  tb . Тождество Безу и , следовательно, предыдущий алгоритм можно обобщить на контекст евклидовых областей .

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

Тождество Безу дает еще одно определение наибольшего общего делителя g двух чисел a и b . Рассмотрим набор всех чисел 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 ,

мг = msa + mtb .

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

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

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

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

s _k = s _{k −2} - q _k s _{k −1}

t _k = t _{k −2} - q _k t _{k −1}

со стартовыми значениями

s ₋₂ = 1, t ₋₂ = 0

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

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

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

r _j = s _j a + t _j b

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

Р К _знак равно Р _{К −2} - д _К Р _{К −1} .

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

r _k = ( s _{k −2} a + t _{k −2} b ) - q _k ( s _{k −1} a + t _{k −1} b ).

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

r _k = s _k a + t _k b = ( s _{k −2} - q _k s _{k −1} ) a + ( t _{k −2} - q _k t _{k −1} ) b .

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

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

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

может быть записано как произведение матриц частных 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}} \ ,.}$

Чтобы выразить г в виде линейной суммы и б , обе стороны этого уравнения можно умножить на обратной матрицы М . Определитель из М равен (-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}} \ ,.}$

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

g = (−1) ^{N +1} ( m ₂₂ a - m ₁₂ b ),

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

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

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

1 = su + tw  .

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

v = suv + twv = sL + twv  .

Поскольку w делит оба члена в правой части, он должен также делить левую часть, v . Этот результат известен как лемма Евклида . В частности, если простое число делит L , то он должен разделить по крайней мере один фактор L . Наоборот, если число w взаимно просто с каждым из ряда чисел a ₁ , a ₂ , ..., a _n , то w также взаимно просто с их произведением a ₁  ×  a ₂  × ... ×  a _n .

Леммы Евклида достаточно, чтобы доказать, что каждое число имеет уникальное разложение на простые числа. Чтобы убедиться в этом, предположим противное, что есть две независимые факторизации 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. Решения показаны синими кружками.

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

ах + по = с

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

ax ≡ c mod b .

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

sa + tb = g

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

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

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

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

а ( х ₁ - х ₂ ) = Ь ( у ₂ - у ₁ ).

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

х = х ₁ - бу / г

у = у ₁ + аи / г .

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

Мультипликативные инверсии и алгоритм 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 ).   

В таком поле с т чисел, каждый ненулевой элемент имеет уникальную модульную мультипликативный обратный , ^-1 такое , что аа ^-1  =  с ^-1 в  ≡ 1 по модулю  т . Это обратное можно найти, решив уравнение сравнения ax  ≡ 1 mod  m или эквивалентное линейное диофантово уравнение

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

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

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

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

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

Цель состоит в том, чтобы определить 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 х \ эквив (х_ {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 . Этот факт можно использовать, чтобы доказать, что каждое положительное рациональное число встречается в этом дереве ровно один раз.

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

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

${\ Displaystyle {\ begin {align} & \ gcd (3,4) & \ leftarrow \\ = {} & \ gcd (3,1) & \ rightarrow \\ = {} & \ gcd (2,1) & \ rightarrow \\ = {} & \ gcd (1,1). \ end {выравнивается}}}$

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

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

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

${\ displaystyle {\ begin {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} \,. \ end {выровнено}}}$

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

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

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

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

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

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

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

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

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

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

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

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

Количество шагов для вычисления НОД двух натуральных чисел a и b можно обозначить T ( a ,  b ). Если g - НОД элементов a и b , то a  =  mg и b  =  ng для двух взаимно простых чисел m и n . потом

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

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

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

T ( a , b ) = 1 + T ( b , r ₀ ) = 2 + T ( r ₀ , r ₁ ) =… = N + T ( r _{N −2} , r _{N −1} ) = N + 1

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

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

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

Этого результата достаточно, чтобы показать, что количество шагов в алгоритме Евклида никогда не может превышать количество его цифр более чем в пять раз (основание 10). Ведь если алгоритм требует 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.

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

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

Чтобы уменьшить этот шум, второе среднее значение τ ( 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 , где φ - функция Эйлера . Это среднее тау растет плавно а

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

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

${\ 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) \ приблизительно 1,467}$

где γ является постоянной Эйлера-Mascheroni и ζ»является производной от дзета - функции Римана . Старший коэффициент (12 / π ² ) ln 2 определялся двумя независимыми методами.

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

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

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

${\ Displaystyle Т (а) \ приблизительно C + {\ frac {12} {\ pi ^ {2}}} \ ln 2 \ left (\ ln a- \ sum _ {d \ mid a} {\ frac {\ Lambda (d)} {d}} \ right)}$

где Λ ( d ) - функция Мангольдта .

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

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

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

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

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

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

г _{к -2} = д _к т _{к -1} + г _к .

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

Р К _знак равно Р _{К −2} - д _К Р _{К −1} .

Вычислительные затраты деления ч -разрядного числа шкал , как O ( ч ( л + 1)), где ℓ является длиной фактора.

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

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

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

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

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

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

Алгоритм двоичного НОД является эффективной альтернативой , которая заменяет деление с более быстрыми операциями за счет использования двоичного представления , используемый компьютерами. Однако эта альтернатива также масштабируется как O ( h ²) . Как правило, он быстрее, чем алгоритм Евклида на реальных компьютерах, хотя масштабируется таким же образом. Дополнительную эффективность можно получить, изучив только первые цифры двух чисел a и b . Бинарный алгоритм может быть расширен на другие основы ( k- мерные алгоритмы) с пятикратным увеличением скорости. Алгоритм НОД Лемера использует тот же общий принцип, что и бинарный алгоритм, для ускорения вычислений НОД с произвольной базой.

Рекурсивный подход для очень больших целых чисел (более 25 000 цифр) приводит к квазилинейным целочисленным алгоритмам НОД, таким как алгоритмы Шёнхаге, Стеле и Циммерманна. Эти алгоритмы используют матричную форму 2 × 2 алгоритма Евклида, приведенного выше . Эти квазилинейные методы обычно масштабируются как O ( h (log h ) ² (log log h )).

Обобщения

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

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

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

Алгоритм Евклида с действительными числами отличается от своего целочисленного аналога в двух отношениях. Во-первых, остатки 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 ₂ ,…] . Примерами бесконечных цепных дробей являются золотое сечение φ = [1; 1, 1, ...] и квадратный корень из двух , √ 2 = [1; 2, 2, ...] . Алгоритм вряд ли остановится, так как почти все отношения a / b двух действительных чисел иррациональны.

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

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

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

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

Полиномы

Многочлены от одной переменной x можно складывать, умножать и разложить на неприводимые многочлены , которые являются аналогами простых чисел для целых чисел. Наибольший многочлен общего делителя g ( x ) двух многочленов a ( x ) и b ( x ) определяется как произведение их общих неприводимых многочленов, которые можно идентифицировать с помощью алгоритма Евклида. Основная процедура аналогична работе с целыми числами. На каждом шаге 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 ) .

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

${\ displaystyle {\ begin {align} 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 {выравнивается}}}$

Деление 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 ) , в соответствии с их факторизацией.

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

У полиномиального алгоритма Евклида есть и другие приложения, такие как цепи Штурма , метод подсчета нулей полинома , лежащих внутри заданного реального интервала . Это, в свою очередь, имеет приложения в нескольких областях, таких как критерий устойчивости Рауса – Гурвица в теории управления .

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

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

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

Целые числа Гаусса - это комплексные числа вида α = u + vi , где u и v - обычные целые числа, а i - квадратный корень из отрицательной единицы . Определяя аналог алгоритма Евклида, можно показать, что гауссовские целые числа однозначно факторизуемы с помощью приведенного выше аргумента . Эта уникальная факторизация полезна во многих приложениях, таких как вывод всех троек Пифагора или доказательство теоремы Ферма о суммах двух квадратов . В целом алгоритм Евклида удобен в таких приложениях, но не является существенным; например, теоремы часто можно доказать другими аргументами.

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

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

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

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

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

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

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

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

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

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

Распределение простых чисел Эйзенштейна 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. Случаи D = −1 и D = −3 дают целые числа Гаусса и целые числа Эйзенштейна соответственно.

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

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

Алгоритм Евклида может применяться к некоторым некоммутативным кольцам, таким как набор кватернионов Гурвица . Пусть α и β представляют два элемента из такого кольца. У них есть общий правый делитель δ, если α = ξδ и β = ηδ при некотором выборе ξ и η в кольце. Аналогично, у них есть общий левый дивизор, если α = dξ и β = dη для некоторого выбора ξ и η в кольце. Поскольку умножение не коммутативно, существует две версии алгоритма Евклида: одна для правых делителей, а другая для левых делителей. Выбирая правильные делители, первый шаг в нахождении НОД ( α , β ) с помощью алгоритма Евклида можно записать

${\ Displaystyle \ rho _ {0} = \ альфа - \ psi _ {0} \ beta = (\ xi - \ psi _ {0} \ eta) \ delta,}$

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

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

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

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

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

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

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

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

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

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

Примечания

использованная литература

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

• Коэн, Х. (1993). Курс вычислительной алгебраической теории чисел . Нью-Йорк: Springer-Verlag. ISBN 0-387-55640-0.
• Кон, Х. (1962). Продвинутая теория чисел . Нью-Йорк: Дувр. ISBN 0-486-64023-X.
• Кокс, Д .; Little, J .; О'Ши, Д. (1997). Идеалы, разновидности и алгоритмы: введение в вычислительную алгебраическую геометрию и коммутативную алгебру (2-е изд.). Springer-Verlag. ISBN 0-387-94680-2.
• Crandall, R .; Померанс, К. (2001). Простые числа: вычислительная перспектива (1-е изд.). Нью-Йорк: Springer-Verlag. ISBN 0-387-94777-9.
• Лежен Дирихле, PG (1894). Дедекинд, Ричард (ред.). Vorlesungen über Zahlentheorie (Лекции по теории чисел) (на немецком языке). Брауншвейг: Vieweg. LCCN  03005859 . OCLC  490186017 .. См. Также Vorlesungen über Zahlentheorie.
• Knuth, DE (1997). Искусство компьютерного программирования , Том 2: получисловые алгоритмы (3-е изд.). Аддисон-Уэсли. ISBN 0-201-89684-2.
• Левек, WJ (1996) [1977]. Основы теории чисел . Нью-Йорк: Дувр. ISBN 0-486-68906-9.
• Моллин, Р.А. (2008). Фундаментальная теория чисел с приложениями (2-е изд.). Бока-Ратон: Chapman & Hall / CRC. ISBN 978-1-4200-6659-3.
• Оре, О. (1948). Теория чисел и ее история . Нью-Йорк: Макгроу – Хилл.
• Розен, К. Х. (2000). Элементарная теория чисел и ее приложения (4-е изд.). Ридинг, Массачусетс: Аддисон – Уэсли. 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). Элементарная теория чисел в девяти главах . Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-85014-8.

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

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