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

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

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

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

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

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

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

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

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 должен в конечном итоге равняться нулю, и на этом этапе алгоритм останавливается. ^[13] Последний ненулевой остаток r _{N −1} является наибольшим общим делителем a и b . Число N не может быть бесконечным, потому что между начальным остатком r ₀ и нулем находится только конечное число неотрицательных целых чисел .

Доказательство действительности [ править ]

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

Чтобы продемонстрировать, что 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 является наибольшим общим делителем всех последующих пар: ^{[15] [16]}

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 вычитаются из 1071, пока остаток не станет меньше 462. Два таких кратных можно вычесть ( q ₀  = 2), в результате остается 147:

1071 = 2 × 462 + 147.

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

462 = 3 × 147 + 21.

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

147 = 7 × 21 + 0.

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

Визуализация [ править ]

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

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

Реализации [ править ]

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

функция gcd (a, b), а b ≠ 0 t: = b b: = a mod b а: = т возвращение

В начале 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} .

В версии на основе вычитания, которая была исходной версией Евклида, вычисление остатка ( ) заменено повторным вычитанием. ^{[20] В} отличие от версии на основе деления, которая работает с произвольными целыми числами в качестве ввода, версия на основе вычитания предполагает, что ввод состоит из положительных целых чисел, и останавливается, когда 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 - следующий остатокг _к . Затем b уменьшается на кратное a, пока оно снова не станет меньше a , что дает следующий остаток r _{k +1} , и так далее.

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

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

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

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

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

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

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

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

Историческое развитие [ править ]

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

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

Спустя столетия алгоритм Евклида был независимо открыт как в Индии, так и в Китае ^[33], главным образом для решения диофантовых уравнений , возникших в астрономии, и создания точных календарей. В конце 5-го века индийский математик и астроном Арьябхата описал алгоритм как «измельчитель» ^[34], возможно, из-за его эффективности при решении диофантовых уравнений. ^[35] Хотя частный случай китайской теоремы об остатках уже был описан в китайской книге Sunzi Suanjing , ^[36] общее решение было опубликовано Qin Jiushao в его книге 1247 года Shushu Jiuzhang(數 書 九章Математический трактат в девяти разделах ). ^[37] Евклида алгоритм был впервые описан числен и популяризировал в Европе во втором издании Баша в задачах и их plaisants и др délectables ( и приятные проблемы , 1624). ^[34] В Европе он также использовался для решения диофантовых уравнений и для построения цепных дробей . Расширенный алгоритм Евклида был опубликован английским математиком Николас Саундерсона , ^[38] , которые приписывают его к Roger Cotes в качестве способа для эффективного вычисления дробей.^[39]

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

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

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

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

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

Личность Безу [ править ]

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

Целые числа s и t можно вычислить из частных q ₀ , q ₁ и т. Д., Изменив порядок уравнений в алгоритме Евклида. ^[56] Начиная с предпоследнего уравнения, 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 . ^[10] Рассмотрим множество всех чисел 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 ). НОД называется генератором идеала из и б . Это определение НОД привело к современным абстрактным алгебраическим концепциям главного идеала (идеал, порожденный одним элементом) и области главных идеалов ( область в котором каждый идеал является главным идеалом).

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

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

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

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 также можно найти с помощью эквивалентного матричного метода. ^[59] Последовательность уравнений алгоритма Евклида.

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

Чтобы выразить г в виде линейной суммы и б , обе стороны этого уравнения можно умножить на обратной матрицы М . ^{[59] [60]} определитель из М равен (-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 ₁₂ . Матричный метод столь же эффективен, как и эквивалентная рекурсия, с двумя умножениями и двумя сложениями на шаг алгоритма Евклида.

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

Личность Безу важна для многих приложений алгоритма Евклида, таких как демонстрация уникального факторизации чисел на простые множители. ^[61] Чтобы проиллюстрировать это, предположим, что число 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 . Этот результат известен как лемма Евклида . ^[62] В частности, если простое число делит л , то он должен разделить по крайней мере один фактор L . Наоборот, если число w взаимно просто с каждым из ряда чисел a ₁ , a ₂ , ..., a _n , то w также взаимно просто с их произведением a ₁  ×  a ₂  × ... ×  a _n . ^[62]

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

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

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

Линейные диофантовы уравнения [ править ]

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

ах + по = с

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

ax ≡ c mod b .

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

sa + tb = g

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

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

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

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

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

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

х = х ₁ - бу / г

у = у ₁ + аи / г .

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

Мультипликативные инверсии и алгоритм 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 , ^[69] или эквивалентное линейное диофантово уравнение ^[70]

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

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

Китайская теорема об остатках [ править ]

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

${\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 . ^[75] Этот факт можно использовать для доказательства того, что каждое положительное рациональное число встречается в этом дереве ровно один раз.

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

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

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

Непрерывные дроби [ править ]

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

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

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

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

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

Алгоритмы факторизации [ править ]

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

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

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

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

Количество шагов [ править ]

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

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

что можно увидеть, разделив все шаги алгоритма Евклида на g . ^[94] По тому же аргументу, количество шагов остается неизменным, если 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 по предположению. ^[93]

Худший случай [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Комбинирование расчетного количества шагов с расчетными вычислительными затратами на шаг показывает, что алгоритм Евклида растет квадратично ( 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}).}$

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

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

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

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

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

Обобщения [ править ]

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

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

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

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

Бесконечная непрерывная дробь может быть усечена на шаге 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 : ^[134]

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

Полиномы [ править ]

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

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

${\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 ) в соответствии с их факторизацией.

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

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

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

Гауссовские целые числа [ править ]

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

Алгоритм Евклида, разработанный для двух целых гауссовских чисел α и β , почти такой же, как и алгоритм для обычных целых чисел ^[140], но отличается в двух отношениях. Как и раньше, задача на каждом шаге 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 обычно находятся путем округления действительной и комплексной частей точного отношения (например, комплексного числа α / β ) до ближайших целых чисел. ^[140]Второе отличие состоит в необходимости определения того, как один комплексный остаток может быть «меньше» другого. Для этого определяется функция нормы f ( u + vi ) = u ² + v ² , которая преобразует каждое целое гауссовское число u + vi в обычное целое число. После каждого шага k алгоритма Евклида норма остатка f ( r _k ) меньше, чем норма предыдущего остатка, f ( r _{k −1} ). Поскольку норма является неотрицательным целым числом и уменьшается с каждым шагом, алгоритм Евклида для целых гауссовских чисел завершается за конечное число шагов. ^[141] Последний ненулевой остаток - это НОД ( α , β ) , гауссовское целое число наибольшей нормы, которое делит как α, так и β ; он уникален с точностью до умножения на единицу, ± 1 или ± i . ^[142]

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

Евклидовы домены [ править ]

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

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

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

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

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

В квадратичных целых кольцах являются полезными для иллюстрации домены евклидовы. Квадратичные целые числа являются обобщением гауссовских целых чисел, в которых мнимая единица 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. ^{[154] [155]} Случаи D = −1 и D = −3 дают гауссовские целые числа и целые числа Эйзенштейна соответственно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Библиография [ править ]

• Коэн, Х. (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-е изд.). Бока-Ратон: Чепмен и Холл / 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
• Игра Евклида на пороге
• Музыка и алгоритм Евклида