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

Алгори́тм Евкли́да, алгоритм для нахождения наибольшего общего делителя двух целых чисел.

Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

Историками математики (Цейтен и др.) было выдвинуто предположение, что именно с помощью А.Е. (процедуры последовательного взаимного вычитания) в древнегреческой математике впервые было открыто существование несоизмеримых величин (стороны и диагонали квадрата, или стороны и диагонали правильного пятиугольника). Впрочем, это предположение не имеет достаточных документальных подтверждений. Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в I книге древнекитайского трактата Математика в девяти книгах.

Ряд математиков средневекового Востока (Сабит ибн Курра, ал-Махани, Ибн ал-Хайсам, Омар Хайям) попытались построить на основе А.Е. теорию отношений, альтернативную по отношению теории отношений Евдокса, изложенной в V книге «Начал» Евклида. Согласно определению, предложенному этими авторами, четыре величины, первая ко второй и третья к четвёртой, имеют между собой одно и то же отношение, если при последовательном взаимном вычитании второй величины в обеих парах на каждом шаге будут получаться одни и те же неполные частные.

А.Е. для целых чисел:

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

определена тем, что каждое rk — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

a = bq0 + r1

b = r1q1 + r2

r1 = r2q2 + r3

rk − 2 = rk − 1qk − 1 + rk

rn − 1 = rnqn

Тогда НОД(a,b), наибольший общий делитель a и b, равен rn, последнему ненулевому члену этой последовательности.

Существование таких r1,r2,..., то есть возможность деления с остатком m на n для любого целого m и целого , доказывается индукцией по m.

Корректность этого алгоритма вытекает из следующих двух утверждений:

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

• НОД(0,r) = r для любого ненулевого r.

Проще сформулировать алгоритм Евклида так: если даны натуральные числа 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>b>R1>R2>R3>R4>...>Rn в данном конкретном случае будет выглядеть так:

1071>462>147>21

Так как последний остаток равен нулю, алгоритм заканчивается числом 21 и НОД(1071, 462)=21.

В табличной форме, шаги были следующие

Шаг k	Равенство	Частное и остаток
0	1071 = q0 462 + r0	q0 = 2 и r0 = 147
1	462 = q1 147 + r1	q1 = 3 и r1 = 21
2	147 = q2 21 + r2	q2 = 7 и r2 = 0; алгоритм заканчивается

Расширенный А.Е. и соотношение Безу:

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

r1 = a + b( − q0)

r2 = b − r1q1 = a( − q1) + b(1 + q1q0)

НОД (a,b) = rn = as + bt

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

Отношение a / b допускает представление в виде цепной дроби:

.

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

.

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

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

Третье равенство может быть использовано чтобы заменить знаменатель выражения r1/r0, получим

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

В приведённом выше примере, НОД(1071, 462) было посчитано и были найдены частные qk 2,3 и 7 соответственно. Поэтому, 1071/462 может быть записана как

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

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

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

Пример для кольца Z[x]

Пусть cont(f) по определению — НОД коэффициентов многочлена f(x) из Z[x] — содержание многочлена. Частное от деления f(x) на cont(f) называется примитивной частью многочлена f(x) и обозначается primpart(f(x)).

эти определения понадобятся для нахождения НОД двух многочленов p1(x) и p2(x) в кольце Z[x]. Для многочленов над целыми числами верно следующее:

cont(НОД{p1(x),p2(x)}) = НОД{cont(p1(x)),con(p2(x))}, primpart(НОД{p1(x),p2(x)}) = НОД{primpart(p1(x)),primpart(p2(x))}.

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

Пусть есть два примитивных многочлена p1(x) и p2(x) из Z[x], для которых выполняется соотношение между их степенями: deg(p1(x)) = m и deg(p2(x)) = n, m > n. Деление многочленов с остатком предполагает точную делимость старшего коэффициента делимого на старший коэффициент делителя, в общем случае деление с остатком выполнить невозможно. Поэтому вводят алгоритм псевдоделения, который всё же позволяет получить псевдочастное и псевдоостаток (prem), которые будут сами по себе принадлежать множеству многочленов над целыми числами.

Под псевдоделением будем понимать, что самому делению предшествует умножение полинома p1(x) на (lc(p2(x)))m − n + 1, то есть lc(p2(x))m − n + 1p1(x) = p2(x)q(x) + r2(x), deg(r(x)) < deg(p2(x)), где q(x) и r(x) — соответственно псевдочастное и псевдоостаток.

Итак,  — (принадлежат кольцу многочленов над целыми числами), причём . Тогда алгоритм Евклида состоит из следующих шагов:

1. Вычисление НОД содержаний:

c: = НОД{cont(p1),cont(p2)}.

2. Вычисление примитивных частей:

p1'(x): = cont(p1(x)); p2'(x): = cont(p2(x)).

3. Построение последовательности полиномиальных остатков:

p1'(x),

p2'(x),

p3(x): = prem(p1'(x),p2'(x)),

p4(x): = prem(p2'(x),p3(x)),

p5(x): = prem(p3(x),p4(x)),

...,

ph(x): = prem(ph − 2(x),ph − 1(x)).

4. Выход и возврат результата:

Если deg(ph(x)) = 0, то вернуть c, иначе вернуть .

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

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

где

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

Лит.: Виноградов И. М. Основы теории чисел. Курант Р., Роббинс Г. Дополнение к главе I, § 4. // Что такое математика? — 3-e изд., испр. и доп.. — М., 2001. — 568 с. Абрамов С. Самый знаменитый алгоритм // Квант. — 1985. — № 11. — С. 44—46. Щетников А. И. Алгоритм Евклида и непрерывные дроби — Новосибирск: АНТ, 2003. Fowler D. H. The Mathematics of Plato’s Academy: a new reconstruction — 2nd. — Clarendon Press, 1999. von zur Gathen J., Gerhard J. Modern Computer Algebra. — ISBN 0-521-82646-2.

АЛГОРИТМ ЭВКЛИДА — способ нахождения наибольшего общего делителя. Был предложен сна­чала в геометрической форме для нахождения наи­большей общей меры двух отрезков, или, вообще, двух геометрических величин. В этой форме он име­ется в «Началах» Эвклида,Тот же, по существу, алгоритм применяется для нахождения наиболь­шего общего делителя двух целых чисел или наи­большего общего делителя двух многочленов.

Только в современной алгебре эти разновидности А. Э. были отчётливо восприняты как частные слу­чаи одной общей теории. Чтобы охватить А. Э. для геометрических величин, общую теорию надо строить ири ещё более широких пред­посылках, чем это делается в теории Эвклидовых колец; в статье «Кольцо алгебраическое» пояс­няется самый принцип объединения различных случаев А. Э. в одну общую теорию.

1. Пусть даны два отрезка а и Ъ. Они называются соизмеримыми, если существует такой от­резок с, который укладывается какое-либо целое число п раз в отрезке а и какое-либо целое число т раз в отрезке Ь. Любой такой отрезок с называется общей мерой отрезков а и Ъ. Если у отрезков а и Ь общей меры нет, то они называются несоизме­римыми. Среди общих мер двух отрезков а и Ъ всегда существует наибольшая общая мера с0; любая другая общая мера тех же отрезков укладывается в наибольшей мере нек-рое целое число раз. Наир., наибольшей общей мерой отрезков длины 1.000 м и 375 м является отрезок длины 125 м, укладывающийся в первом восемь раз, а во втором — три раза. Отрезки в 5 м или 1 м тоже будут общими мерами указанных отрез­ков, но уже не наибольшими.

А. Э. позволяет найти для любых двух соизмери­мых отрезков именно их наибольшую общую ме­ру. Состоит он в следующем. Если отрезки а и Ъ равны, то любой из них может быть принят за отрезок с0. Если отрезки не равны, то нусть а обозначает больший отрезок, а Ь — меньший. В таком случае откладывают вдоль по отрезку а, на­чиная, скажем, от лево­"'—'—'—'—'—' ' ' ' го его конца (рис. 1), til,, отрезок Ъ столько раз,

_^Ьг^ сколько он уложится.

a-2b+b'-' 1 ■ Если ири этом не ио-

ь=ь1+ь,,-лучается никакого ос-

Рис. 1. татка, то отрезок Ъ и ь,=гь2. I I является наибольшей

обшей мерой (сам в себе он укладывается один раз). Если остаётся нек-рый остаточный отрезок bt (который, очевидно, должен быть короче Ь), то он откладывается вдоль отрезка Ь столько раз, сколько он уложится. Если ири этом не получается остатка, то Ь, и есть наибольшая общая мера с0. В случае, когда вновь получается остаточный отрезок Ь2, он откладывается вдоль отрезка Ь,, и т. д. Если отрезки а и Ь соизмеримы, то процесс этот непре­менно кончится на каком-то шаге с номером к тем, что отрезок Ък уложится целое число раз в отрезке Ьк_, (на рис. 1 это случается при к=2). Отрезок Ьк и есть в этом случае общая наибольшая мера от­резков а и Ь.

А. Э. употребляется не только для нахождения общей меры двух отрезков, но и для доказательства существования среди общих мер наиболь­шей, а также для доказательства того, что любая другая их общая мера содержится нек-рое целое число раз в наибольшей. Это теоретическое назна­чение А. Э. в геометрии является основным, так как в конкретной измерительной практике указан­ный сиособ нахождения наибольшей общей меры отрезков мог бы найти лишь очень ограниченное применение.

2. Пусть а и Ь — два положительных целых числа, причём а^Ъ. Деление (см.) с остатком чис­ла а на число Ь всегда приводит к результату а=пЪ-1гЪ1, rge (неполное) частное п является положительньш целым числом, а остаток 6j — либо О, либо положительное целое число, меньшее Ь: OsSbx < Ь.

Будем цронзводить последовательное деление: а= пЪ-\-Ъг,

Ъ =nxbi+ Ь2. О bi = пф2-\-Ъ3,

(где вс5 время щ—положительные целые числа и 0^4<6i_1), до тех иор, иока не получится остаток, равный нулю. Этот равный нулю остаток Ьк+1 можно не писать, так что ряд равенств (1) закончится так:

bk~i = »fe-i6fe-i + 6fc> bk_1 = nlebk.

В курсах арифметики доказывается, что последний положительный остаток Ьк в этом процессе и являет­ся наибольшим общим делителем чисел а и Ъ. При этом А. Э. служит не только для нахождения общего наибольшего делителя, но и для доказательства самого его существования.

3. Пусть теперь А(х) и В(х) — два многочлена. Если степень многочлена А(х) не меньше степени многочлена В{х), то рассматриваемое во всех эле­ментарных учебниках алгебры действие «деления с остатком» заключается в том, что находится многочлен «частное» N(x) и многочлен «остаток» Вх (х), обладающие тем свойством, что

A(x) = N(x)B(x)-\-B1 (х), причём степень остатка Вх(х) меньше степени В(х), Процесс последовательного деления,

A[x) = N{x)B(x)-\-B1 (х), B{x) = N1 (х)В1(х) + Вг(х),

Bfc-i (х) = Ifu-i (*) Bfc-i (*) +Вк (х),

Bfc_! (x) = Nk (х) Вк [х), в случае многочленов всегда кончается получением остатка Вк+1 (х) (не написанного у нас), равного нулю. Последний отличный от нуля остаток Вк(х) и есть наибольший общий делитель многочленов А(х) и В(х).

А. Э. для отрезков (см. раздел 1) может оказаться и бесконечным. Это будет в том (и только в том) случае, если взятые отрезки а и Ь несоизмеримы. Та­ков, наир., случай диагона- N. ли и стороны квадрата. На >. рис. 2 изображён квадрат N. (ABCD) с диагональю ЛС=а N. и стороной DC=6. Мы строим \^ ,

отрезок AD'-—AD=b, а на <!^\ отрезке D'C-=bx — квадрат *\ (A'B'CD'). На диагонали | / \ \J

меньшего квадрата отклады- 0 л'Ч. и''/°

ваем A'D" = A'D' = 6,. Лег- \ /

ко доказать, что углы, от- Рис. 2. N/ меченные на рисунке двумя

дужками, равны - прямого угла. Поэтому DA'= ~А'Т>'=ЪХ. Первые шаги А. Э. в рассматриваемом случае будут таковы:

а — AC=AD'+D'C = b-j-bu b = DC = DA'-j- A'D" 4- D"C — 2bt + 62.

В силу подобия фигур (ABCDD') и (A'B'CD'D"), , при откладывании отрезка D"C=b3 вдоль отрезка D'C=bl повторится точно та же картина, какая наблюдалась при откладывании отрезка D'C=bl вдоль отрезка DC=b. Поэтому, дальнейшие шаги А. Э. будут таковы:

bj = 26,4-6,,

и т. д., до бесконечности. Именно на этом пути гре­ческие математики впервые открыли существование несоизмеримых отрезков.

Так как отношение диагонали квадрата и стороне равно Vl, то приведённое геометрическое доказа­тельство несоизмеримости диагонали и стороны квадрата вместе с тем нвлнетсн и доказательством иррациональности числа "^2. О применении А. Э. к вопросам, связанным с иррациональными числами. Здесь мы ограничимся лить указанием, что, в силу сказанного выше, Y% разлагается в бесконечную непрерывную дробь сле­дующего вида:

V2=l + 1-

~ 2 f 1_

2 + 1_

2-г

Лит.: А. Э. в геометрии — см.: Киселев А., Геометрия, 9 изд., М., 1948; А. Э. в арифметике и алгебре—Марку шевич А. И., Деление с остат­ком в арифметике и алгебре, М.—Л., 1949; А. Э. с точки зрения теории колец — Ва и-д е р-В а р-ден Б. Л., Современная алгебра, пер. с нем.,ч. 1—2, [2 изд.]. М.-Л., 1947.