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

Алгоритм Евклида — эффективный алгоритм для нахождениянаибольшего общего делителя двух целых чисел (или общеймеры двух отрезков). Алгоритм назван в честь греческого математикаЕвклида, который впервые описал его в VII и X книгах «Начал». В самомпростом случае алгоритм Евклида применяется к паре положительных целыхчисел и формирует новую пару, которая состоит из меньшего числа иразницы между большим и меньшим числом. Процесс повторяется, пока числане станут равными. Найденное число и есть наибольший общий делительисходной пары.
 Первое описание алгоритма находится в «Началах» Евклида (около 300 летдо н. э.), что делает его одним из старейших численных алгоритмов,используемых в наше время. Оригинальный алгоритм был предложен толькодля натуральных чисел и геометрических длин (вещественных чисел). Однаков XIX веке он был обобщён на другие типы чисел, такие как целые числаГаусса и полиномы от одной переменной. Это привело к появлению всовременной общей алгебре такого понятия, как евклидово кольцо. Позжеалгоритм Евклида также был обобщён на другие математические структуры,такие как узлы и многомерные полиномы.
 Для данного алгоритма существует множество теоретических и практическихприменений. В частности, он является основой для криптографическогоалгоритма с открытым ключом RSA, широко распространённого в электроннойкоммерции. Также алгоритм используется при решении линейных диофантовыхуравнений, при построении непрерывных дробей, в методе Штурма. АлгоритмЕвклида является основным инструментом для доказательства теорем всовременной теории чисел, например таких как теорема Лагранжа о суммечетырёх квадратов и основная теорема арифметики.

История


 Древнегреческие математики называли этот алгоритм или  — «взаимноевычитание». Этот алгоритм не был открыт Евклидом, так как упоминание онём имеется уже в Топике Аристотеля. В «Началах» Евклида онописан дважды — в VII книге для нахождения наибольшего общего делителядвух натуральных чисел и в X книге для нахождения наибольшей общей мерыдвух однородных величин. В обоих случаях дано геометрическое описаниеалгоритма, для нахождения «общей меры» двух отрезков.
 Историками математики было выдвинуто предположение, что именно с помощьюалгоритма Евклида (процедуры последовательного взаимного вычитания) вдревнегреческой математике впервые было открыто существованиенесоизмеримых величин (стороны и диагонали квадрата, или стороны идиагонали правильного пятиугольника). Впрочем, это предположение неимеет достаточных документальных подтверждений. Алгоритм для поисканаибольшего общего делителя двух натуральных чисел описан также в Iкниге древнекитайского трактата Математика в девяти книгах.

Описание


Алгоритм Евклида для целыхчисел


 Пусть a и b — целые числа, не равные одновременно нулю, ипоследовательность чисел

a>b>r1>r2>r3>r4>  >rn
 определена тем, что каждое rk — это остаток от деленияпредпредыдущего числа на предыдущее, а предпоследнее делится напоследнее нацело, то есть:

a=bq0+r1,
b=r1q1+r2,
r1=r2q2+r3,

rk2=rk1qk1+rk,

rn2=rn1qn1+rn,
rn1=rnqn.
 Тогда НОД(a, b), наибольший общий делитель a иb, равен rn, последнему ненулевому членуэтой последовательности.
Существование таких r1,r2, ..., rn, то естьвозможность деления с остатком m на n для любого целогоm и целого n ≠ 0, доказывается индукцией по m.
Корректность этого алгоритма вытекает из следующих двухутверждений:

  • Пусть a = bq + r, тогда НОД (a, b) = НОД (b, r).


  • НОД(r, 0) = r для любого ненулевого r (так как 0 делится на любое целое число, кроме нуля).

Геометрический алгоритмЕвклида


 Пусть даны два отрезка длины a и b. Вычтем из большегоотрезка меньший и заменим больший отрезок полученной разностью.Повторяем эту операцию, пока отрезки не станут равны. Если этопроизойдёт, то исходные отрезки соизмеримы, и последний полученныйотрезок есть их наибольшая общая мера. Если общей меры нет, то процессбесконечен. В таком виде алгоритм описан Евклидом и реализуется спомощью циркуля и линейки.

Пример


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

 1071 = 2 × 462 + 147.
 Затем от 462 отнимем кратное значение 147, пока не получим разностьменьше, чем 147. Мы должны трижды отнять 147(q1 = 3), оставаясь с остатком 21:

 462 = 3 × 147 + 21.
 Затем от 147 отнимем кратное значение 21, пока не получим разностьменьше, чем 21. Мы должны семь раз отнять 21(q2 = 7), оставаясь без остатка:

 147 = 7 × 21 + 0.
 Таким образом последовательность a \textgreater b \textgreaterr1 \textgreater r2\textgreater r3 \textgreater \ldots\textgreater rn в данном конкретном случаебудет выглядеть так:

 1071 \textgreater 462 \textgreater 147 \textgreater 21.
 Так как последний остаток равен нулю, алгоритм заканчивается числом 21 иНОД(1071, 462) = 21.
 В табличной форме шаги были следующие:
Шаг kРавенствоЧастное и остаток
01071 = q0 462 + r0q0 = 2 и r0 = 147
1462 = q1 147 + r1q1 = 3 и r1 = 21
2147 = q2 21 + r2q2 = 7 и r2 = 0; алгоритмзаканчивается

Применения


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


 Формулы для ri могут быть переписаны следующим образом:

r1=a+b(q0)
r2=br1q1=a(q1)+b(1+q1q0)

НОД (a,b)=rn=as+bt
 Здесь s и t целые. Это представление наибольшего общегоделителя называется соотношением Безу, а числа s и t —коэффициентами Безу. Соотношение Безу является ключевым в доказательствелеммы Евклида и основной теоремы арифметики.

Цепныедроби


 Алгоритм Евклида достаточно тесно связан с цепными дробями. Отношениеa/b допускает представление в виде цепной дроби:


ab=[q0;q1,q2,,qn].

 При этом цепная дробь без последнего члена равна отношению коэффициентовБезу t/s, взятому со знаком минус:


[q0;q1,q2,,qn1]=ts.

 Последовательность равенств, задающая алгоритм Евклида, может бытьпереписана в форме:


 \{begin\{align\} \{frac\{a\}\{b\} \&= q\_0 +\{frac\{r\_0\}\{b\} \{\{\{frac\{b\}\{r\_0\} \&= q\_1 +\{frac\{r\_1\}\{r\_0\} \{\{\{frac\{r\_0\}\{r\_1\} \&= q\_2 +\{frac\{r\_2\}\{r\_1\} \{\{ \&\{\}\{ \{vdots\{\{\{frac\{r\_\{k-2\}\}\{r\_\{k-1\}\} \&= q\_k +\{frac\{r\_k\}\{r\_\{k-1\}\}\{\{ \& \{\}\{\{vdots \{\{\{frac\{r\_\{N-2\}\}\{r\_\{N-1\}\} \&= q\_N\{end\{align\}
 Последнее слагаемое в правой части равенства всегда равно обратномузначению левой части следующего уравнения. Поэтому первые два уравнениямогут быть объединены в форме:

ab=q0+1q1+r1r0
 Третье равенство может быть использовано, чтобы заменить знаменательвыражения r1/r0, получим:

ab=q0+1q1+1q2+r2r1
 Последнее отношение остатковrk/rk−1всегда может быть заменено с использованием следующего равенства впоследовательности, и так до последнего уравнения. Результатом являетсяцепная дробь:

ab=q0+1q1+1q2+1+1qN=[q0;q1,q2,,qN]
 В приведённом выше примере НОД(1071, 462) был посчитан и были найденычастные qk, равные 2, 3 и 7соответственно. Поэтому 1071/462 может быть записана как:

1071462=2+13+17=[2;3,7]

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


 Диофантово уравнение — это уравнение с целочисленными коэффициентами ис одним или несколькими переменными, причем ставится задача поиска лишьего целых корней. Такое уравнение может иметь бесконечно много решений,конечное число решений или не иметь их вовсе. Простейшее диофантовоуравнение — линейное с двумя неизвестными:
ax+by=c,
 где a, b, c — целые числа. С помощью алгоритмаЕвклида может быть найдено полное решение уравнения такого типа. Сначалас помощью этого алгоритма можно определить d = НОД(a,b). Затем, используя расширенный алгоритм Евклида, определяютсятакие k и l, что:
ak+bl=d.
 То есть x = k и y = l - это частное решение уравнения приc = d. Получается, что если c = q⋅d, то x = q⋅k,y = q⋅l - частное решение исходного уравнения, так как:
ax+by=a(qk)+b(ql)=q(ak+bl)=qd=c.
 Обратно, если существует хотя бы одно решение уравнения, то cкратно d. Это следует из того, что d делит и a, иb (а значит, и всю левую часть), поэтому должно делить и c(правую часть). Таким образом, линейное диофантово уравнение имеет хотябы одно решение тогда и только тогда, когда c кратноНОД(a, b).

Вариации иобобщения


Евклидовокольцо


 Кольца, в которых применим алгоритм Евклида, называются евклидовымикольцами. К ним относятся, в частности, кольца целых чисел и кольцамногочленов.

Обобщённый алгоритм Евклида длямногочленов


 Алгоритм Евклида и расширенный алгоритм Евклида естественным образомобобщается на кольцо многочленов k[x] от однойпеременной над произвольным полем k, поскольку для такихмногочленов определена операция деления с остатком. При выполненииалгоритма Евклида для многочленов аналогично алгоритму Евклида для целыхчисел получается последовательность полиномиальных остатков (PRS).

Ускоренные версииалгоритма



  • Одним из методов ускорения целочисленного алгоритма Евклида является использование симметричного остатка:



riri2(modri1),


  • Одна из версий ускоренного алгоритма Евклида для полиномов основывается на том, что промежуточные значения алгоритма в основном зависят от высоких степеней. Применение стратегии «разделяй и властвуй» позволяет уменьшить асимптотическую сложность алгоритма.

Реализация алгоритма наC++


 \beginverbatimint gcd (int a, int b) return b ? gcd(b, a\endverbatim