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

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

История

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

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

Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в I книге древнекитайского трактата Математика в девяти книгах.

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

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

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

$r_{1}=a+b(-q_{0})$

$r_{2}=b-r_{1}q_{1}=a(-q_{1})+b(1+q_{1}q_{0})$

$\cdots$

$\gcd(a,b)=r_{n}=as+bt$

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

Связь с цепными дробями

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

${\frac {a}{b}}=[q_{0};q_{1},q_{2},\cdots ,q_{n}]$.

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

$[q_{0};q_{1},q_{2},\cdots ,q_{n-1}]=-{\frac {t}{s}}$.

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

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

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

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

$r_{i}\equiv r_{i-2}{\pmod {r_{i-1}}},$

где

$-{\frac {r_{i-1}}{2}}\leq r_{i}\leq {\frac {r_{i-1}}{2}}.$

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

См. также

• Примеры реализации алгоритма Евклида
• Евклидово кольцо
• Непрерывная дробь
• Обоснование Алгоритма Евклида.

Литература

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

ar:خوارزمية إقليدس bg:Алгоритъм на Евклид ca:Algorisme d'Euclides cs:Euklidův algoritmus el:Αλγόριθμος του Ευκλείδη Шаблон:Link FA eo:Eŭklida algoritmo hu:Euklideszi algoritmus id:Algoritma Euklidean lt:Euklido algoritmas lv:Eiklīda algoritms mn:Евклидийн алгоритм nds:Euklidsch Algorithmus nl:Algoritme van Euclides no:Euklids algoritme pl:Algorytm Euklidesa simple:Euclidean algorithm sl:Evklidov algoritem sr:Еуклидов алгоритам sv:Euklides algoritm uk:Алгоритм Евкліда vi:Giải thuật Euclid