Как найти нод двух чисел алгоритм евклида

Как найти нод двух чисел алгоритм евклида

Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков). Алгоритм назван в честь греческого математика Евклида (III век до н. э.), который впервые описал его в VII[1] и X[2] книгах «Начал». Это один из старейших численных алгоритмов, используемых в наше время[3].

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

Для данного алгоритма существует множество теоретических и практических применений. В частности, он является основой для криптографического алгоритма с открытым ключом RSA[4], широко распространённого в электронной коммерции. Также алгоритм используется при решении линейных диофантовых уравнений[5], при построении непрерывных дробей[6], в методе Штурма[7]. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел, например таких как теорема Лагранжа о сумме четырёх квадратов[8] и основная теорема арифметики[9].

История[править | править код]

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

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

Описание[править | править код]

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

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

{displaystyle a>b>r_{1}>r_{2}>r_{3}>r_{4}> dots >r_{n}}

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

a=bq_{0}+r_{1},
b=r_{1}q_{1}+r_{2},
r_{1}=r_{2}q_{2}+r_{3},
cdots
r_{k-2}=r_{k-1}q_{k-1}+r_{k},
cdots
r_{n-2}=r_{n-1}q_{n-1}+r_{n},
r_{n-1}=r_{n}q_{n}.

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

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

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

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

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

  1. Пусть k — любой общий делитель чисел a и b, не обязательно наибольший, тогда a = t1⋅k и b = t2⋅k, где t1 и t2 — целые числа из определения.
  2. Тогда k является также общим делителем чисел b и r, так как b делится на k по определению, а {displaystyle r=a-bcdot q=(t_{1}-t_{2}cdot q)cdot k} (выражение в скобках есть целое число, следовательно, k делит r без остатка).
  3. Обратное также верно и доказывается аналогично пункту 2: любой делитель b и r так же является делителем a и b.
  4. Следовательно, все общие делители пар чисел (a, b) и (b, r) совпадают. Другими словами, нет общего делителя у чисел (a, b), который не был бы также делителем (b, r), и наоборот.
  5. В частности, наибольший общий делитель остаётся тем же самым, так как в предположении, что НОД (a, b) > НОД (b, r) или НОД (a, b) < НОД (b, r) получаются противоречия, следовательно, НОД (a, b) = НОД (b, r). Что и требовалось доказать.

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

Геометрический алгоритм Евклида[править | править код]

Пусть даны два отрезка длины a и b. Вычтем из большего отрезка меньший и заменим больший отрезок полученной разностью. Повторяем эту операцию, вычитая из большего отрезка меньший, пока отрезки не станут равны. Если это произойдёт, то исходные отрезки соизмеримы, и последний полученный отрезок есть их наибольшая общая мера. Если общей меры нет, то процесс бесконечен. В таком виде алгоритм описан Евклидом[2] и реализуется с помощью циркуля и линейки.

Пример[править | править код]

Для иллюстрации алгоритм Евклида будет использован, чтобы найти НОД 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 > … > 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; алгоритм заканчивается

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

Применения[править | править код]

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

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

r_{1}=a+b(-q_{0})
r_{2}=b-r_{1}q_{1}=a(-q_{1})+b(1+q_{1}q_{0})
vdots
НОД (a,b)=r_{n}=as+bt

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

Цепные дроби[править | править код]

Алгоритм Евклида достаточно тесно связан с цепными дробями[6]. Отношение 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}}.

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

{begin{aligned}{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{aligned}}

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

{frac {a}{b}}=q_{0}+{cfrac {1}{q_{1}+{cfrac {r_{1}}{r_{0}}}}}

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

{frac {a}{b}}=q_{0}+{cfrac {1}{q_{1}+{cfrac {1}{q_{2}+{cfrac {r_{2}}{r_{1}}}}}}}

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

{frac {a}{b}}=q_{0}+{cfrac {1}{q_{1}+{cfrac {1}{q_{2}+{cfrac {1}{ddots +{cfrac {1}{q_{N}}}}}}}}}=[q_{0};q_{1},q_{2},ldots ,q_{N}]

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

{displaystyle {frac {1071}{462}}=2+{cfrac {1}{3+{cfrac {1}{7}}}}=[2;3;7]}

Линейные диофантовы уравнения[править | править код]

Диофантово уравнение — это уравнение с целочисленными коэффициентами и с одним или несколькими переменными, причём ставится задача поиска лишь его целых корней. Такое уравнение может иметь бесконечно много решений, конечное число решений или не иметь их вовсе. Простейшее диофантово уравнение — линейное с двумя неизвестными:

acdot x+bcdot y=c,

где a, b, c — целые числа. С помощью алгоритма Евклида может быть найдено полное решение уравнения такого типа[5]. Сначала с помощью этого алгоритма можно определить d = НОД(a, b). Затем, используя расширенный алгоритм Евклида, определяются такие k и l, что:

acdot k+bcdot l=d.

То есть x = k и y = l — это частное решение уравнения при c = d. Получается, что если c = q⋅d, то x = q⋅k, y = q⋅l — частное решение исходного уравнения, так как:

acdot x+bcdot y=acdot (qcdot k)+bcdot (qcdot l)=qcdot (acdot k+bcdot l)=qcdot d=c.

Обратно, если существует хотя бы одно решение уравнения, то c кратно d. Это следует из того, что d делит и a, и b (а значит, и всю левую часть), поэтому должно делить и c (правую часть). Таким образом, линейное диофантово уравнение имеет хотя бы одно решение тогда и только тогда, когда c кратно НОД(a, b).

Вариации и обобщения[править | править код]

Евклидово кольцо[править | править код]

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

Обобщённый алгоритм Евклида для многочленов[править | править код]

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

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

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

cont(НОД{p_{1}(x),p_{2}(x)})=НОД{cont(p_{1}(x)),cont(p_{2}(x))},

primpart(НОД{p_{1}(x),p_{2}(x)})=НОД{primpart(p_{1}(x)),primpart(p_{2}(x))}.

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

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

Под псевдоделением будем понимать, что самому делению предшествует умножение полинома p_{1}(x) на (lc(p_{2}(x)))^{m-n+1}, то есть

lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),deg(r(x))<deg(p_{2}(x)),

где q(x) и r(x) — соответственно псевдочастное и псевдоостаток.

Итак, p_{1}(x),p_{2}(x)in Z[x], причём deg(p_{1})=n_{1}geq deg(p_{2})=n_{2}. Тогда алгоритм Евклида состоит из следующих шагов:

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

c:=НОД{cont(p_{1}),cont(p_{2})}.

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

p_{1}'(x):=primpart(p_{1}(x));

p_{2}'(x):=primpart(p_{2}(x)).

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

p_{1}'(x),

p_{2}'(x),

p_{3}(x):=prem(p_{1}'(x),p_{2}'(x)),

p_{4}(x):=prem(p_{2}'(x),p_{3}(x)),

p_{5}(x):=prem(p_{3}(x),p_{4}(x)),

...

p_{h}(x):=prem(p_{h-2}(x),p_{h-1}(x)).

4. Возврат результата:

Если deg(p_{h}(x))=0, то вернуть c, иначе вернуть ccdot primpart(p_{h}(x)).

Ускоренные версии алгоритма[править | править код]

  • Одним из методов ускорения целочисленного алгоритма Евклида является использование симметричного остатка[16]:
r_{i}equiv r_{i-2}{pmod {r_{i-1}}},
где

-{frac {r_{i-1}}{2}}leq r_{i}leq {frac {r_{i-1}}{2}}.
  • Одна из версий ускоренного алгоритма Евклида для полиномов основывается на том, что промежуточные значения алгоритма в основном зависят от высоких степеней. Применение стратегии «разделяй и властвуй» позволяет уменьшить асимптотическую сложность алгоритма[16].

Вычислительная сложность алгоритма[править | править код]

"A set of colored lines radiating outwards from the origin of an x-y coordinate system. Each line corresponds to a set of number pairs requiring the same number of steps in the Euclidean algorithm."

Число шагов в алгоритме Евклида для НОД(x,y). Более светлые точки (красные и жёлтые) указывают на относительно меньшее количество шагов, тогда как более тёмные точки (фиолетовые и синие) на большее количество шагов. Самая большая тёмная область следует за прямой y = Φx, где Φ — золотое сечение.

Вычислительная сложность алгоритма Евклида изучена полностью.[17] Эта сложность может быть описана произведением количества шагов деления, требуемых алгоритмом, на вычислительную сложность одного шага. Первый известный анализ алгоритма Евклида был предложен Рейнаудом в 1811.[18] Он показал, что число шагов алгоритма для пары чисел (u, v) ограничено v. Позже он улучшил оценку до v/2 + 2. Эмиль Леже в 1837 году изучил наихудший случай, когда для вычисления НОД подаются последовательные числа Фибоначчи.[19] Затем, в 1841 году, Пьер Джосеф Финк показал,[20] что количество шагов алгоритма не превышает 2 log2 v + 1. Следовательно, алгоритм работает за полиномиальное время от размера меньшего из пары чисел (u, v).[19] Анализ Финка был уточнён Габриэлем Ламе в 1844 году.[21] Он показал, что количество шагов, необходимых для завершения алгоритма, не более чем в пять раз превышает h — количество цифр в десятичном представлении меньшего из пары чисел (u, v).[22][23]

Когда НОД вычисляется для чисел, которые вписываются в одно машинное слово, каждый шаг алгоритма занимает постоянное время. В данном случае анализ Ламе предполагает, что вычислительная сложность оценивается как O(h). Однако в модели расчёта, подходящей для вычислений с числами больше одного машинного слова, оценка сложности вычисления одного остатка может быть O(h2).[24] В этом случае общее время для всех этапов алгоритма можно проанализировать с помощью телескопического ряда, показав, что это также O(h2). Для ускорения алгоритма Евклида могут быть использованы современные алгоритмические методы, основанные на методе Шёнхаге — Штрассена для быстрого целочисленного умножения. Это приводит к квазиполиномиальному времени.[25]

Количество шагов[править | править код]

Число шагов для вычисления НОД двух натуральных чисел a и b обозначим как T(a, b). Если g — это наибольший общий делитель a и b, тогда a = mg и b = ng для двух взаимно простых чисел m и n. Тогда T(a, b) = T(m, n), что можно заметить, если разделить уравнения, полученные при вычислении НОД для пары (a, b), на g.[26] Используя тот же принцип, число шагов алгоритма остаётся неизменным, если a и b умножаются на общий множитель w, что эквивалентно равенству T(a, b) = T(wa, wb). Следовательно, количество шагов T может сильно различаться между соседними парами чисел, такими как (a, b) и (a, b+1), так как данная величина зависит от НОД.

Рекурсивный характер алгоритма Евклида даёт следующее уравнение T(a, b) = 1 + T(b, r0) = 2 + T(r0, r1) = … = N + T(rN−2, rN−1) = N + 1, где T(x, 0) = 0 по предположению.[17]

Наихудший случай[править | править код]

Если для алгоритма Евклида требуются N шагов для пары натуральных чисел a > b > 0, наименьшие значения a и b, для которых это выполняется — числа Фибоначчи FN+2 и FN+1 соответственно.[27] Тогда, если алгоритм Евклида требует N шагов для пары чисел (a,b), где a > b, выполняются следующие неравенства a ≥ FN+2 и b ≥ FN+1. Доказать это можно по математической индукции. Если N = 1, тогда a делится на b без остатка. Наименьшие натуральные числа, для которых это верно, равны b = 1 и a = 2, соответственно F2 и F3. Предположим теперь, что результат выполняется для всех значений N до M − 1. Первый шаг алгоритма Евклида с M шагами a = q0b + r0, и алгоритм Евклида для пары чисел (b,r0), где b > r0, требует M − 1 шагов. По предположению индукции имеем b ≥ FM+1 и r0 ≥ FM. Следовательно, a = q0b + r0 ≥ b + r0 ≥ FM+1 + FM = FM+2, что является искомым неравенством. Это доказательство, опубликованное Габриэлем Ламе в 1844 году, представляет собой начало теории сложности вычислений,[28] а также первое практическое применение чисел Фибоначчи.[27]

Теорема Ламе[править | править код]

Число делений с остатком в процессе применения алгоритма Евклида не превосходит упятеренного количества цифр меньшего числа b, записанного в десятичной системе[29].

Среднее[править | править код]

Существуют различные способы вычисления среднего количества шагов алгоритма. Первый способ вычисления — среднее время T(a), необходимое для вычисления НОД заданного числа a и меньшего натурального числа b, выбранного с равной вероятностью из целых чисел от 0 до a − 1.[17]

{displaystyle T(a)={frac {1}{a}}sum _{0leq b<a}T(a,b).}

Однако, поскольку T(a, b) сильно колеблется в зависимости от НОД двух чисел, усреднённая функция T(a) также является «шумной».[30] Для того, чтобы уменьшить этот шум, второе среднее τ(a) берётся по всем числам, взаимно простым с a.

{displaystyle tau (a)={frac {1}{varphi (a)}}sum _{begin{smallmatrix}0leq b<a\gcd(a,b)=1end{smallmatrix}}T(a,b)}

где φ(a) функция Эйлера. Это среднее плавно растёт с ростом a.[31]

{displaystyle tau (a)={frac {12}{pi ^{2}}}ln 2ln a+C+O(a^{-1/6-varepsilon })}

Константа (константа Портера[32]) в этой формуле {displaystyle Capprox 1.467}, а ε является бесконечно малым.

Третье среднее значение Y(n) определяется как среднее число шагов, требуемых, когда a и b выбираются случайным образом (с равномерным распределением) от 1 до n.

{displaystyle Y(n)={frac {1}{n^{2}}}sum _{a=1}^{n}sum _{b=1}^{n}T(a,b)={frac {1}{n}}sum _{a=1}^{n}T(a).}

Вычислительная сложность шага[править | править код]

На каждом шаге алгоритма Евклида вычисляется коэффициент qk и остаток rk для заданной пары целых чисел rk−2 и rk−1. Эти величины связаны следующим соотношением:

rk−2 = qk rk−1 + rk

Вычислительная сложность каждого шага связана главным образом с нахождением qk, так как остаток rk можно быстро вычислить, используя rk−2, rk−1, и qk

rk = rk−2 − qk rk−1

Вычислительная сложность операции деления чисел размером h бит оценивается как O(h(ℓ+1)), где ℓ размер частного.[24]

Для сравнения, исходный алгоритм Евклида, с использованием вычитания, может быть намного медленнее. В большинстве случаев коэффициент qk является малым числом. Вероятность данного частного q примерно равна ln|u/(u − 1)|, где u = (q + 1)2.[33] Для иллюстрации вероятность частного 1, 2, 3 или 4 составляет примерно 41,5 %, 17,0 %, 9,3 % и 5,9 % соответственно. Так как операция вычитания быстрее, чем деление, особенно для чисел больше одного машинного слова,[34] алгоритм Евклида с использованием вычитания может быть более конкурентоспособным в сравнении с алгоритмом, использующим деление.[35] Это используется в бинарном алгоритме вычисления НОД.[36]

Оценка сложности алгоритма вычисляется как произведение количества шагов на время выполнения одного шага. Она показывает, что алгоритм Евклида растёт квадратично O(h2), где h — среднее число цифр в двух начальных числах a и b в десятичной записи. Пусть h0, h1, …, hN−1 представляют число цифр в последовательных остатках r0, r1, …, rN−1. Так как число шагов N растёт линейно с h, время работы ограничено следующим выражением:

{displaystyle O{Big (}sum _{i<N}h_{i}(h_{i}-h_{i+1}+2){Big )}subseteq O{Big (}hsum _{i<N}(h_{i}-h_{i+1}+2){Big )}subseteq O(h(h_{0}+2N))subseteq O(h^{2}).}

Примечания[править | править код]

  1. ↑ 1 2 Мордухай-Болтовской, 1949, с. 11—13.
  2. ↑ 1 2 3 Мордухай-Болтовской, 1949, с. 103—105.
  3. ↑ 1 2 Кнут, 2001, с. 378.
  4. ↑ Menezes, 1996, с. 286.
  5. ↑ 1 2 Курант, 2001, с. 74—76.
  6. ↑ 1 2 Виноградов, 1952, с. 14—18.
  7. ↑ Энгелер, 1987, с. 24—31.
  8. ↑ Тихомиров, 2003, с. 11—14.
  9. ↑ Калужин, 1969, с. 6—14.
  10. ↑ Цейтен, 1932, с. 112—114.
  11. ↑ Виноградов, 1952, с. 9—10.
  12. ↑ Курант, 2001, с. 67—70.
  13. ↑ Хассе, 1953, с. 29—30.
  14. ↑ Курош, 1973, с. 91—92.
  15. ↑ Панкратьев, 2007, с. 54—58.
  16. ↑ 1 2 Gathen, 2013, с. 313—326.
  17. ↑ 1 2 3 Knuth, 1997, с. 344.
  18. ↑ Shallit, 1994, с. 414.
  19. ↑ 1 2 Shallit, 1994, с. 401—419.
  20. ↑ Shallit, 1994, с. 413.
  21. ↑ Lame, 1844, с. 867—870.
  22. ↑ Grossman, 1924, с. 443.
  23. ↑ Абрамов С. А. Математические построения и программирование. — М., Наука, 1978. — Тираж 100 000 экз. — c. 170
  24. ↑ 1 2 Knuth, 1997, с. 257—261.
  25. ↑ Moeller, 2005, с. 1.
  26. ↑ Ore, 1948, с. 45.
  27. ↑ 1 2 Knuth, 1997, с. 343.
  28. ↑ LeVeque, 1996, с. 3.
  29. ↑ Абрамов С. А. Математические построения и программирование. — М., Наука, 1978. — Тираж 100 000 экз. — c. 170
  30. ↑ Knuth, 1997, с. 353.
  31. ↑ Tonkov, 1974, с. 47—57.
  32. ↑ Weisstein, Eric W. Porter’s Constant (англ.) на сайте Wolfram MathWorld.
  33. ↑ Knuth, 1997, с. 352.
  34. ↑ Wagon, 1999, с. 335—336.
  35. ↑ Cohen, 1993, с. 14.
  36. ↑ Cohen, 1993, с. 14—15, 17-18.

Литература[править | править код]

  • Абрамов С. А. Самый знаменитый алгоритм // Квант / под ред. И. К. Кикоин, Ю. А. Осипьян, В. В. Козлов, А. Л. Семёнов, А. А. Гайфуллин — МИАН, 1985. — вып. 11. — С. 44—46. — ISSN 0130-2221
  • Виноградов И. М. Основы теории чисел. — М.—Л.: ГИТТЛ, 1952. — 180 с. — ISBN 978-5-811-40535-0.
  • Калужин Л. А. Основная теорема арифметики. — Популярные лекции по математике. — М.: Наука, 1969. — 33 с.
  • Кнут Д. Э. Искусство программирования. — Вильямс, 2001. — Т. 2. — 829 с. — ISBN 5-8459-0081-6.
  • Курант Р., Роббинс Г. Дополнение к главе I, § 4. // Что такое математика? — 3-e изд., испр. и доп. — М., 2001. — 568 с. — ISBN 5-900916-45-6.
  • Курош А. Г. Лекции по общей алгебре / под ред. О. Н. Головин — 2-е изд. — М.: Наука, 1973. — 400 с. — ISBN 978-5-8114-0617-3
  • Начала Евклида / пер.с греч. и комм. Д. Д. Мордухая-Болтовского под ред. Выгодского М. Я. и Веселовского И. Н.. — ГИТТЛ, 1949. — Т. 2. — 511 с.
  • Панкратьев Е. В. Элементы компьютерной алгебры. — ИНТУИТ, 2007. — 217 с. — ISBN 978-5-955-60099-4.
  • Тихомиров В. М. Великие математики прошлого и их великие теоремы. — 2-е изд., испр. — МЦНМО, 2003. — 16 с. — ISBN 5-94057-110-7.
  • Хассе Г. Лекции по теории чисел. — Изд. иностранной литературы, 1953. — 527 с.
  • Цейтен Г. Г. История математики в Древности и в Средние века. — ГТТИ, 1932. — 232 с.
  • Энгелер Э. Метаматематика элементарной математики. — М.: Мир, 1987. — 128 с.
  • Cohen H. A Course in Computational Algebraic Number Theory. — Springer-Verlag, 1993. — ISBN 0-387-55640-0.
  • von zur Gathen J., Gerhard J. Modern Computer Algebra. — Cambridge University Press, 2013. — 808 с. — ISBN 978-1-107-03903-2.
  • Grossman H. On the Number of Divisions in Finding a G.C.D. (англ.) // The American Mathematical Monthly. — 1924. — Vol. 31, iss. 9. — P. 443. — doi:10.2307/2298146. — JSTOR 2298146.
  • Knuth D. E. The Art of Computer Programming. — 3. — Addison–Wesley, 1997. — Т. 2: Seminumerical Algorithms. — ISBN 0-201-89684-2.
  • Lamé G. Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers (фр.). — Comptes Rendus Acad. Sci., 1844. — No 19.
  • LeVeque W. J. Fundamentals of Number Theory (англ.). — Dover, 1996. — ISBN 0-486-68906-9.
  • Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC-Press, 1996. — 816 с. — (Discrete Mathematics and Its Applications). — ISBN 0-8493-8523-7.
  • Moeller Niels. Mathematics of Computation (англ.). — 2005.
  • Ore O. Number Theory and Its History (англ.). — McGraw–Hill, 1948.
  • Shallit J. Origins of the analysis of the Euclidean algorithm (англ.) // Historia Math.. — 1994. — Vol. 21. — doi:10.1006/hmat.1994.1031.
  • Tonkov T. On the average length of finite continued fractions (англ.) // Acta Arithmetica. — 1974. — Vol. 26.
  • Wagon S. Mathematica in Action (англ.). — Springer-Verlag, 1999. — ISBN 0-387-98252-3.

Ссылки[править | править код]

  • Реализация алгоритма Евклида на языке Pascal
  • Алгоритм Евклида на e-maxx.ru
  • Реализация расширенного алгоритма Евклида на языке C
Источник

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

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

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

Суть алгоритма заключается в том, чтобы последовательно проводить деление с остатком, в ходе которого получается ряд равенств вида:

a=b·q1+r1, 0<r1<bb=r1·q2+r2, 0<r2<r1r1=r2·q3+r3, 0<r3<r2r2=r3·q4+r4, 0<r4<r3⋮rk-2=rk-1·qk+rk, 0<rk<rk-1rk-1=rk·qk+1

Мы можем закончить деление тогда, когда rk+1=0, при этом rk=НОД(a, b).

Пример 1

Найдите наибольший общий делитель чисел 64 и 48.

Решение

Введем обозначения: a=64, b=48.

На основе алгоритма Евклида проведем деление 64 на 48.

Получим 1 и остаток 16. Получается, что q1=1, r1=16.

Вторым шагом разделим 48 на 16, получим 3. То есть q2=3, а r2=0. Таким образом число 16 – это наибольший общий делитель для чисел из условия.

Ответ: НОД(64, 48)=16.

Пример 2

Чему равен НОД чисел 111 и 432?

Решение

Делим 432 на 111. Согласно алгоритму Евклида получаем цепочку равенств 432=111·3+99, 111=99·1+12, 99=12·8+3, 12=3·4.

Таким образом, наибольший общий делитель чисел 111 и 432 – это 3.

Ответ: НОД(111, 432)=3.

Пример 3

Найдите наибольший общий делитель чисел 661 и 113.

Решение

Проведем последовательно деление чисел и получим НОД(661, 113)=1. Это значит, что 661 и 113 – это взаимно простые числа. Мы могли выяснить это до начала вычислений, если бы обратились к таблице простых чисел.

Ответ: НОД(661, 113)=1.

Нахождение НОД с помощью разложения чисел на простые множители

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

Пример 4

Если мы разложим числа 220 и 600 на простые множители, то получим два произведения: 220=2·2·5·11 и 600=2·2·2·3·5·5. Общими в этих двух произведениях будут множители 2,2 и 5. Это значит, что НОД(220, 600)=2·2·5=20.

Пример 5

Найдите наибольший общий делитель чисел 72 и 96.

Решение

Найдем все простые множители чисел 72 и 96:

72361893122233

96482412631222223

Общими для двух чисел простые множители: 2, 2, 2 и 3. Это значит, что НОД(72, 96)=2·2·2·3=24.

Ответ: НОД(72, 96)=24.

Правило нахождения наибольшего общего делителя двух чисел основано на свойствах наибольшего общего делителя, согласно которому НОД(m·a1, m·b1)=m·НОД(a1, b1), где m– любое целое положительное число.

Нахождение НОД трех и большего количества чисел

Независимо  от количества чисел, для которых нам нужно найти НОД, мы будем действовать по одному и тому же алгоритму, который заключается в последовательном нахождении НОД двух чисел. Основан этот алгоритм на применении следующей теоремы: НОД нескольких чисел a1, a2, …, ak равен числу dk, которое находится при последовательном вычислении НОД(a1, a2)=d2, НОД(d2, a3)=d3, НОД(d3, a4)=d4, …, НОД(dk-1, ak)=dk.

Пример 6

Найдите наибольший общий делитель четырех чисел 78, 294, 570 и 36.

Решение

Введем обозначения: a1=78, a2=294, a3=570, a4=36.

Начнем с того, что найдем НОД чисел 78 и 294: d2=НОД(78, 294)=6.

Теперь приступим к нахождению d3=НОД(d2, a3)=НОД(6, 570). Согласно алгоритму Евклида 570=6·95. Это значит, что d3=НОД(6, 570)=6.

Найдем d4=НОД(d3, a4)=НОД(6, 36). 36 делится на 6 без остатка. Это позволяет нам получить d4=НОД(6, 36)=6.

d4=6, то есть, НОД(78, 294, 570, 36)=6.

Ответ: НОД(78, 294, 570, 36)=6.

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

Пример 7

Вычислите НОД чисел 78, 294, 570 и 36.

Решение

Произведем разложение данных чисел на простые множители: 78=2·3·13, 294=2·3·7·7, 570=2·3·5·19, 36=2·2·3·3.

Для всех четырех чисел общими простыми множителями будут числа 2 и 3.

Получается, что НОД(78, 294, 570, 36)=2·3=6.

Ответ: НОД(78, 294, 570, 36)=6.

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

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

Пример 8

Найдите НОД отрицательных целых чисел −231 и −140.

Решение

Для выполнения вычислений возьмем модули чисел, данных в условии. Это будут числа 231 и 140. Запишем это кратко: НОД(−231, −140)=НОД(231, 140). Теперь применим алгоритм Евклида для нахождения простых множителей двух чисел: 231=140·1+91; 140=91·1+49; 91=49·1+42; 49=42·1+7 и 42=7·6. Получаем, что НОД(231, 140)=7.

А так как НОД(−231, −140)=НОД(231, 140), то НОД чисел −231 и −140 равен 7.

Ответ: НОД(−231, −140)=7.

Пример 9

Определите НОД трех чисел −585, 81 и −189.

Решение

Заменим отрицательные числа в приведенном перечне на их абсолютные величины, получим  НОД(−585, 81, −189)=НОД(585, 81, 189). Затем разложим все данные числа на простые множители: 585=3·3·5·13, 81=3·3·3·3 и 189=3·3·3·7. Общими для трех чисел являются простые множители 3 и 3. Получается , что НОД(585, 81, 189)=НОД(−585, 81, −189)=9.

Ответ: НОД(−585, 81, −189)=9.

Ирина Мальцевская

Преподаватель математики и информатики. Кафедра бизнес-информатики Российского университета транспорта

Источник

Как найти НОД двух чисел по алгоритму Евклида

Содержание:

  • Что такое алгоритм Евклида
  • Понятие НОД
  • Основная суть алгоритма Евклида

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

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

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

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

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

Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.

Понятие НОД

Аббревиатура НОД расшифровывается как «наибольший общий делитель».

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

Основная суть алгоритма Евклида

Суть алгоритма заключается в построении ряда следующего вида (при условии, что a больше b):

a, b, x1, x2, x3, … xn.

В нем каждое последующее число — это остаток от деления двух предыдущих, ряд заканчивается, когда остаток от деления становится равным 0 — при условии использования деления.

В нем каждое последующее число является результатом вычитания двух предыдущих, ряд заканчивается, когда частное становится равным 0 — при условии использования вычитания.

Последовательность нахождения НОД при помощи деления:

  1. Большее число делится на меньшее.
  2. Если результат деления:
  • без остатка, то меньшее число и есть НОД;
  • с остатком, тогда большее число заменяется на остаток.
  1. Переход к пункту 1.

Пример №1

60 / 36 = 1 (остаток 24)

36 / 24 = 1 (остаток 12)

24 / 12 = 2 (остаток 0)

НОД для 60 и 36 равен 12 (делитель).

Последовательность нахождения НОД при помощи вычитания:

  1. Из большего числа вычитается меньшее.
  2. Если результат вычитания:
  • равен 0, то числа равны друг другу и являются НОД;
  • не равен 0, в таком случае большее число заменяется на результат вычитания.
  1. Переход к пункту 1.

Пример №2

60 — 36 = 24

36 — 24 = 12

24 — 12 = 12

12 — 12 = 0

НОД для 60 и 36 равен 12 (уменьшаемое, вычитаемое)

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

Задача №1

Найти наибольший общий делитель для чисел 128 и 96.

Решение:

128 — 96 = 32

96 — 32 = 64

64 — 32 = 32

32 — 32 = 0

Или

128 / 96 = 1 (остаток 32)

96 / 32 = 3

Ответ: 32

Задача №2

Найти наибольший общий делитель для чисел 37 и 17.

Решение:

37 / 17 = 2 (остаток 3)

17 / 3 = 5 (остаток 2)

3 / 2 = 1 (остаток 1)

2 / 1 = 2 (остаток 0)

Или

37 — 17= 20

20 — 17 = 3

17 — 3 = 14

14 — 3 = 11

11 — 3 = 8

8 — 3 = 5

5 — 3 = 2

3 — 2 = 1

2 — 1 = 1

1 — 1 = 0

Числа 37 и 17 являются простыми, соответственно, их НОД — единица. Совет: перед вычислениями проверяйте таблицу простых чисел.

Ответ: 1

Насколько полезной была для вас статья?

Рейтинг: 4.50 (Голосов: 18)

Выделите текст и нажмите одновременно клавиши «Ctrl» и «Enter»

Текст с ошибкой:

Расскажите, что не так

Поиск по содержимому

Источник

#хакнем_математика 👈 рубрика, содержащая интересный, познавательный контент по математике как для школьников, так и для взрослых 🥳

Евклид, ок. 1474. Юстус ван Гент
Евклид, ок. 1474. Юстус ван Гент

Цикл статей “Дроби”

Первая часть Вторая часть Третья часть

Четвертая часть Пятая часть Шестая часть Седьмая часть Восьмая часть

Здравствуйте, уважаемые читатели!

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

Для начала опишем последовательность шагов алгоритма.

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

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

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

Замечу, что описание Алгоритма Евклида для нахождения НОД двух натуральных чисел значительно «объёмнее» его исполнения. Найдём, например, НОД (1729; 2584) сначала с использованием традиционного метода с разложением чисел на простые множители, а затем с помощью алгоритма Евклида.

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

Алгоритм Евклида для нахождения НОД двух натуральных чисел, который вы не найдёте в школьных учебниках

А теперь используем алгоритм:

Алгоритм Евклида для нахождения НОД двух натуральных чисел, который вы не найдёте в школьных учебниках

ОТВЕТ: НОД (1729; 2584) = 19.

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

Автор: #себихов_александр 71 год, много лет проработал конструктором-технологом микроэлектронных приборов и узлов в одном из НИИ г. Саратова, затем преподавателем математики и физики.

Читайте наш канал в телеграм – по этой ссылке

Другие статьи автора:

Алгоритм Евклида для нахождения НОД двух натуральных чисел, который вы не найдёте в школьных учебниках

Цикл статей “Дроби”

1 статья 2 статья 3 статья 4 статья 5 статья 6 статья

7 статья 8 статья 9 статья [Текущая]

Источник

Алгоритм Евклида – нахождение наибольшего общего делителя

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.

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

Решение задачи на языке программирования Python

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

  1. Большее число делим на меньшее.
  2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
  3. Если есть остаток, то большее число заменяем на остаток от деления.
  4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0)
Конец: НОД – это делитель 6.
НОД (30, 18) = 6

a = int(input())
b = int(input())
 
while a != 0 and b != 0:
    if a > b:
        a = a % b
    else:
        b = b % a
 
print(a + b)

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

Если условием завершения цикла является равенство хотя бы одной из переменных нулю (a == 0 or b == 0), то условием продолжения его работы является обратное этому условие – обе переменные должны иметь отличные от нуля значения (a != 0 and b != 0).

Блок-схема алгоритма Евклида

Для того, чтобы вышеприведенная программа могла обрабатывать отрицательные числа, в логическом выражении при if должны сравниваться модули значений переменных: if abs(a) > abs(b):. Иначе большим числом может оказаться меньшее по модулю. В этом случае интерпретатор Питона в качестве остатка от деления выдает вещественное число. В результате это приводит к зацикливанию, так как низвести переменные до нуля становится как минимум маловероятным.

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

  1. Из большего числа вычитаем меньшее.
  2. Если получается 0, значит, числа равны друг другу и являются НОД (следует выйти из цикла).
  3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
  4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 – 18 = 12
18 – 12 = 6
12 – 6 = 6
6 – 6 = 0
Конец: НОД – это уменьшаемое или вычитаемое.
НОД (30, 18) = 6

a = int(input())
b = int(input())
 
while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a
 
print(a)

Функция, вычисляющая НОД

def gcd(m, n):
    while m != n:
        if m > n:
            m = m - n
        else:
            n = n - m
    return n
 
 
a = int(input())
b = int(input())
 
print(gcd(a, b))

Функция gcd модуля math

В модуле math языка программирования Python есть функция gcd, вычисляющая наибольший общий делитель двух чисел.

>>> import math
>>> math.gcd(30, 18)
6

Больше задач в PDF

Источник

Добавить комментарий