Алгоритм Евклида - формулы, правила и примеры решения задач

Общие сведения

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

Суть алгоритма заключается в формировании новой пары чисел из меньшего и разницы между большим и меньшим элементом. Процесс, состоящий из арифметических операций, повторяется до тех пор, пока числа не будут равны друг другу. Первоначально инструкция создавалась для натуральных чисел и геометрических величин. Однако в XIX веке ее расширили и стали применять для других объектов: целых чисел Гаусса и многочленов с одной переменной (полиномов). Направление, получившееся в математике, специалисты стали называть евклидовым кольцом. Позднее его доработали и стали применять для узлов и многомерных полиномов.

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

Описание и доказательство алгоритма

Для целых чисел алгоритм состоит из соотношений, количество которых равно числу элементов. Если предположить, что а и b являются целыми и неравными нулю значениями, то для них выполняется соотношение a > b > R1 > … > Rn. Величинами R с определенными индексами являются остатки от деления а на некоторое значение Q1 и b на Q2. Описывается процесс такими формулами:

1. а = b * q0 + R1.
2. b = R1 * q1 + R2.
3. R1 = R2 * Q2 + R3.
4. Rn-1 = Rn * Qn.

На последнем этапе не должно быть остатка. Для отрезков применяется геометрический алгоритм. Чтобы найти наибольший общий отрезок, нужно из большего вычесть меньший, а затем заменить первый их разностью. Операцию следует завершить при равенстве двух отрезков. Реализуется данный алгоритм при помощи циркуля и линейки. Для доказательства алгоритма Евклида следует взять пару чисел f и g, для которых можно привести такие утверждения:

1. Делители f и g — общие делители (f — g) и g.
2. Делители (f — g) и g — общие делители f и g.
3. Когда f > g, тогда НОД (f, g) = НОД (f — g, g).
4. НОД (f, 0) = f.

Для доказательства следует ввести новую переменную z. Она является общим делителем для f и g. Кроме того, разность f — g также делится на z. Из предположения f = z * k и g = z * s следует, что f — g = z * k — z * s = z * (k — s). Иными словами, z — общий множитель для f — g. Из соотношения можно доказать, что z делит не только разность, но и сумму: f — g + g = f. Следовательно, z — общий делитель для f и g.

На основании полученных вычислений можно сделать вывод, что z для f и g совпадает с (f — g) и g. Если одно из чисел имеет нулевое значение, то НОД равен другому числу, поскольку 0 делится на любое число.

Следует отметить, что методика для нескольких чисел (трех и более) аналогичная. В этом случае нужно брать не одну разность, а две, в которой будет присутствовать минимальное число. Данный алгоритм применяется в построении программного обеспечения. Однако перед написанием кода следует сначала составить блок-схему. Она позволит избежать ошибок, а также внимательно сосредоточиться на проекте.

Применение в математике

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

Тождество справедливо и для натуральных чисел. У него такая же формулировка, только слово «целых» заменяется на «натуральных». Кроме того, существует расширенный алгоритм Евклида:

1. R1 = f + g * (-Q0).
2. R2 = g — R1 * Q1 = f * (-Q1) + g * (1 + Q1 * Q0).
3. Для целых w и z: НОД (f, g) = Rn = f * w + g * z.

Еще одним примером использования алгоритма считаются цепные дроби. Пусть f и g — числитель и знаменатель соответственно. Любая дробь такого типа может быть представлена следующим образом: f / g = [Q0;Q1,Q2,…, Qn]. Без Qn она равна отношению коэффициентов Безу w / z, результат которого нужно брать с отрицательным знаком, т. е. [Q0;Q1,Q2,…, Qn-1] = - w / z. Следовательно, равенства могут иметь такое представление:

1. f / g = Q0 + R0 / b.
2. b / R0 = Q1 + R1 / R0.
3. R0 / R1 = Q2 + R2 / R1.
4. (Rn-2) / (Rn-1) = Qn.

Если обратить внимание, то можно понять закономерность: последний элемент правой части равен обратной величине левой части последующего тождества. В результате этого можно объединить две формулы: f / g = Q0 + 1 / [Q1 + (R1/R0)]. Третья применяется для замены знаменателя: f / g = Q0 + 1 / [Q1 + (1 / (Q2 + (R2/R1)))]. Следовательно, можно записать цепную дробь в таком виде: f / g = Q0 + 1 / [Q1 + (1 / (Q2 + … + 1 / Qn))].

Алгоритм применяется и для решения диофантовых уравнений. Диофантовым является уравнение с целыми коэффициентами и одной или несколькими переменными, решение которого сводится к нахождению только целых корней. Решений у него может быть много. Примером простейшего считается обыкновенное линейное с двумя переменными Ах + Ву = С, где А и В — некоторые коэффициенты. Переменными величинами являются х и у. Решается оно следующим образом:

• Находится коэффициент D: D = НОД (А, В).
• При помощи расширенного алгоритма Евклида следует найти некоторые коэффициенты w, z: А * w + B * z = D.
• Получаются такие соотношения (x = w, y = z) при D = С: С = Q * D, х = Q * w и y = Q * z.
• Частное решение: Ах + Ву = А * (Q * w) + B * (Q * z) = Q * (A * w + B * z) = Q * D = C.

Если у уравнения всего один корень, то C кратно D. Данное утверждение следует из соотношения, в котором D делит А, В и всю левую сторону, а значит, должно делить правую на С.

Различные вариации

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

Для многочлена вида Z[g] от одной неизвестной g над некоторым полем (функцией) Z определена операция деления. Последняя выполняется только с остатком. Если применить к нему правило Евклида, то получится последовательность остатков в виде полиномов. Для примера следует разобрать такую задачу: пусть cont (w) является НОД для коэффициентов f (w) из полинома Z[g]. При делении f (w) на cont (w) образуется примитивная часть многочлена primpart (f (w)). Необходимо найти НОД Р1 (g) и Р2 (g). Если числа являются целыми, то в этом случае верны такие тождества:

1. сont (НОД {Р1 (g), Р2 (g)}) = НОД{сont (Р1 (g)), сont (Р2 (g))}.
2. primpart (НОД {Р1 (g), Р2 (g)}) = НОД{primpart (Р1 (g)), primpart (Р2 (g))}.

Следовательно, поиск НОД для двух многочленов нужно свести к поиску НОД примитивных полиномов. Для примитивных полиномов Р1 (g) и Р2 (g), принадлежащих Z[g], выполняется такое соотношение между их степенями: deg (Р1 (g)) = m и deg (Р2 (g)) = n (m > n). Деление с остатком осуществляется по псевдоделимости, поскольку иногда выполнить первую процедуру невозможно.

В результате этого вводят специальный алгоритм для псевдоделения, результатом которого является псевдоостаток. Его обозначают «prem». Формула операции псевдоделения имеет такой вид с учетом псевдочастного Q (g) и псевдоостатка R (g): [lc (P2 (g))^(m-n+1)] * P1 (g) = P2 (g) * Q (g) + R2 (g) при deg (R (g)) < deg (P2 (g)). Следовательно, P1 (g) и P2 (g) принадлежат Z[g] при условии, что deg (P1) = n1 >= deg (P2) = n2. На основании полученных результатов лема Евклида состоит из таких пунктов:

1. Найти НОД: НОД{сont (Р1 (g)), сont (Р2 (g))}.
2. Расчет примитивных частей: [P1 (g)]' = primpart (P1 (g)) и [P2 (g)]' = primpart (P2 (g)).
3. Последовательность псевдоостатков полиномного типа: [P1 (g)]', [P2 (g)]', [P3 (g)]' = prem ([P1 (g)]', [P2 (g)]'), [P4 (g)]' = prem ([P2 (g)]', [P3 (g)]'),…, [Pn (g)]' = prem ([(Pn-2)(g)]', [(Pn-1)(g)]').
4. Возвратить результат: если deg (Pn (g)) = 0, то вернуть НОД{сont (Р1 (g)), сont (Р2 (g))}. Иначе — выражение в первом пункте нужно умножить на primpart (Pn (g)).

Существует еще одна разновидность алгоритма. Она называется ускоренной. Ее суть заключается в применении понятия симметричного остатка: Ri = Ri-2 * (mod [Ri-1]). Для данного выражения должно выполняться такое условие: -[Ri-1 / 2] <= Ri <= [Ri-1 / 2].

Вычислительная сложность

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

Во время вычислительного процесса значение НОД записывается только в одно машинное слово. Алгоритм состоит из совокупности определенных шагов, каждый из которых занимает равные отрезки времени. Следовательно, они являются постоянными величинами. Количество шагов для расчета НОД (f, g) следует обозначить W (f, g).

Предположив, что s = НОД (f, g), можно воспользоваться введением некоторых целых коэффициентов m и n: f = m * s и g = n * s. В этом случае W (f, g) = W (m, n) уравнение можно разделить на s. Число шагов является постоянной величиной при умножении f и g на множитель L, т. е. W (f, g) = W (L * m, L * n). Следовательно, искомая переменная зависит от НОД.

Когда для вычисления по алгоритму требуется N шагов для чисел f > 0 и g > 0, должно выполняться такое неравенство с числами Фибоначчи Fn+2 и Fn+1 соответственно: f >= Fn+2 и g >= Fn+1. Доказывается данное утверждение при помощи математической индукции. Если предположить, что N = 1, то остаток отношения f / g эквивалентен 0.

Наименьшими значениями являются f = 2 и g = 1 (F2 и F3 соответственно). Предположим, что результат для значений на промежутке от N до М — 1. Первый шаг c M шагами записывается таким образом: f = Q0 * g + R0. Следовательно, выполнение алгоритма для чисел g и R0 (g > R0) требует (М — 1) шагов.

В результате этого получаются два нестрогих неравенства g >= Fm+1 и R0 >= Fm. Из выражения следует, что f = Q0 * g + R0 >= g + R0 >=Fm+1 + Fm = Fm+2. Данное доказательство было выполнено в 1844 году математиком Г. Ламе. Оно является главным элементом теории сложности вычислений. Формулировка данного утверждения следующая: при нахождении НОД f и g в результате деления с некоторым остатком число операций по алгоритму Евклида не превосходит 5.

Пример решения

Специалисты рекомендуют закрепить теоретические знания решением различных упражнений. Необходимо разобрать применение алгоритма на примере нахождения НОД (1071,462). Для этого следует действовать по такой инструкции, позволяющей решить простым способом задачу:

• Выполнить операцию разности до получения остатка: 1071 — 462 — 462 + 147 = 1071 — 2 * 462 + 147 (Q0 = 2, R0 = 147).
• От 462 отнять 147 до получения результата, который меньше 147: 462 — 147 — 147 — 147 + 21 = 462 — 3 * 147 + 21 (Q1 = 3, R1 = 21).
• Анализ пары чисел 147 и 21: 147 — 21 — 21 — 21 — 21 — 21 — 21 — 21 + 0 (Q2 = 7, R2 = 0).
• Определение результата: НОД (1071,462) = 21.

На третьем шаге алгоритм заканчивается, поскольку остаток отсутствует, т. е. R2 = 0. В написании программ применяется такой же принцип. Если даны три числа, то методика решения усложняется. Для этой цели применяется специальный онлайн-калькулятор.

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