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

Имеется викиучебник по теме
«Алгоритм Евклида»

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

Содержание

1 История
2 Алгоритм Евклида для целых чисел
3 Пример
4 Расширенный алгоритм Евклида и соотношение Безу
- 4.1 Связь с цепными дробями
5 Вариации и обобщения
- 5.1 Обобщённый алгоритм Евклида для многочленов
- 5.2 Ускоренные версии алгоритма
6 См. также
7 Литература

История

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

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

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

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

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

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

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

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

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

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

Доказательство

Пусть k — любой общий делитель чисел a и b, не обязательно наибольший, тогда ; где и — целые числа из определения.
Тогда k является также общим делителем чисел b и r, так как b делится на k по определению, а (выражение в скобках есть целое число, следовательно, k делит r без остатка)
Обратное также верно и доказывается аналогично пункту 2: любой делитель b и r так же является делителем a и b.
Следовательно, все общие делители пар чисел (a, b) и (b, r) совпадают. Другими словами, нет общего делителя у чисел (a, b), который не был бы также делителем (b, r), и наоборот.
В частности, наибольший общий делитель остается тем же самым. Что и требовалось доказать.

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

Проще сформулировать алгоритм Евклида так: если даны натуральные числа и и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.

Пример

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

1071 = 2 × 462 + 147.

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

462 = 3 × 147 + 21.

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

147 = 7 × 21 + 0.

Таким образом последовательность a>b>R1>R2>R3>R4>...>Rn в данном конкретном случае будет выглядеть так:

1071>462>147>21

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

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

Шаг k	Равенство	Частное и остаток
0	1071 = q₀ 462 + r₀	q₀ = 2 и r₀ = 147
1	462 = q₁ 147 + r₁	q₁ = 3 и r₁ = 21
2	147 = q₂ 21 + r₂	q₂ = 7 и r₂ = 0; алгоритм заканчивается

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

Основная статья: Соотношение Безу

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

НОД

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

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

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

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

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

$\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}$

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

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

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

В приведённом выше примере, НОД(1071, 462) было посчитано и были найдены частные q_k 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]. Для многочленов над целыми числами верно следующее:

НОДНОД, НОДНОД.

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

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

Под псевдоделением будем понимать, что самому делению предшествует умножение полинома p1(x) на , то есть , , где и — соответственно псевдочастное и псевдоостаток.

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

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

НОД.

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

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

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

Если , то вернуть , иначе вернуть .

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

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

где

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

См. также

Литература

Имеется викиучебник по теме
«Примеры реализации алгоритма Евклида»

Виноградов И. М. Основы теории чисел.
Курант Р., Роббинс Г. Дополнение к главе 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
Панкратьев Е. В. Наибольший общий делитель и последовательности полиномиальных остатков // intuit.ru.
Обоснование алгоритма Евклида
Алгоритм Евклида на e-maxx.ru
C# реализация расширенного алгоритма Эвклида

Sud-mal.ru

МОУ СОШ

Новости