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

Эта статья об алгоритме определения наибольшего общего делителя. Для математики пространства см. Евклидову геометрию . Чтобы узнать о других значениях слова «евклидово», см. «Евклидово (значения)» .

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

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

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

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

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

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

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

Основная статья: Наибольший общий делитель

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

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

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

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

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

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

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

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

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

Описание

Процедура

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

р _{N -2} = q _N р _{N -1}

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

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 делит остатки rk _{) ,} . По определению 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 — наибольший общий делитель всех последующих пар:

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

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

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

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

1071 = 2 × 462 + 147.

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

462 = 3 × 147 + 21.

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

147 = 7 × 21 + 0.

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

Шаг k	Уравнение	Частное и остаток
0	1071 = д 0 462 + г 0	q 0 = 2 и r 0 = 147
1	462 = q 1 147 + r 1	q 1 = 3 и r 1 = 21
2	147 = q 2 21 + r 2	q 2 = 7 и r 2 = 0 ; алгоритм заканчивается

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

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

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

Основная статья: Евклидово деление

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

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

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

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

р _k знак равно р _{k -2} мод р _{k -1} .

Реализации

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

функция  НОД(а, б) 
      в то время как  б ≠ 0 
          т := б 
          б :=  мод  б 
          а := т 
      вернуть ​ 
 

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

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

В версии, основанной на вычитании, которая была исходной версией Евклида, вычисление остатка ( b := a mod 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 следующий остаток rk _— . Затем b уменьшается кратно a , пока оно снова не станет меньше a , давая следующий остаток r _{k +1} и так далее.

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

функция  НОД(а, б) 
      если  б = 0 
          вернуть ​ 
      иначе 
         верните  НОД(b,  мод  b) 
 

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

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

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

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

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

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

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

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

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

| р _к | ≤ | р _{k −1} | / 2

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

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

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

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

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

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

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

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

«[Алгоритм Евклида] — дедушка всех алгоритмов, потому что это старейший нетривиальный алгоритм, дошедший до наших дней».

Дональд Кнут , Искусство компьютерного программирования, Vol. 2: Получисловые алгоритмы , 2-е издание (1981), с. 318.

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

Алгоритм Евклида был первым алгоритмом целочисленных отношений , который представляет собой метод поиска целочисленных отношений между соизмеримыми действительными числами. Было разработано несколько новых алгоритмов целочисленных отношений , таких как алгоритм Хеламана Фергюсона и Р.В. Форкейда (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} :

грамм знак равно р _{N -1} знак равно р _{N -3} - q _{N -1} р _{N -2} .

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

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

р _{N -3} знак равно р _{N -5} - q _{N -3} р _{N -4} .

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

р ₂ знак равно р ₀ - q ₂ р ₁

р ₁ знак равно б - q ₁ р ₀

р ₀ знак равно а - 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 ,

мг = мса + мтб .

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

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

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

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

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

s _k знак равно s _{k -2} - q _k s _{k -1}

т _k знак равно т _{k -2} - q _k т _{k -1}

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

с _-2 = 1, т _-2 = 0

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

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

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

р _j = s _j a + t _j b

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

р _k знак равно р _{k -2} - q _k р _{k -1} .

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

р _k знак равно ( s _{k -2} а + т _{k -2} б ) - q _k ( s _{k -1} а + т _{k -1} б ).

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

р _k знак равно s _k а + т _k б знак равно ( s _{k -2} - q _k s _{k -1} ) а + ( т _{k -2} - q _k т _{k -1} ) б .

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

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

${\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, умноженных на двумерный вектор остатка.

${\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 представляет собой произведение всех фактор-матриц

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

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

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

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

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

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

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

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

Лемма Евклида

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

1 = вс + вт

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

v = suv + twv = sL + twv

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

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

L знак равно п ₁ п ₂ … п _м знак равно q ₁ q ₂ … q _п .

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

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

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

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

топор + по = с

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

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

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

в + ТБ = г

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

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

топор ₁ + на ₁ = c = топор ₂ + на ₂

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

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

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

х = х ₁ - бу / г

y знак равно y ₁ + au / g .

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

и алгоритм

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

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

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

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

Китайская

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

${\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 _i , и определить Mi _как M

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

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

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

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

$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 являются мультипликативными обратными числами Mi их _, можно найти с помощью алгоритма Евклида, описанного в предыдущем подразделе.

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

Основная статья: Дерево Штерна – Броко

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

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

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

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

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

Цепные дроби

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

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

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

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

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

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

Итоговое соотношение остатков r _k / r _{k −1} всегда можно заменить с помощью следующего уравнения в ряду, вплоть до итогового уравнения. Результатом является непрерывная дробь

${\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), а коэффициенты составили _qk 2, 3 и 7 соответственно. Следовательно, дробь 1071/462 можно записать

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

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

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

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

эффективность

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

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

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

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

Т ( а , б ) знак равно 1 + Т ( б , р ₀ ) знак равно 2 + Т ( р ₀ , р ₁ ) знак равно … знак равно N + Т ( р _{N -2} , р _{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 > р ₀ . предположению индукции имеем b ≥ FM _{. +1} и r ₀ ≥ FM _M По Следовательно a = q ₀ b + r ₀ ≥ b + r ₀ ≥ F _{M +1} + F _M = FM _{+2 ,} , что и есть желаемое неравенство. Это доказательство, опубликованное Габриэлем Ламе в 1844 году, представляет собой начало теории сложности вычислений . а также первое практическое применение чисел Фибоначчи.

Этого результата достаточно, чтобы показать, что число шагов в алгоритме Евклида никогда не может превышать количество его цифр (по основанию 10) более чем в пять раз. Ибо если алгоритм требует N шагов, то b больше или равно F _{N +1} , что, в свою очередь, больше или равно φ. ^{Н -1} , где φ — золотое сечение . Поскольку b ≥ φ ^{Н -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.

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

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

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

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

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

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

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

$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$

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

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

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

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

$T(a)\approx 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.

$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 )

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

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

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

р _{k -2} знак равно q _k р _{k -1} + р _k .

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

р _k знак равно р _{k -2} - q _k р _{k -1} .

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

Для сравнения: оригинальный алгоритм Евклида, основанный на вычитании, может быть намного медленнее. Одно целочисленное деление эквивалентно частному q числу вычитаний . Если отношение a и b очень велико, частное велико и потребуется много вычитаний. С другой стороны, было показано, что частные, скорее всего, будут небольшими целыми числами. Вероятность данного частного q примерно равна ln | ты /( ты - 1)| где и = ( 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 , время выполнения ограничено величиной

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

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

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

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

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

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

Обобщения

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

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

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

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

${\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 ; числитель и знаменатель взаимно просты и подчиняются рекуррентному соотношению

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

$\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 ) идентифицируются для удовлетворения рекурсивного уравнения

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

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

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

${\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) х ² + (5/3) Икс - (2/3) . На следующем этапе b ( x ) делится на r ₀ ( x ) , получая остаток r ₁ ( x ) = x ² + х + 2 . Наконец, деление r ₀ ( x ) на r ₁ ( x ) дает нулевой остаток, указывая, что r ₁ ( x ) является наибольшим общим делителем многочленов a ( x ) и b ( x ) , что согласуется с их факторизацией.

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

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

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

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

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

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

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

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

где каждый остаток строго меньше своего предшественника: | р _к | < | р _{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 неумолимо ; следовательно, если f можно уменьшить только конечное число раз, алгоритм должен остановиться за конечное число шагов. Этот принцип основан на свойстве правильного упорядочения неотрицательных целых чисел, которое утверждает, что каждый непустой набор неотрицательных целых чисел имеет наименьший член.

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

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

факторизация квадратичных

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

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

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

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

$\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η для некоторого выбора ξ и η в кольце. Поскольку умножение не является коммутативным, существуют две версии алгоритма Евклида: одна для правых делителей и одна для левых делителей. Выбрав правильные делители, первый шаг в нахождении НОД( α , β ) по алгоритму Евклида можно записать

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

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

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

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

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

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

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

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

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

См. также

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

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

• Буэсо, Хосе; Гомес-Торресильяс, Хосе; Вершорен, Ален (2003). Алгоритмические методы в некоммутативной алгебре: приложения к квантовым группам . Математическое моделирование: теория и приложения. Том. 17. Издательство Kluwer Academic, Дордрехт. дои : 10.1007/978-94-017-0285-0 . ISBN  1-4020-1402-3 . МР   2006329 .
• Коэн, Х. (1993). Курс вычислительной алгебраической теории чисел . Нью-Йорк: Springer-Verlag. ISBN  0-387-55640-0 .
• Кон, Х. (1962). Расширенная теория чисел . Нью-Йорк: Дувр. ISBN  0-486-64023-Х .
• Кокс, Д .; Литтл, Дж.; О'Ши, Д. (1997). Идеалы, разновидности и алгоритмы: введение в вычислительную алгебраическую геометрию и коммутативную алгебру (2-е изд.). Спрингер-Верлаг. ISBN  0-387-94680-2 .
• Крэндалл, Р. ; Померанс, К. (2001). Простые числа: вычислительная перспектива (1-е изд.). Нью-Йорк: Springer-Verlag. ISBN  0-387-94777-9 .
• Лежен Дирихле, П.Г. Дедекинд, Ричард (ред.). Лекции по теории чисел (на немецком языке). Брауншвейг: Просмотрег. LCCN03005859   . OCLC   490186017 . . Так что смотрите лекции по теории чисел
• Кнут, 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-е изд.). Спрингер-Верлаг. ISBN  0-387-15800-6 .
• Старк, Х. (1978). Введение в теорию чисел . МТИ Пресс. 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 .

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

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