Что нужно знать об алгоритме Евклида — основные сведения

Алгоритм Евклида для нахождения НОД

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

Так выглядел Евклид:

Базовый вариант использования алгоритма Евклида — использовать его на двух положительных целых числах. В результате вычислений создается новейшая диада, состоящая из самого маленького числа и разности большого и маленького чисел. Вычисления воспроизводятся снова и снова до момента, пока цифры не приобретут равность. Число, которое было найдено в результате, считается самым большим общим делителем первоначальной диады.

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

Наибольший общий делитель: понятие, свойства

Свойства наибольшего общего делителя

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

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

Данное свойство не нужно доказывать, потому что оно вытекает из дефиниции термина «наибольший общий делитель».

Доказательство для второго свойства. Каждый общий делитель диады a и b считается делителем для любого из данных типов чисел, включая число b. Из-за того, что число можно поделить без остатка на b, тогда каждый делитель для величины b можно считать делителем для величины a. Получается, что каждый делитель значения b можно считать общим делителем диады a и b.

Таким образом, в случае, когда a возможно поделить на b, то общность делителей диады a и b эквивалентна общности делителей одной величины b. Из-за того, что самый большой делитель величины b — непосредственно значение b, тогда наибольший общий делитель величины b = b. Так, НОД (a, b) = b. В особенности, в случае, когда a=b, тогда НОД (a, b) = НОД (a, a) = a = b. К примеру, НОД (25, 25) = 25.

Свойство, которое было доказано, возможно применять для нахождения значения НОД для двух чисел, в случае, когда одно может поделиться на другое. Так НОД эквивалентен одному из данных чисел, на которое можно поделить иное число. К примеру, НОД (4, 40) = 4, потому что 40 делится без остатка на 4.

Доказательство для третьего свойства. Есть в математике уравнение a = bq + c, оно означает, что любой общий делитель диады a и b может поделить и значение c, из-за свойств делимости. Из-за этого и любой общий делитель диады b и c разделяет a. Из-за этого общность общих делителей диады a и b эквивалентны общности общих делителей величин b и c. Из-за этого обязаны соблюдаться условия равенства самых больших значений общих делителей. Получается, что НОД (a, b) = НОД(b, c) является справедливым.

История алгоритма Евклида

В Древней Греции ученые давали название данному алгоритму как «взаимное вычитание». По ошибке все считают, что алгоритм изобрел Евклид, но это не так. На самом деле он был описан еще в Топике пера Аристотеля, задолго до Евклида. В работе «Начала» Евклида дается описание алгоритма два раза — в седьмой книге описан процесс нахождения НОД двух натуральных чисел, а в десятой книге описан процесс нахождения самой большой совокупной мерой двух одинаковых величин. Оба вида описываются геометрически.

Математические историки предположили, что при помощи алгоритма Евклида математики в Древней Греции смогли открыть наличие несоизмеримых величин. Но, к сожалению, никаких доказательств этому факту нет. Подобный алгоритму Евклида алгоритм описывается в книге о математике периода Древнего Китая.

Алгоритм Евклида для вычисления наибольшего общего делителя

Алгоритм Евклида помогает рассчитать НОД для диады положительных чисел. Сущность алгоритма состоит в постепенном делении с учетом остатка. В итоге алгоритма должно быть выведено равенство типа:

\(a=b\times{q_{1}}+r_{1}, 0<r_{1}<b\)

\(b=r_{1}\times{q_{2}}+r_{2}, 0<r_{2}<r_{1}\)

\(r_{1}=r_{2}\times{q_{3}}+r_{3}, 0<r_{3}<r_{2}\)

\(r_{2}=r_{3}\times{q_{4}}+r_{4}, 0<r_{4}<r_{3}\)

\(r_{k-2}=r_{k-1}\times{q_{k}}+r_{k}, 0<r_{k}<r_{k-1}\)

\(r_{k-1}=r_{k}\times{q_{k+1}}.\)

Нахождение НОД отрицательных чисел

В случае, когда одно\некоторое количество или же все значения, НОД которых необходимо вычислить, являются отрицательными, тогда НОД таких чисел равняет самому большому общему делителю модуля данных значений. Это можно объяснить тем, что противопоставленные числа a и -a обладают равными делителями.

Алгоритм Евклида «с вычитанием»

Алгоритм «с вычитанием» выглядит таким образом:

1. Производим вычитание меньшего из большего числа.
2. В случае, когда итог — ноль, тогда числа эквиваленты, а, значит, их можно считать НОД — цикл заканчивается.
3. В случае, когда итоге — не ноль, тогда заменяется большее число при помощи итога вычитания.
4. Производим снова первый шаг.

НОД: расширенный алгоритм Евклида

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

Расширенный алгоритм Евклида часто применяется в случаях, при которых a и b являются взаимно простыми. В таком случае x считается модульным обратным значения a по линии модуля b. В это же время y считается модульным обратным значения b по линии модуля a. Расширенный алгоритм Евклида для многочленов помогает рассчитать обратное число в математических расширениях, в том числе в конечных полях непростого порядка. Данный тип алгоритма активно применяют в области криптографии.

Простой алгоритм Евклида направлен на нахождение НОД диады a и b, в то время как расширенный алгоритм Евклида ищет значения показателей x и y. Получается, что: \(a\times{x}+b\times{y}=gcd(a,b)\). Расширенный алгоритм занимается поиском показателей, при помощи которых НОД диады может выражаться посредством данных чисел.

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

Представим, что было найдено решение \((x_{1}, y_{1})\) для диады (b@a, a):

\((b@a,a)\times{x_{1}}+a\times_{y_{1}}=g\), нужно решить (x, y) для диады \((a, b): a\times{x}+b\times{y}=g\). Произведем трансформацию значения \(b@a: b@a=b-\left[\frac{b}{a}\right]\times{a}\). Теперь нужно подставить данное значение в верхнее уравнение с показателями \(x_{1}, y_{1}\), тогда получится: \(g=(b@a)\times{x_{1}}+a\times{y_{1}}=(b-\left[\frac{b}{a}\right]\times{a})\times{x_{1}}+a\times{y_{1}}\), трансформируем уравнение: \(g=b\times{x_{1}}+a\times(y_{1}-\left[\frac{b}{a}\right]\times{x_{1}})\).

Произведем сравнение с первоначальным уравнением, получится: \(\begin{cases}x=y_{1}-\left[\frac{b}{a}\right]\times{x_{1}}\\y=x_{1}\end{cases}\).

Расширенный алгоритм Евклида реализуется правильно даже в случае работы с отрицательными числами.

Сложность алгоритма Евклида

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

Ученым Эмилем Леже в середине 19 века был исследован худший вариант, при котором для нахождения НОД дают постепенные числа Фибоначчи. Потом, также в середине 19 века, ученым Пьером Финком было указано, что число ходов алгоритма — не более \( 2\log_{2}{v+1}\). Это значит, что алгоритм может совершать работу за полиномиальное время от величины меньшего из диады u и v. Исследование ученого Финка дополнил ученый Габриэль Ламе через три года после Финка. Им было исследовано, что число ходов, которые нужны для окончания расчетов, не превышает в пять раз h-число чисел в десятичном виде меньшего из диады u, v.

В случае, когда наибольший общий делитель входит в одно машинное слово, каждый ход алгоритма забирает постоянное количество времени. В случае исследования Ламе получается, что вычислительная сложность — O(h). Но в расчетной модели оценка сложности расчетов единого остатка способна принимать вид \(O(h^{2})\). При таком условии суммарное время всех шагов алгоритма возможно проанализировать при помощи телескопического спектра, указав, что \(O(h^{2})\).

Сделаем предположение, что \(s = НОД (f, g)\), тогда можно применить введение в уравнение показателей m и n: \(f=m\times{s}\)  и \(g=n\times{s}\). В данном варианте \(W(f,g) = W (m,n)\) выражение возможно поделить на s. Количество ходов считается перманентным значением в процессе умножения f и g на коэффициент L. Таким образом \(W(f,g)=W(L\times{m}, L\times{n})\). Значит, что переменная, которую мы рассчитываем, находится в зависимости от НОД.

В случае, при котором для расчета, согласно алгоритму, нужно n ходов для значений f>0, g>0, обязано исполняться подобное неравенства с числами Фибоначчи \(F_{n}+2\) и \(F_{n}+1\). Получается, что \(f> =F_{n}+2\) и \(g> =F_{n}+2\). Можно доказать это выражение с помощью индукции в математике. Предположим, что n=1, тогда остаток соотношения \(\frac{f}{g}\) будет равен нулю. Самой маленькой величиной считаются \(f=2, g=1 (F_{2}\) и \(F_{3})\).

Сделаем предположение, что итог для величин на отрезке от n до m будет 1. Первым ходом с m ходами будет записываться \(f=Q_{0}\times{g}+R_{0}\). Значит, что исполнение алгоритма для величин g и \(R_{0} (g> R_{0})\) утверждает (m-1) ходов.

В итоге всех действий выводятся два нестрогих уравнения \(g>F_{m}+1 \)и \(R_{0}>F_{m}\). Из данного неравенства получается, что \(f=Q_{0}\times{g}+R_{0}>=g+R_{0}>=F_{m}+1+F_{m}=F_{m}+2.\)

Значимость алгоритма Евклида

Алгоритм Евклида также служит базой для теоретического доказательства теории чисел. Например, его используют для доказательства теории Лагранжа или же базовой теоремы арифметики.

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

Использование в рамках математики

Один из вариантом использования алгоритма Евклида можно считать соотношение Безу (тождество или Леме). Сущность соотношения Безу состоит в показе наибольшего общего делителя в виде линейной сочетания с определенными значениями целого вида. Существует такая дефиниция: в случае целых чисел f и g (одно из чисел не должно быть эквивалентно нулю) бывают определенные показатели целого вида, для которых будет объективным отношение \(НОД (f,g) = m\times{f}+n\times{g}\), при котором m и n являются показателями Безу.   

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

Примеры решения задач с алгоритмом Евклида

Представляем решение данного уравнения методом «столбика»:

Для того, чтобы найти НОД трех (и более) чисел, используем такой алгоритм:

1. Необходимо найти НОД любых двух значений.
2. Необходимо найти НОД итогового делителя из первого пункта и третьего значения.
3. Необходимо найти НОД итогового делителя и четвертого значения, так до последнего делителя.