Войти
Метод Евклида для нахождения наибольшего общего делителя (НОД) двух начальных длин BA и DC, оба стандарта как кратные общей «единичной длины». Длина DC короче, она используется для «измерения» BA, но только один раз, потому что остаток EA меньше DC. EA теперь измеряет (в два раза) более короткую длину DC, а остаток FC короче, чем EA. Затем FC отмеряет (трижды) длину EA. Остаточка времени нет, процесс заканчивается тем, что FC является GCD. Справа пример Никомаха с числами 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) меньшего целого числа начало. вычислительной сложности. В ХХ веке были разработаны дополнительные методы повышения эффективности алгоритма.
Алгоритм Евклида имеет множество теоретических и практических приложений. Он используется для уменьшения дробей до их простейшей формы и для в ыполн ения деления в модульной арифметике. Вычисления с использованием этого алгоритма составляют часть криптографических протоколов, которые используются для интернет-связи, а также в методах взлома этой криптосистемы путем факторизации больших чисел. Алгоритм Евклида может предложить решения диофантовых уравнений, например для нахождения чисел, удовлетворяющих множественных сравнений согласно китайскойореме об остатках, для построения непрерывных уравнений и найти точные рациональные приближения к действительному чисм. Наконец, его можно использовать в основном качестве доказательства теоремы в теории чисел, таких как теорема Лагранжа о четырех квадратах и уникальность разложения на простые множители. Первоначальный алгоритм был описан только для различных типов чисел и различных длин (действительных чисел), но в 19 алгоритме был обобщен различные типы чисел, таких как целые числа Гаусса и полиномы одной. Это привело к появлению современных абстрактных алгебраических понятий, таких как евклидовы области.
Алгоритм Евклида вычисляет самый большой общий делитель (НОД) двух натуральных чисел а и б. На общее натуральное число g - это наибольшее делит как a, так и b, не оставляет остатка. Синонимы GCD включают в себя самый большой общий фактор (GCF), наивысший общий фактор (HCF), наивысший общий делитель (HCD) и наивысший общий фактор (GCM). На большой общий делитель записывается как gcd (a, b) или, проще говоря, как (a, b), хотя последнее обозначение часто неоднозначно, также используется для таких понятий, как идеал в кольцо целых чисел, которое связано с НОД.
Если gcd (a, b) = 1, то a и b называются взаимно простыми (или взаимно простыми). Это свойство не подразумевает, что a или b сами по себе являются простыми числами. Например, ни 6, ни 35 не являются простыми числами, так как они оба имеют два простых множителя: 6 = 2 × 3 и 35 = 5 × 7. Тем не менее, 6 и 35 взаимно просты. Никакое натуральное число, кроме 1, не делит 6 и 35, поскольку у них нет дел общих.
Прямоугольник 24 на 60 покрыт десятью квадратными плитками 12 на 12, где 12 - это НОД 24 и 60. В более общем плане прямоугольник a на b может быть покрыт квадратными плитками со стороной -длина c, только если c является общим делителем a и б. Пусть g = gcd (a, b). A и b оба кратны g, их можно записать a = mg и b = ng, и не существует большего числа G>g, для которого это верно. Натуральные числа m и n должны быть взаимно простыми, так как любой общий множитель может быть выделен из m и n, чтобы сделать g больше. Таким образом, любое другое число c, которое делит и a, и b, также должно делить g. На общий делитель g чисел a и b - это единственный (положительный) делитель a и b, который делится на любой другой общий делитель c.
НОД можно представить следующим образом. Рассмотрим прямоугольную область 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 - это произведение простых множителей, для общих двух чисел, причем один и тот же простой множитель может Inn раз, но только до тех пор, пока произведение этих множителей делит оба числа. а и б. Например, поскольку 1386 можно разложить на 2 × 3 × 3 × 7 × 11, а 3213 можно разложить на 3 × 3 × 3 × 7 × 17, наибольший общий делитель 1386 и 3213 равенство 63 = 3 × 3 × 7, произведение их общий простых факторов. Если два не имеют общих простых делителей, их самый общий делитель равен 1 (получен здесь как пример пустого произведения ), другими словами они взаимно просты. Ключевым преимуществом алгоритма Евклида является то, что он может эффективно находить GCD без необходимости вычислять простые множители. Факторизация больших целых чисел считается очень сложной вычислительной проблемой, и безопасность многих широко используемых криптографические протоколы основаны на их недопустимости.
Другое определение GCD полезно в продвинутой математике, особенно в теории колец. На максимальный общий делитель g двух ненулевых чисел a и b также является их наименьшей положительной целочисленной линейной комбинацией, то есть наименьшим положительным числом ua + vb, где u и v - целые числа. Набор всех целых линейных комбинаций a и b фактически такой же, как набор всех кратных g (mg, где m - целое число). На современном математическом языке , порожденный a и b, является идеалом, порожденным только одним, называется основным идеалом, все идеалы целые числа - главные идеалы). Некоторые свойства НОД легче увидеть с помощью этого описания, например, тот факт, что любой делитель a и b также делит НОД (он делит оба члена ua + vb). Эквивалентность этого определения GCD другим определениям описывается ниже.
НОД или более трех чисел равняется всех основных множителей, для общих чисел, но также его можно вычислить, многократно взяв НОД пар чисел. Например,
Таким образом, алгоритма Евклида, вычисляет НОД двух целых чисел, достаточно для вычислений НОД произвольного числа целых чисел.
Алгоритм Евклида состоит из ряда шагов, так что выходные данные каждого шага используются в качестве входных данных для следующего. Пусть k будет целым числом, которое считает шаги алгоритма, начиная с нуля. Таким образом, начальный шаг соответствует k = 0, следующий шаг соответствует k = 1 и так далее.
Каждый шаг начинается с двух неотрицательных остатков r k-1 и r k-2. Алгоритм гарантирует, что остатки не уменьшаются с каждым шагом, r k-1, чем его предшественник r k-2. Цель k-го шага - найти частное qkи остаток rk, которые удовлетворяют уравнению
и имеют 0 ≤ r k< rk-1. Другими словами, кратные меньшего числа r k-1 вычитаются из большего числа r k-2 до тех пор, пока остаток r k не станет меньше r k - 1.
На начальном этапе (k = 0) остатки r −2 и r −1 равны a и b, числам, для которых НОД ищется. На следующем этапе (k = 1) остатки равны b, а остатки r 0 от начального этапа и так далее. Таким образом, алгоритм можно записать в виде системы уравнений
Если a меньше b, первый шаг алгоритма меняет местами числа. Например, если < b, the initial quotient q0равен нулю, а остаток r 0 равен. Таким образом, r k меньше своего предшественника r k - 1 для всех k ≥ 0.
Временки уменьшаются с каждым шагом, но никогда не могут быть отрицательными, остатки r N должен в конечном итоге равняться нулю, после чего останавливается. Последний ненулевой остаток r N - 1 является самым большим общим делителем a и b. Число N не может быть бесконечным, потому что между начальным остатком r 0 и нулем находится только конечное число неотрицательных целых чисел.
Достоверность алгоритма Евклида может быть доказана двухэтапным аргументом. На первом изображении показан конечный ненулевой кусок r N-1 делит как a, так и b. Это общий делитель, он должен быть меньше или большему количеству делителей g. На втором представлен любой общий делитель a и b, включая g, должен делить r N - 1 ; следовательно, g должно быть меньше или равно r N-1. Эти два варианта несовместимы, если r N-1 = g.
Чтобы выполнить что r N-1 делит как a, так и b (первый шаг), r N-1 делит своего предшественника r N - 2.
, поскольку конечный остаток r N равен нулю. r N-1 также делит своего следующего предшественника r N-3
, потому что он делит оба члена в правой части уравнения. Повторяя тот же аргумент, 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 0, поскольку r 0 = a - q 0 b = mc - q 0 nc = ( m - q 0 n) c. Аналогичный аргумент показывает, что также делит последующие остатки r 1, r 2 и т. Д. Следовательно, наибольший общий делитель g должен делить r N - 1, откуда следует, что g ≤ r N - 1. Первая часть аргумента показывает обратное (r N-1 ≤ g), отсюда следует, что g = r N-1. Таким образом, g является наибольшим общим делителем всех пар:
Анимация алгоритма Евклида на основе вычитания. Исходный прямоугольник имеет размеры 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 0 = 2), оставив остаток 147:
Тогда кратные 147 вычитаются из 462, пока остаток не станет меньше 147. Можно вычесть три кратных (q 1 = 3), в результате останется остаток 21:
Затем кратные 21 вычитаются из 147, пока остаток не станет меньше 21. Можно вычесть семь кратных (q 2 = 7), не оставя остатка:
Последний остаток равенства нулю, алгоритм заканчивается 21 как наибольшим общим делителем 1071 и 462. Это согласуется с НОД (1071, 462), полученным путем разложения на простые множители выше. В табличной шаги следующие:
| Шаг k | Уравнение | Частное и остаток |
|---|---|---|
| 0 | 1071 = q 0 462 + r 0 | q0= 2 и r 0 = 147 |
| 1 | 462 = q 1 147 + r 1 | q1= 3 и r 1 = 21 |
| 2 | 147 = q 2 21 + r 2 | q2= 7 и r 2 = 0; конец алгоритма |
Алгоритм Евклида может быть визуализирован в терминах мозаичной аналогии, приведенной выше для наибольшего общего делителя. Предположим, что мы хотим точно покрыть прямоугольник a на b квадратными плитками, где a - большее из двух чисел. Сначала мы пытаемся выложить прямоугольник, используя квадратные плитки b на b; однако при этом остаточный прямоугольник размером r 0 на b остается нетронутым, а квадратные плитки размером r 0< b. We then attempt to tile the residual rectangle with r0на r 0. В результате остается второй остаточный прямоугольник r 1 -by-r 0, который мы пытаемся разбить, используя r 1 -by-r 1 квадратная плитка и тд. Последовательность завершается, когда нет остаточного прямоугольника, когда квадратные плитки точно покрывают предыдущий остаточный прямоугольник. Длина сторон самой маленькой квадратной плитки - это НОД размеров прямоугольника. Например, самая маленькая квадратная плитка на соседнем рисунке размер 21 на 21 (показан красным), а 21 - это НОД 1071 и 462, размеры прямоугольника (показано зеленым).
На каждом шаге k алгоритм Евклида вычисляет частное q k и остаток r k из двух чисел r k-1 и r k-2
, где r k - неотрицательный и строго меньше, чем абсолютное значение для r k-1. Теорема, лежащая в основе определения евклидова деления, гарантирует, что такое частное и остаток всегда существуют и уникальны.
В исходной версии алгоритма Евклида частное и остаток находятся по формуле повторное вычитание; то есть r k-1 вычитается из r k-2 многократно, пока остаток r k не станет меньше, чем r k-1. После этого r k и r k-1 меняются местами, и процесс повторяется. Евклидово деление сокращает все шаги между двумя обменами до одного шага, таким образом, более эффективно. Более того, частные не нужны, поэтому можно заменить евклидово деление операцией по модулю, которое дает только остаток. Таким образом, итерация алгоритма Евклида становится просто
Реализации алгоритма могут быть выражены в псевдокод. Например, версия с разделением может быть запрограммированной as
функцией gcd (a, b), а b ≠ 0 t: = bb: = a mod ba : = t return a
В начале k-й итерации переменная b содержит последний остаток r k - 1, тогда как переменная a содержит своего предшественника, r к-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.
. В версии на основе вычитания, которая была Евклидова В исходной версии вычисление остатка (b: = a mod b) заменяется повторным вычитанием. В качестве отличия от версии на деления, которая работает с произвольными целыми числами в вводе, версия на основе вычитания предполагает, что вводится из положительных целых чисел и останавливается, когда a = b:
function gcd (a, b) while a ≠ b if a>ba: = a - b else b: = b - a return a
Переменные a и b чередуются удерживающие предыдущие остатки r k-1 и r k-2. Предположим, что a больше, чем b в начале итерации; тогда a равно r k-2, поскольку r k-2>r k-1. Во время итерации цикла уменьшается в несколько раз по сравнению с предыдущим остатком b, пока a не станет меньше b. Тогда a - следующий остаток r k. Затем b уменьшается кратно a, пока снова не станет меньше a, что дает следующий остаток r k + 1, и так далее.
Рекурсивная версия основывается на равенстве НОД последовательных остатков и НОД условия остановки (r N-1, 0) = r N-1.
функция gcd (a, b) if b = 0 return a elsereturn gcd (b, a mod b)
Для иллюстрации gcd (1071, 462) вычисляется из эквивалентного gcd (462, 1071 mod 462) = gcd (462, 147). Последний НОД рассчитывается из НОД (147, 462 mod 147) = НОД (147, 21), который, в свою очередь, вычисляется из НОД (21, 147 mod 21) = НОД (21, 0) = 21.
В другой версии алгоритма Евклида частное на каждом шаге увеличивается на единицу, если результирующий отрицательный остаток меньше по величине, чем типичный положительный остаток. Ранее в уравнении
предполагалось, что | r k - 1 |>г к>0. Однако можно вычислить альтернативный отрицательный остаток e k :
, если r k - 1>0 или
, если r k - 1 < 0.
Если r k заменено на e k. когда | e k| < |rk|, то получается вариант алгоритма Евклида такой, что
на каждом шаге.
Леопольд Кронекер показал, что эта версия требует наименьшего количества шагов по версией алгоритма Евклида. В более общем плане было доказано, что для любых входных чисел a и b количество шагов минимально тогда и только тогда, когда q k выбрано для того, чтобы 
Алгоритм Евклида, вероятно, был изобретен до Евклида, изображен здесь правим компас на картине около 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 века евклидов алгоритм постепенно вытеснен более общей теорией идеалов.
Дедекинда «[алгоритм Евклида] является дедушкой всех алгоритмов, потому что это самый старый нетривиальный алгоритм, имеющий сохранились до наших дней». |
| Дональд Кнут, Искусство программирования, Том. 2: Получисловые алгоритмы, 2-е издание (1981), стр. 318. |
Другие приложения алгоритма Евклида были разработаны в 19 веке. В 1829 году Чарльз Штурм показал, что этот алгоритм был полезен в методе цепочки Штурма для подсчета действительных корней многочленов в любом заданном интервале.
Алгоритм Евклида был первый алгоритм целочисленных отношений, который представляет собой метод нахождения целочисленных отношений между соизмеримыми действительными числами. Было разработано несколько новых алгоритмов целочисленных отношений, таких как алгоритм Геламана Фергюсона и RW Forcade (1979) и алгоритм LLL.
в 1969 году Коул и Дэви. разработал игру для двух игроков, основанную на алгоритме Евклида, названную «Игра Евклида», которая имеет оптимальную стратегию. Игроки начинают с двумя стопками камней a и b. Игроки по очереди удаляют m кратных меньших стопок из большей. Таким образом, если две стопки состоят из x и y камней, где x больше, чем y, следующий размер может уменьшить большую стопку с x камней до x - моих камней, если последнее является целым неотрицательным числом. Победитель становится первым игроком, который уменьшит одну стопку до нуля.
Тождество Безу утверждает, что наибольший общий делитель g двух целых чисел a и b можно представить как линейную сумму двух исходных чисел a и b. Другими словами, всегда можно найти целые числа s и t такие, что g = sa + tb.
Целые числа s и t могут быть вычислены из частных q 0, q 1 и т. Д., Изменив порядок уравнений в алгоритме Евклида. Начало с предпоследнего уравнения, g можно выразить через частное q N - 1 и два предшествующих остатка, r N - 2 и r N-3 :
Эти два остатка могут быть аналогичным образом выражены через их частные и предшествующие остатки,
Подстановка эти формулы для r N-2 и r N-3 в первом уравнении дают g как линейную сумму остатков r N-4 и r N-5. Процесс остатков замены формулами, включающими их предшественников, может быть продолжен до тех пор, пока не будут достигнуты исходные числа a и b:
После подстановки всех остатков r 0, r 1 и т.д. окончательное уравнение выражает 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) эквивалентен набору кратных gcd (a, b). Говорят, что НОД является генератором идеала элементов a и b. Это определение НОД привело к современным абстрактным алгебраическим концепциям идеала (идеал, порожденный одним элементом) и области главных идеалов (домен, в котором каждый идеал есть главный идеал).
Используя этот результат, можно решить некоторые проблемы. Например, рассмотрим две мерные чашки объемом a и b. Добавляя / вычитая u, кратные первой чашке, и v, кратные второй, можно измерить любой объем ua + vb. Все эти объемы кратны g = gcd (a, b).
Целые числа s и t идентичности Безу могут быть эффективно вычислены с использованием расширенного алгоритма Евклида. Это расширение добавляет два рекурсивных уравнения к алгоритму Евклида
с начальными значениями
Используя это При рекурсии целые числа s и t Безу задаются как s = s N и t = t N, где N + 1 - шаг, на котором алгоритм завершается с r N +1 = 0.
Справедливость этого подхода можно показать по индукции. Предположим, что формула рекурсии верна до шага k - 1 алгоритма; другими словами, предположим, что
для всех j, меньших k. K-й шаг алгоритма дает уравнение
Поскольку формула рекурсии считается правильной для r k −2 и r k − 1, они могут быть выражены через соответствующие переменные s и t
Преобразование этого уравнения дает формулу рекурсии для шага k, как требуется
Целые числа s и t также можно найти с помощью эквивалента матричный метод. Последовательность уравнений алгоритма Евклида
может быть записано как произведение матриц частных 2 на 2, умноженных на двумерный вектор остатка
Пусть M представляет произведение всех матрицы частных
Это упрощает алгоритм Евклида до вида
Чтобы выразить g как линейную сумму a и b, обе части этого уравнения можно умножить на инверсия матрицы M . Определитель для M равен (-1), поскольку он равен произведению определителей матриц частных, каждая из которых отрицательна. Поскольку определитель M никогда не равен нулю, вектор конечных остатков может быть решен с использованием обратного выражения M
Поскольку верхнее уравнение дает
два целых числа идентичности Безу: s = (−1) m 22 и t = (−1) m 12. Матричный метод столь же эффективен, как и эквивалентная рекурсия, с двумя умножениями и двумя сложениями на алгоритма Евклида.
Идентичность Безу важна для многих приложений алгоритма Евклида, таких как демонстрация уникальной факторизации чисел на простые множители. Чтобы проиллюстрировать это, предположим, что число L можно записать как произведение двух множителей u и v, то есть L = uv. Если другое число также делит L, но взаимно просто с u,
