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

Алгоритм Евклида — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков). Алгоритм назван в честь греческого математика Евклида, который впервые описал его в 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 \textgreater r1 \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++


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